# Knapsack problem with the restriction on the number of items

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!

• The best answer to a question of the form "is it possible" is "give it a try"! – Yuval Filmus Jun 8 '17 at 5:46
• cs.stackexchange.com/tags/dynamic-programming/info – D.W. Jun 8 '17 at 18:29
• 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$. – j_random_hacker Apr 4 '18 at 9:38

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)$.
• I'm trying to understand your algorithm. $j-X_l$ may be negative? – Albert Hendriks Jan 4 '18 at 9:31
• 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). – j_random_hacker Apr 4 '18 at 9:47