algorithm Dynamic Programming Knapsack Problem
Example
0-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).
