There is a problem that I can not solve.
Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the total weight should not be more than some weight limit:
$\sum_{j=1..n}w_jx_j<W$, where $x_j$ are non-negative integers.
The problem is to maximize total weight of the items choosen: $\sum_{j=1..n}w_jx_j$.
This problem is a special case of Strongly Correlated Unbounded Knapsack Problem, where one should maximize total value $\sum_{j=1..n}p_jx_j$, and the values are linear functions of the weights: $p_j=kw_j+c$. It is also similar to the Subset Sum Problem, with the only difference that in SSP each item can be taken not more than one time: $x_j$ is either 0 or 1.
Both SCUKP ans SSP are NP-complete, but unlike them the problem that I need to solve looks to have exact polynomial-time solution, probably something based on the Euclidean algorithm.
Please help me solve it if you have any idea.
Best Answer
The problem described is exactly the unbounded subset sum problem. For the proof of NP-completeness of the decision variant as well for the algorithm designed especially for the unbounded subset sum problem see