1

I am currently a bit stumped on a programming assignment - as I am required to follow the structure of a specific piece of pseudo-code to solve the problem. I am also a relatively inexperienced programmer; sorry if this problem is an easy fix.

If you are not familiar with the knapsack problem, the code takes a list (items), which contains an item name, the weight of the item, and the value of the item. It should then create and output a list of the lowest-weight and highest-value items which are <= the maximum weight (W)

The pseudo-code to follow:

function dpKnapsack(items, W):
    n = len(items)
    T = new int[n][W+1]
    for i in 0..n:     //[0, n-1]
        T[i][0] = 0    // weight == 0
    for j in 1..W+2:   // [0,W+1]
        if items[0].weight <= j:
            T[0][j] = items[0].value
    for i in 1..n:
        for j in 1..W+2:
            if items[i].weight <= j:
                T[i][j] = max(T[i-1][j], items[i].value + T[i][j-items[i].weight])
            else
                T[i][j] = T[i-1][j]
    return T[n-1][W]

My attempt towards translating it to python:

def dp_knapsack(items, W):
    n = len(items)
    T = [[0]*n, [0]*(W+1)]
    # items[0][0] = name of item 0
    # items[0][1] = weight of item 0
    # items[0][2] = value of items 0
    for i in range(0, n):
        T[i][0] = 0
    for j in range(1, (W+2)):
        if items[0][1] <= j:
            T[0][j] = items[0][2]
    for i in range(1, n):
        for j in range(1, (W+2)):
            if items[i][1] <= j:
                T[i][j] = max(T[i-1][j], items[i][2] + T[i][j-items[i][1]])
            else:
                T[i][j] = T[i-1][j]
    return T[n-1][W]

The code runs, however the list that it outputs goes (significantly) over the maximum weight.

Any and all help is appreciated, thanks!

Side note: the item list is a list of 100 items with randomly-generated weights and values. The list is generated in a function similar to this:

item_list = (
    # name      weight               value
    ("item_00", random.randint(100), random.randint(1000)),    
    ("item_01", random.randint(100), random.randint(1000)),
    ("item_02", random.randint(100), random.randint(1000)),   
    ("item_03", random.randint(100), random.randint(1000)),
    ("item_04", random.randint(100), random.randint(1000)),   
    ("item_05", random.randint(100), random.randint(1000)),
    # . . . etc 

)

Edit, the output I get when I print the returned list after running the program with a maximum weight of 50:

[('item_99', 6, 42), ('item_94', 3, 21), ('item_90', 42, 98), ('item_88', 42, 85), ('item_85', 19, 30), ('item_79', 1, 24), ('item_75', 33, 69), ('item_73', 8, 60), ('item_65', 31, 77), ('item_62', 61, 92), ('item_59', 17, 65), ('item_58', 50, 73), ('item_56', 37, 69), ('item_49', 9, 16), ('item_48', 1, 33), ('item_47', 25, 65), ('item_45', 15, 32), ('item_44', 9, 61), ('item_43', 54, 96), ('item_42', 9, 90), ('item_38', 59, 94), ('item_36', 2, 80), ('item_34', 43, 64), ('item_33', 6, 73), ('item_32', 8, 88), ('item_29', 21, 73), ('item_28', 67, 94), ('item_26', 40, 57), ('item_21', 11, 23), ('item_19', 30, 42), ('item_15', 4, 20), ('item_13', 22, 32), ('item_12', 14, 41), ('item_11', 20, 50), ('item_08', 65, 83), ('item_06', 16, 89), ('item_05', 72, 93), ('item_03', 17, 75), ('item_02', 10, 21)]
  • 1
    Is this really your code? This doesn't go over the weight limit, this crashes with an IndexError. The way you initialize `T` is wrong. You should be creating a `n*(W+1)` size array, but you're creating a `[n, W+1]` size array. – Aran-Fey Mar 15 '17 at 00:00
  • Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [Minimal, complete, verifiable example](http://stackoverflow.com/help/mcve) applies here. We cannot effectively help you until you post your MCVE code and accurately describe the problem. Specifically, assign constant items and show the invalid output you get. – Prune Mar 15 '17 at 00:01
  • You should also include a description or copy of your debugging attempts. From what you've posted, it appears that all you've done is to stare at the invalid output and your code until you gave up on that approach. Use a debugger. Put in some logic-tracing print statements. Find out where the beast goes over weight and ignores the limit. – Prune Mar 15 '17 at 00:03
  • @Rawing Yes. I edited and added the output. Doesn't crash for me. I am trying to create a multi-dimensional array, not an array of n*(W+1) size. –  Mar 15 '17 at 00:34
  • @patb You're creating a 2d array where the first row has size n and the 2nd row has size W+1, but you should be creating an array with n rows and W+1 columns. Your array only has 2 rows. Your code crashes whenever n is greater than 2. – Aran-Fey Mar 15 '17 at 00:38
  • http://stackoverflow.com/questions/2397141/how-to-initialize-a-two-dimensional-array-in-python Seems mostly a typo problem – pvg Mar 15 '17 at 00:42
  • `T = [[0]*n, [0]*(W+1)]` is not equivalent to `T = new int[n][W+1]`, so your code has to crash before you get to the end. – njzk2 Mar 15 '17 at 00:44

0 Answers0