# Knapsack Problem

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;
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 = 
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).