Knapsack without repetitions: Maximum Amount of Gold - Python code question

user_14594287 0
Viewed 1349

From Coursera's Algorithmic Toolbox course.

Problem Introduction

You are given a set of bars of gold and your goal is to take as much gold as possible into your bag. There is just one copy of each bar and for each bar you can either take it or not (hence you cannot take a fraction of a bar).

Problem Description

Task. Given gold bars, find the maximum weight of gold that fits into a bag of capacity . Input Format. The first line of the input contains the capacity of a knapsack and the number of bars of gold. The next line contains integers 0,1, . . . ,−1 defining the weights of the bars of gold.

Constraints. 1 ≤ ≤ 10^4; 1 ≤ ≤ 300; 0 ≤ 0, . . . , −1 ≤ 10^5.

Output Format. Output the maximum weight of gold that fits into a knapsack of capacity .

My solution in Python using dynamic programming:

def optimal_weight(W, w):

    golds = [0] + w
    gold_dict = {}
    for i in range(0, W+1):
        gold_dict[(i, golds[0])] = 0
    for i in golds:
        gold_dict[(0, i)] = 0

    for i in range(1, len(golds)):
        for weight in range(1, W+1):
            gold_dict[(weight, golds[i])] = gold_dict[(weight, golds[i-1])]
            if golds[i] <= weight:
                val = gold_dict[(weight-golds[i], golds[i-1])] + golds[i]
                if gold_dict[(weight, golds[i])] < val:
                    gold_dict[(weight, golds[i])] = val

    return max(gold_dict.values())

The second input would be a list of gold bars with their weight as integer. For the input of:

10, [1, 4, 8]

The result should be an integer 9 (which is 1+8).

I have tested a list of examples including some extreme value such as:

1, [0]

And for all of them, the result seems to be right. However, the final test is keeping showing one of the tests is not passed due to the wrong answer. Hence there must be a bug within my code. Yet I am having difficulty locating it. (the assignment test would not release testing parameters, hence I could not get the input that triggers the wrong answer)

Could someone please advise what is the potential issue? Even a hint would be really appreciated. Thanks a lot.

Edit:

I have added the main function to show how input was read, though I do not think that links to the potential bug:

if __name__ == '__main__':
    input = sys.stdin.read()
    W, n, *w = list(map(int, input.split()))
    print(optimal_weight(W, w))

The sys.stdin will read a testing txt file with example input as follows:

10 3
1 4 8

Which means a bag capacity of 10, 3 gold bars, weight for 1, 4, 8 each.

The main method comes with the question and is not modified.

Edit2 Answer:

Thanks for Arty's advice below, the issue came from the use of gold[i] as part of the tuple key for gold_dict. If there are multiple gold bars that have the same weight, their index in the gold[] list will be different (different i) but their gold[i] value will be the same. In such a condition, the tuple key (weight, gold[i]) will potentially be referring to the wrong object.

I have done a random test on Arty's correct code with my wrong one to find the parameters that could trigger the bug, which shows up after ~3000 runs:

209 38
16, 21, 21, 96, 129, 144, 159, 253, 254, 259, 259, 267, 285, 290, 304, 351, 351, 383, 411, 429, 493, 494, 527, 530, 534, 596, 619, 625, 692, 717, 727, 727, 745, 772, 833, 853, 856, 946

For this example, my code will get an answer 208 while the correct answer is 202.

Fix is very simple actually, just change gold[i] to i for all key tuples:

def optimal_weight(W, w):

    golds = [0] + w
    gold_dict = {}
    for i in range(0, W+1):
        gold_dict[(i, 0)] = 0
    for i in range(0, len(golds)):
        gold_dict[(0, i)] = 0
    for i in range(1, len(golds)):
        for weight in range(1, W+1):
            gold_dict[(weight, i)] = gold_dict[(weight, (i-1))]
            if golds[i] <= weight:
                val = gold_dict[(weight-golds[i], i-1)] + golds[i]
                if gold_dict[(weight, i)] < val:
                    gold_dict[(weight, i)] = val
    return max(gold_dict.values())
knapsack-problem python
1 Answers

I implemented my own solution using array of bools d, element d[i][j] is True if and only if weight j can be composed in some way by taking/not-taking golds with indexes 0 to i. We start from row that contains True only for j = 0 i.e. weight 0 can be composed by not taking anything. Each next row is computed as follows - element d[i][j] is True if d[i - 1][j] is True (which corresponds to not taking current gold) or if d[i - 1][j - golds[i]] is True (which corresponds to taking current gold).

Regarding your solution. I'll suggest to do next correction in your algorithm, keys of dict gold_dict should have second element equal to index of gold bar, not the value of gold bar, i.e. instead of gold_dict[(weight, gold[i])] you need to use everywhere gold_dict[(weight, i)], try doing this correction and maybe your code will work for all tests! Your corrected with this suggestion code is here.

My solution code is down below:

Try it online!

def optimal_weight(W, golds):
    # We can compose weight 0 by taking nothing
    d = [[True] + [False] * W]
    for i in range(len(golds)):
        # We copy previous row which corresponds to
        # solution of not taking current gold
        d.append(d[-1][:])
        for w in range(golds[i], W + 1):
            # Weight w can be composed either by not taking current
            # gold (d[-2][w]) or by taking it (d[-2][w - golds[i]])
            d[-1][w] = d[-2][w] or d[-2][w - golds[i]]
        # It is enough to keep only last row
        d = d[-1:]
    for w in range(W, -1, -1):
        # Return maximal weight w that has True in d
        if d[-1][w]:
            return w
    
if __name__ == '__main__':
    import sys
    W, n, *w = list(map(int, sys.stdin.read().split()))
    print(optimal_weight(W, w))

Input:

10 3
1 4 8

Output:

9
user_9415310
Related