Simple Unbounded Multi-Knapsack with Distinct Items Constraint - strongly or weakly NP-c?

Question

Is the following Knapsack problem strongly or weakly NP-hard? We have unbounded knapsacks, meaning we can use each item unlimited number of times.

Given:

$I = \{ w_1, ... w_n \}$ - a set of the available items to use (weight=value)

$C = {c_1, ... c_m}$ - $m$ knapsacks (with possibly different capacities)

$s$ - a total amount of distinct items that can be used (from $I$, $s\leq n$)

Question: Can all knapsacks be completely filled by using at most $M$ items in total? Where $M$ counts the multiplicity of each item used.

The answer is trivial if we remove the constraint $s$. We can simply run a DP for each knapsack, and return yes if sum of minimum items required among all knapsacks is at most $M$.

However, by adding the constraint, it seems that too many dimensions appear in the DP, making it exponential.

Do you have any advice on what reduction could possibly be done, or if there is an pseudopolynomial algorithm for that, provide any information for it?

Answer 1

The problem asks whether m knapsacks can be filled exactly using at most M items drawn from at most s distinct item types, each type available in unlimited quantity. A classical pseudo‐polynomial DP for (unbounded) multi‐knapsack keeps one dimension per knapsack ­capacity and, for each item type, decides how many copies to add. When you introduce the extra requirement "use ≤ s distinct types in total", the DP must somehow remember which types have already been chosen so it does not exceed the limit. In complexity theory a decision problem is in NP if, whenever the answer is "yes", there exists a short certificate (also called a witness) that lets us verify that "yes" answer in time polynomial in the input size.

For your knapsack variant a natural certificate is needed that is simply a table that tells, for every knapsack and every item type you use, how many copies of that type go into that knapsack. Concretely the certificate can be written as:

knapsack j	item i1	item i2	...	item ik
1	x11	x12	...	x1k
2	x21	x22	...	x2k
...	...	...	...	...
m	xm1	xm2	...	xmk

Here the set {i1,...,ik} lists the ≤ s distinct item types actually used, and xjl is a non‐negative integer giving how many copies of type il are placed in knapsack j. (Any entries for unused types are simply omitted or set to 0.) To verify the certificate we perform four straightforward checks, each doable in polynomial time.

Capacity check: For every knapsack j compute $$ \sum_{\ell=1}^{k} x_{j\ell} \cdot w_{i_\ell} $$ and confirm it equals the capacity cj. I tried a tiny "brute‐force + limited‐search" algorithm that solves one toy instance of the problem, so you can see the logic in action if needed.