Suppose $X$ is a set of integers. I am interested in the algorithm which computes the number of ways to represent an integer $W$ as a sum of exactly $k$ elements from $X$. Is it possible to modify the standard knapsack algorithm so that it does the job? Thank you for your suggestions!

  • 2
    $\begingroup$ The best answer to a question of the form "is it possible" is "give it a try"! $\endgroup$ – Yuval Filmus Jun 8 '17 at 5:46
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W. Jun 8 '17 at 18:29
  • $\begingroup$ Hint: How are the following two problems related? Problem 1: $X_1=\{3, 4, 8, 9\}, W_1=13$. Problem 2: $X_2=\{1003, 1004, 1008, 1009\}, W_2 = 2013$. $\endgroup$ – j_random_hacker Apr 4 '18 at 9:38

Iterative solution (recursive is very similar too):

Have a 2d array $mat[W][k]$ and let the columns be $0..k$ and the rows be from $0..W$. Let $mat[x][y] = 0 \;\forall \;0\le x \le W, 0\le y \le k$. Let $mat[0][0] = 1$.

Now run $i$ across $[1,k]$. Within the $i$ loop run another loop iterating $j$ across $[1,W]$. In every iteration of the inner loop, run through the set of elements and calculate this:

$${mat[i][j] = \sum_{l=1}^{|X|} mat[i-1][j-X_l] }\:$$

$mat[W][k]$ will store the final answer. Time complexity = $\mathcal{O}(W.k.|X|)$, and space complexity = $\mathcal{O}(W.k)$.

  • $\begingroup$ I'm trying to understand your algorithm. $j-X_l$ may be negative? $\endgroup$ – Albert Hendriks Jan 4 '18 at 9:31
  • $\begingroup$ What does $mat[i][j]$ represent? It can't be a boolean value indicating whether it's possible to get a weight of exactly $i$ by using exactly $j$ items, since it can be greater that one (also I would expect to see a $\max$ somewhere). Separately, you seem to be allowing repeated use of an item (admittedly the OP is not clear on whether this is permitted). $\endgroup$ – j_random_hacker Apr 4 '18 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.