Sunday, February 22, 2015

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)

1 comment:

  1. there are question that just like knapsak problem but the constrain is different. say that a series bus stations position from one point probablity distance is in increasing order d1,d2,d3,,,,dn, their profit is p1,p2,p3,,,,,pn, we want to maximize the total profit.the constraint is two point distance is at least K.
    could you help me about this problem? thank you

    ReplyDelete