# How to derive max amount of items from DP table of Knapsack problem?

I have a little bit changed algorithm for 1-0 Knapsack problem. It calculates max count (which we can put to the knapsack) as well. I'm using it to find max subset sum which <= target sum. For example:

weights: 1, 3, 4, 5, target sum: 10
result: 1, 4, 5 (because 1 + 4 + 5 = 10)

weights: 2, 3, 4, 9 target sum: 10
result: 2, 3, 4 (2 + 3 + 4 = 9, max possible sum <= 10)


I use 2 DP tables: one for calculating max possible sum (dp) and one for max possible amount (count).

The question is: how I can derive chosen values from the both tables?

Example:

weights: [3, 2, 5, 2, 1, 1, 3], target_sum: 10
indexes:  0, 1, 2, 3, 4, 5, 6

dp:
0: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1: [0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 3]
2: [0, 0, 2, 3, 3, 5, 5, 5, 5, 5, 5]
3: [0, 0, 2, 3, 3, 5, 5, 7, 8, 8, 10]
4: [0, 0, 2, 3, 4, 5, 5, 7, 8, 9, 10]
5: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
6: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
7: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

count:
0: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
2: [0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2]
3: [0, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3]
4: [0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4]
5: [0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5]
6: [0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5]
7: [0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5]


Here, items with weight [3, 2, 1, 3, 1] should be derived (because they have max possible count) instead of (for example) [5, 2, 3].

Some notation explanations:
dp means the same as in original Knapsack problem: i - for the items, j for the weight. The value in the dp[i][j] mean the sum of chosen items (weights) which have sum <= j.

Each cell in the count corresponds to dp and shows max possible amount of items (with total weight = dp[i][j])

How chosen items could be derived efficiently?

I know how to derive just any items from the dp (e.g. not the max amount of them) by reconstructing it from the bottom-right cell. Also, I've found a hack which allows to derive the items if input is sorted. But I'm looking for the way which allows to do that without soring. Is it's possible?

The code which constructs these two tables doesn't matter much, but here it is:

def max_subset_sum(ws, target_sum):
n = len(ws)
k = target_sum

dp = [[0] * (k + 1) for _ in range(n + 1)]
count = [[0] * (k + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
for j in range(1, k + 1):
curr_w = ws[i - 1]
if curr_w > j:
dp[i][j] = dp[i - 1][j]
count[i][j] = count[i - 1][j]
else:
tmp = round(dp[i - 1][j - curr_w] + curr_w, 2)
if tmp >= dp[i - 1][j]:
dp[i][j] = tmp
count[i][j] = count[i - 1][j - curr_w] + 1
else:
dp[i][j] = dp[i - 1][j]
count[i][j] = count[i - 1][j]

return get_items(dp, k, n, ws)

def get_items(dp, k, n, ws):
# The trick which allows to get max amount of items if input is sorted
start = n
while start and dp[start][k] == dp[start - 1][k]:
start -= 1

res = []
w = dp[start][k]
i, j = start, k
while i and w:
if w != dp[i - 1][j]:
res.append(i - 1)
w = round(w - ws[i - 1], 2)
j -= ws[i - 1]
i -= 1

return res


Also, I have weird attempt to get max amount of items. But it's produces incorrect result which sums to 9: [3, 1, 1, 2, 2]

def get_items_incorrect(dp, count, k, n, ws):
start = n

res = []
w = dp[start][k]
i, j = start, k
while i and w:
# while dp[i][j] < ws[i - 1]:
#     i -= 1
while ws[i - 1] > j:
i -= 1
if i < 0:
break

max_count = count[i][j]
max_count_i = i

while i and w == dp[i - 1][j]:
if count[i - 1][j] > max_count:
max_count = count[i - 1][j]
max_count_i = i - 1
i -= 1

res.append(max_count_i - 1)
w = round(w - ws[max_count_i - 1], 2)
j -= ws[max_count_i - 1]

i = max_count_i - 1

return res


Sorry for the long read and thank you for any help!

UPDATE 04/14/2021

I found an error in generating count table: it will generate the same as in this post if the input is sorted. If input isn't sorted it will contains not max count. Will try to fix it.

• Pseudocode would be much readable and understandable than the python one. – Inuyasha Yagami Apr 11 at 14:29
• @inuyasha-yagami python so simple that it's itself pseudocode, IMO – Nikita Apr 11 at 15:17
• I can google a few things online. But why not make the question self contained and less time consuming for a general audience? :-) – Inuyasha Yagami Apr 11 at 16:05
• @inuyasha-yagami In pseudocode dp[i][j] or count[i][j] would be the same. Hence it may be non obvious for someone as well. BTW, dp mean the same as in any other DP problem, more specifically it's the same as in Knapsack problem. The main question is how to get the answer (with max amount) from that dp table. How to do that dp doesn't matter much. I will edit question so that it will more clear – Nikita Apr 12 at 7:23
• @Inuyasha Yep, exactly. But the sum should be maximum possible and less than or equal to target sum. – Nikita Apr 14 at 13:29

There are many ways to do this. One way is that you can create another table $$T$$ of size $$7$$ x $$10$$ such that entry $$T[i][j] = 1$$ if item $$i$$ is picked in the optimal solution of sum $$\leq j$$; otherwise $$T[i][j] = 0$$. You can create this table while filling entries for count and dp tables.
Now, to derive the chosen items that have maximum count, you start from the bottom-right cell, i.e., $$T[7][10]$$.
• If $$T[7][10] = 1$$, means you picked $$7^{th}$$ item. Suppose the weight of $$7^{th}$$ item is $$w$$. To get the next item, you now move to entry $$T[6][10-w]$$...and so on.
• On the other hand, if $$T[7][10] = 0$$, you simply move to $$T[6][10]$$ since $$7^{th}$$ was not picked. You can proceed likewise.
• @Nikita I have a problem with your count matrix. In entry [6,9] shouldn't it be 5? Since there are items $3,2,2,1,1$ that sums to $9$ – Inuyasha Yagami Apr 14 at 13:59