# Knapsack Problem

suggest change**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).