CODEWITHSUNDEEP
algorithmdynamic-programmingknapsack-problem
Nikita
Nikita

Reputation: 194

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, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
2: [0, 0, 1, 1, 1, 2, 2, 2, 2, 2, 2]
3: [0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3]
4: [0, 0, 1, 1, 2, 2, 2, 2, 2, 3, 3]
5: [0, 1, 1, 2, 2, 3, 3, 2, 3, 3, 4]
6: [0, 1, 2, 2, 3, 3, 4, 4, 3, 4, 4]
7: [0, 1, 2, 1, 2, 3, 3, 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!

Upvotes: 0

Views: 210

Answers (1)

MBo
MBo

Reputation: 80197

Seems you have overcomplicated the problem. This kind of problem (without item cost) might be solved using 1D list. Weights for the best cases are stored in parallel list.

After table filling we look for the largest occupied index (largest possible sum <= target) and unwind used items chain.

def sol(wts, target):
    dp = [-1] * (target + 1)
    dp[0] = 0
    items = [0] * (target + 1)
    wts.sort()

    for w in weights:
        for i in range(target, w-1, -1):
            if (dp[i-w] >= 0) and (dp[i-w] > dp[i]):
                dp[i] = dp[i-w] + 1
                items[i] = w

    last = target
    while (last) and  (dp[last] < 0):
        last -= 1

    best = dp[last]
    res = []
    while (last):
        res.append(items[last])
        last -= items[last]

    return(best, res)

weights = [1, 2, 3, 3, 5, 2, 1]
target_sum = 9
print(sol(weights, target_sum))

Upvotes: 1

Related Questions