Knapsack

During a robbery, a burglar finds much more loot than he had expected and has to decide what to take. His bag (or “knapsack”) will hold a total weight of at most W pounds. There are n items to pick from, of weight w1...wn and dollar value v1...vn. What's the most valuable combination of items he can t into his bag?

There are two versions of this problem: 

1: Unlimited quantities of each item available

2: Only one of each item

1: Knapsack with repetition:

K(w) = maximum value achievable with a knapsack of capacity w

Can we express this in terms of smaller sub-problems? Well, if the optimal solution to K(w) includes item i, then removing this item from the knapsack leaves an optimal solution to K(w - wi). In other words, K(w) is simply K(w - wi) + vi, for some i. We don't know which i, so we need to try all possibilities:

Implementation:

int maxWeight(int *weights, int *values, int *K, int n, int w)
{
    int max = 0;
    for(int i = 0; i < n; ++i)
    {
            if(weights[i] <= w)
            {
                          int val = K[w-weights[i]] + values[i];
                          if(max < val)
                                 max = val;
            }
    }
    return max;
}

int knapsackWithRepetition(int *weights, int *values, int n, int W)
{
    int *K = new int[W + 1];
    K[0] = 0;
    for(int w = 1; w <= W; ++w)
    {
            K[w] = maxWeight(weights, values, K, n, w);
    }
    return K[W];
}

Time Complexity: O(nW)


2: Knapsack without Repetition:

K(w, j) = maximum value achievable using a knapsack of capacity w and items 1...j

Implementation:

int knapsackWithoutRepetition(int *weights, int *values, int n, int W)

{

    int **K = new int*[W + 1];

    for(int w = 0; w <= W; ++w)

    {

            K[w] = new int[n + 1];

            K[w][0] = 0;

    }

    for(int i = 0; i <= n; ++i)

            K[0][i] = 0;

    

    for(int i = 1; i <= n; ++i)

    {

            for(int w = 1; w <= W; ++w)

            {

                    if(weights[i-1] > w)

                                  K[w][i] = K[w][i - 1];

                    else

                        K[w][i] = MAX(K[w][i-1], K[w-weights[i-1]][i-1] + values[i-1]);

            }

    }

    return K[W][n];

}

Time Complexity: O(nW)