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!
3
-
2$\begingroup$ The best answer to a question of the form "is it possible" is "give it a try"! $\endgroup$– Yuval FilmusCommented Jun 8, 2017 at 5:46
-
$\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$– D.W. ♦Commented Jun 8, 2017 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_hackerCommented Apr 4, 2018 at 9:38
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$ Commented Jan 4, 2018 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$ Commented Apr 4, 2018 at 9:47