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

Remarks

Dynamic Programming is an improvement on Brute Force, see this example (opens new window) to understand how one can obtain a Dynamic Programming solution from Brute Force.

A Dynamic Programming Solution has 2 main requirements:

Overlapping Subproblems means that results of smaller versions of the problem are reused multiple times in order to arrive at the solution to the original problem

Optimal Substructure means that there is a method of calculating a problem from its subproblems.

A Dynamic Programming Solution has 2 main components, the State and the Transition

The State refers to a subproblem of the original problem.

The Transition is the method to solve a problem based on its subproblems

The time taken by a Dynamic Programming Solution can be calculated as No. of States * Transition Time. Thus if a solution has N^2 states and the transition is O(N), then the solution would take roughly O(N^3) time.