4
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ This is also the Frobenius coin problem or postage stamp problem. Much literature exists on the web about this problem, and non trivial algorithms exist for the n=2 and n=3 case. In general, no solution better than dynamic programming exists to my knowledge. Gerhard "But There's Always Something New" Paseman, 2013.10.15 $\endgroup$ Oct 15, 2013 at 20:35
  • 3
    $\begingroup$ @GerhardPaseman, what do you mean by "This is also the Frobenius coin problem or postage stamp problem"? While the descriptions of these three problems are similar, I don't immediately see how they are equivalent. What are reductions between the above problem and the coin problem? $\endgroup$ Oct 16, 2013 at 9:54

2 Answers 2

3
$\begingroup$

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

Kellerer, Hans, Ulrich Pferschy, and David Pisinger. Knapsack problems. Springer, 2004.

$\endgroup$
0
$\begingroup$

According to Wikipedia, what have you have described appears to simply be the unbounded knapsack problem or the integer knapsack problem. It was apparently shown to be NP-complete by Lueker in the paper "Two NP-complete problems in nonnegative integer programming". Report No. 178, Computer Science Laboratory, Princeton.

$\endgroup$
1
  • $\begingroup$ The unbounded knapsack problem shown to be NP-complete by Lueker is to maximize $\sum_ip_ix_i$ subject to the condition $\sum_iw_ix_i<W$. Here, $w_i=p_i$, so the problem is much more restricted. $\endgroup$ Oct 16, 2013 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.