*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.

**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.

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

This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0

This website is not affiliated with Stack Overflow