# 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] = 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).