0
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ Pseudocode would be much readable and understandable than the python one. $\endgroup$ Apr 11 at 14:29
  • $\begingroup$ @inuyasha-yagami python so simple that it's itself pseudocode, IMO $\endgroup$
    – Nikita
    Apr 11 at 15:17
  • 2
    $\begingroup$ I can google a few things online. But why not make the question self contained and less time consuming for a general audience? :-) $\endgroup$ Apr 11 at 16:05
  • $\begingroup$ @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 $\endgroup$
    – Nikita
    Apr 12 at 7:23
  • 1
    $\begingroup$ @Inuyasha Yep, exactly. But the sum should be maximum possible and less than or equal to target sum. $\endgroup$
    – Nikita
    Apr 14 at 13:29
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Unfortunately, it doesn't work -- it returns just any suitable weights (not the max count of them). If you want I can try to the share code somehow. $\endgroup$
    – Nikita
    Apr 14 at 13:57
  • $\begingroup$ @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$ $\endgroup$ Apr 14 at 13:59
  • $\begingroup$ Yes, you're right! I've regenerated the table and looks like there an error/typo in the question post. Moreover, I found that correct count table is generating if input is sorted... If it's not sorted - it contains non-max count values :( I will update the question post. Thank you! $\endgroup$
    – Nikita
    Apr 14 at 19:27

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.