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

Question

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.

Answer 1

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.

---

Note: Constructing dp table might not be of any use to you.