The Knapsack algorithm

knapsack.cpp

/* The classic knapsack problem, solved with
 * dynamic programming. In the dp array,
 * rows represent item subset choice, columns
 * represent weights, and individual cells represent
 * values. The knapsack algorithm can also be adapted
 * to searching subsets for a target value. Just set
 * weights equal to values, and one can then search subsets
 * for a value.
 *
 * If there are n values, and the target value is t, then
 * both space and time complexity is O(n*t)
 */

#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;


int knapSack(int knapSackSize, const vector<int> weights, const vector<int> values) {
    int dp[weights.size()+1][knapSackSize+1];
    memset(dp, 0, sizeof(dp));

    for (int i=1; i <= weights.size(); i++) {
        for (int j=0; j <= knapSackSize; j++) {
            if (j >= weights[i-1]) {
                //If the weight of the current cell is greater than or equal to
                //a weight we are considering, then calculate what the greater of
                //picking this item (values[i-1] + dp[i-1][j-weights[i-1]) or
                //ignoring it (dp[i-1][j]);
                dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j-weights[i-1]]);
            } else {
                //The weight we are considering is less than the current item,
                //so ignore the current item (by choosing the cell above)
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    return dp[weights.size()][knapSackSize];
}