0/1 Knapsack (Dynamic Programming)

knapSack.cpp

// Iteration
int knapSack(int v[], int w[], int n, int W) //Values, Weights, Number of distinct item, Knapsack capacity
{
    // T[i][j] stores the maximum value that can be attained with
    // weight less than or equal to j using items up to first i items
    int T[n+1][W+1];
    for (int j = 0; j <= W; j++)
        T[0][j] = 0;
    // or memset (T[0], 0, sizeof T[0]);

    // do for ith item
    for (int i = 1; i <= n; i++)
    {
        // consider all weights from 0 to maximum capacity W
        for (int j = 0; j <= W; j++)
        {
            // don't include ith element if j-w[i-1] is negative
            if (w[i-1] > j)
                T[i][j] = T[i-1][j];
            else
            // find max value by excluding or including the ith item
                T[i][j] = max(T[i-1][j],
                            T[i-1][j-w[i-1]] + v[i-1]);
        }
    }
    return T[n][W];
}

// Recursion
int knapSack(int v[], int w[], int n, int W)  
{  
    if (n == 0 || W == 0)  
        return 0;  
      
    // If weight of the nth item is more  
    // than Knapsack capacity W, then  
    // this item cannot be included 
    // in the optimal solution  
    if (w[n-1] > W)  
        return knapSack(v, w, n-1, W);  
      
    // Return the maximum of two cases:  
    // (1) nth item included  
    // (2) not included  
    else return max( v[n-1] + knapSack(v, w, n-1, W-w[n-1]),  
                    knapSack(v, w, n-1, W) );  
}