Let $n$ be a natural number $\geq 2$ and for each $i = 1 \ldots k$ let $P_i(x)$ be a polynomial modulo $x^n - 1$ with non-negative integer coefficients. The weight $w(P(x))$ of a polynomial $P(x)$ is the number of non-vanishing terms in $P(x)$.
Problem: Maximize the polynomial weight of
$\sum_{i=1}^k x^{t_i} \cdot P_i(x)$ modulo $x^n - 1$
subject to $t_i \geq 0$ for $i = 1 \ldots k$ and
$\sum_{i=1}^k w(P_i(x)) \leq m$.
Note 1. Non-negative coefficients make sure that no term vanishes under summation of polynomials. For this purpose, the given polynomials may as well have coefficients among $\{ 0, 1 \}$.
Note 2. Mostly $m \leq n$. My special interest is $m = n$.
The posed problem looks much the same as the Knapsack problem. However, there are fundamental differences:
First, the maximal weight of a polynomial combination, $n$, is built in physically as polynomials are taken modulo $x^n - 1$.
Second, the combination "coefficients" $x^{t_i}$ aren't weight factors: individually, they do not change the weight of the polynomial to which it is assigned.
The above maximizing problem is a translation of a purely combinatorial problem in an $n$ by $n$ board: choose any n locations. By cyclically shifting some columns up or down, the chosen set may take a different shape. The problem is, then, to find shifting amounts for each involved column maximizing the number of rows involved with the set.
Call this a vertical (V-)optimization. There is a similar process of horizontal (H-)optimization.
A fundamental result (proven for n up to 37) is that applying an H-optimization on a V-optimized set yields a transversal of the columns. A dual result holds for reasons of symmetry.
Cyclically shifting columns, then rows, is a process called shuffling. It is notoriously good at randomizing a board filled with digits (in whatever base) and finally delivers a rich family of encryption- or hash-procedures.
NP-completeness of the basic operation would be a very welcome property.