Knapsack Problem
suggest change0-1 Knapsack
The Knapsack Problem is a problem when given a set of items, each with a weight, a value and exactly 1 copy, determine the which item(s) to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
C++ Example:
Implementation:
int knapsack(vector<int> &value, vector<int> &weight, int N, int C){ int dp[C+1]; for (int i = 1; i <= C; ++i){ dp[i] = -100000000; } dp[0] = 0; for (int i = 0; i < N; ++i){ for (int j = C; j >= weight[i]; --j){ dp[j] = max(dp[j],dp[j-weight[i]]+value[i]); } } return dp[C]; }
Test:
3 5 5 2 2 1 3 2
Output:
3
That means the maximum value can be achieved is 3, which is achieved by choosing (2,1) and (3,2).
Unbounded Knapsack
The Unbounded Knapsack Problem is a problem which given a set of items, each with a weight, a value and infinite copies, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Python(2.7.11) Example:
Implementation:
def unbounded_knapsack(w, v, c): # weight, value and capactiy m = [0] for r in range(1, c+1): val = m[r-1] for i, wi in enumerate(w): if wi > r: continue val = max(val, v[i] + m[r-wi]) m.append(val) return m[c] # return the maximum value can be achieved
The complexity of that implementation is O(nC)
, which n is number of items.
Test:
w = [2, 3, 4, 5, 6] v = [2, 4, 6, 8, 9] print unbounded_knapsack(w, v, 13)
Output:
20
That means the maximum value can be achieved is 20, which is achieved by choosing (5, 8), (5, 8) and (3, 4).