<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Knapsack
In this programming problem and the next you'll code up the knapsack algorithm from lecture.
Let's start with a warm-up using file knapsack1.txt
This file describes a knapsack instance, and it has the following format
Step1:  Problem 2
This problem also asks you to solve a knapsack instance, but a much bigger one.
Use the text file below knapsack_big.txt
This file describes a knapsack instance, and it has the following format
Step2:  A recursive Implementation of the knapsack algorithm with caching
<ASSISTANT_TASK:>
Python Code:
import numpy as np
file = "knapsack1.txt"
fp = open(file, 'r+')
data = fp.readlines()
W, n = data[0].split(" ")
W, n = int(W), int(n)
v = []
w = []
for r in data[1:]:
    v_i, w_i = r.split(" ")
    v.append(int(v_i))
    w.append(int(w_i))
A = np.zeros([n, W+1])
for i in range(n):
    for x in range(W+1):
        if x >= w[i]:
            A[i,x]= max(A[i-1,x], A[i-1,x-w[i]]+v[i])
        else:
            A[i,x]= A[i-1,x]
print (A)
        
Explanation: Knapsack
In this programming problem and the next you'll code up the knapsack algorithm from lecture.
Let's start with a warm-up using file 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!
End of explanation
file = "knapsack_big.txt"
fp = open(file, 'r+')
data = fp.readlines()
W, n = data[0].split(" ")
W, n = int(W), int(n)
v = []
w = []
for r in data[1:]:
    v_i, w_i = r.split(" ")
    v.append(int(v_i))
    w.append(int(w_i))
Explanation: Problem 2
This problem also asks you to solve a knapsack instance, but a much bigger one.
Use the text file below knapsack_big.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 834558", indicating that the second item has value 50074 and size 834558, respectively. As before, you should assume that item weights and the knapsack capacity are integers.
This instance is so big that the straightforward iterative implemetation uses an infeasible amount of time and space. So you will have to be creative to compute an optimal solution. One idea is to go back to a recursive implementation, solving subproblems --- and, of course, caching the results to avoid redundant work --- only on an "as needed" basis. Also, be sure to think about appropriate data structures for storing and looking up solutions to subproblems.
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!
End of explanation
import sys
sys.setrecursionlimit(2500)
cache = dict()
def knap(i, _w):
#     print (i, _w)
    key = str(i)+"-"+str(_w)
    if i == 0:
        cache[key] = 0
        return 0
    
    if _w > w[i]:
        key1 = str(i-1)+"-"+str(_w - w[i])
        key2 = str(i-1)+"-"+str(_w)
        
        if key1 in cache and key2 in cache:
            a1 = cache[key1]
            a2 = cache[key2]
            cache[key] = max(v[i]+a1, a2)
        elif key1 in cache:
            a1 = cache[key1]
            cache[key] = max(v[i]+a1, knap(i-1, _w))
        elif key2 in cache:
            a2 = cache[key2]
            cache[key] = max(v[i]+knap(i-1,_w-w[i]), a2)
        else:
            cache[key] = max(v[i]+knap(i-1,_w-w[i]), knap(i-1, _w))
    else:
        key2 = str(i-1)+"-"+str(_w)
        if key2 in cache:
            cache[key] = cache[key2]
        else:
            cache[key] = knap(i-1,_w)
            
    return cache[key]
knap(n-1,W)
print (cache[str(n-1)+"-"+str(W)])
Explanation: A recursive Implementation of the knapsack algorithm with caching
End of explanation
<END_TASK>