knapsack1.ipynb

Kernel: Python [conda env:DAND]

Knapsack Algorithm

1 point 1.In this programming problem and the next you'll code up the knapsack algorithm from lecture.

Let's start with a warm-up. Download the text file below.

knapsack1.txt This file describes a knapsack instance, and it has the following format:

[knapsack_size][number_of_items]

[value_1] [weight_1]

[value_2] [weight_2]

...

For example, the third line of the file is "50074 659", indicating that the second item has value 50074 and size 659, respectively.

You can assume that all numbers are positive. You should assume that item weights and the knapsack capacity are integers.

In the box below, type in the value of the optimal solution.

ADVICE: If you're not getting the correct answer, try debugging your algorithm using some small test cases. And then post them to the discussion forum!

import numpy as np

# get the file path
file_path = 'knapsack1.txt'
# file_path = 'test 1.txt'
# convert text file to np.array type
knapsack1_data = np.loadtxt(file_path)
int_knapsack1_data = knapsack1_data.astype(int)

knapsack_size = 10000
items = 100

%%timeit
def Knapsack(int_knapsack1_data, items, knapsack_size):
    A = np.zeros(shape=(items+1,knapsack_size+1))
    for i in range(1,items+1):
        for x in range(knapsack_size+1):
            if int_knapsack1_data[i-1][1] > x:
                A[i][x] = A[i-1][x]
            else:
                A[i][x] = max(A[i-1][x],A[i-1][x-int_knapsack1_data[i-1][1]]+int_knapsack1_data[i-1][0])
    return A[items][knapsack_size]

10000000 loops, best of 3: 104 ns per loop

%%timeit
print(Knapsack(int_knapsack1_data, items, knapsack_size))

2493893.0
2493893.0
2493893.0
2493893.0
1 loop, best of 3: 3.35 s per loop

%%timeit
def Knapsack_simplify1(int_knapsack1_data, items, knapsack_size):
    A = np.zeros(shape=(2,knapsack_size+1))
    for i in range(1,items+1):
        #print(A)
        for x in range(knapsack_size+1):
            if int_knapsack1_data[i-1][1] > x:
                A[1][x] = A[0][x]
            else:
                A[1][x] = max(A[0][x],A[0][x-int_knapsack1_data[i-1][1]]+int_knapsack1_data[i-1][0])
        
        A[0] = A[1]        
        A[1] = np.zeros(shape=(1,knapsack_size+1))
    return A[0][knapsack_size]

10000000 loops, best of 3: 97.3 ns per loop

%%timeit
print(Knapsack_simplify1(int_knapsack1_data, items, knapsack_size))

2493893.0
2493893.0
2493893.0
2493893.0
1 loop, best of 3: 3.37 s per loop

Question 1 Answer:

2493893