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$ 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$ 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$ 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$ 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.