Algorithm for optimal item selections

This problem is NP-Hard by a reduction from the following version of subset sum: given a multi-set $X$ of $2n$ numbers $\{x_1, \dots, x_{2n}\}$ and a target $T$, is there a subset $X'$ of $X$ with $|X'|=n$ and $\sum_{x \in X'} =T$?

However, the problem admits a pseudopolynomial-time dynamic programming algorithm when all weights are integers.

Let $OPT[x]$ be true ($\top$) if there is a way to choose a subset of products whose sum of weights is exactly $x$, and false ($\bot$) otherwise. Clearly $OPT[0]= \top$ and $OPT[x]=\bot$ for $x<0$. Moreover, denoting by $w_i$ the weight of the $i$-th product, whenever $x>0$ you have: $$ OPT[x] = \bigvee_{i=1}^N OPT[x-w_i]. $$

Each value $OPT[x]$ for $x = 0, \dots, X$ can be computed in time $O(N)$, and hence all such values can be found in time $O(N \cdot X)$.

The minimum amount $X^*$ that is not smaller than $X$ can be found in an additional $O(N \cdot X)$ time since either $OPT[X]=\top$ (i.e., $X^* = X$) or it can be found by adding one more product to some achievable amount $x$, i.e., $$ X^* = \min_{i=1,\dots,N} \left( w_i + \min_{\substack{x = \max (0, X-w_i+1), \dots, X-1 \\ OPT[x]=\top}} x \right), $$ where we treat a minimum over an empty range as $+\infty$.

The actual solution can be found (in the same asymptotic time) by retracing the optimal choices backwards.