|
| 1 | +def read_data(data): |
| 2 | + weights = [] |
| 3 | + values = [] |
| 4 | + for d in data: |
| 5 | + weights.append(int(d.split()[1])) |
| 6 | + values.append(int(d.split()[0])) |
| 7 | + return (weights, values) |
| 8 | + |
| 9 | +def knapsack_rep(weights, values, W): |
| 10 | + """ knapsack with repetition """ |
| 11 | + k = [0]*(W + 1) |
| 12 | + for w in range(1, W+1): |
| 13 | + k[w] = max([k[w-i] + values[i] if weights[i]<=w else 0 for i in range(len(weights))]) |
| 14 | + return k[-1] |
| 15 | + |
| 16 | +def knapsack(weights, values, W): |
| 17 | + """ knapsack without repetition. Takes O(w) space |
| 18 | + Reference - http://books.google.co.in/books?id=u5DB7gck08YC&printsec=frontcover&dq=knapsack+problem&hl=en&sa=X&ei=1sbmUJSwDYWGrAeLi4GgCQ&ved=0CDUQ6AEwAA#v=onepage&q&f=true |
| 19 | + """ |
| 20 | + optimal_vals = [0]*(W+1) |
| 21 | + for j in range(0, len(weights)): |
| 22 | + for w in range(W, weights[j]-1, -1): |
| 23 | + if optimal_vals[w-weights[j]] + values[j] > optimal_vals[w]: |
| 24 | + optimal_vals[w] = optimal_vals[w-weights[j]] + values[j] |
| 25 | + return optimal_vals[-1] |
| 26 | + |
| 27 | +with open("kpdata2.txt") as f: |
| 28 | + (weights, values) = read_data(f) |
| 29 | +# print knapsack_rep(weights, values, 10000) |
| 30 | +#print knapsack(weights, values, 2000000) |
0 commit comments