Knapsack Problem

The term knapsack refers to problems where a set of objects is given, and subsets with some properties have to be found. Knapsack problems can often be solved using dynamic programming.

Bottom-Up Knapsack (Iterative) in

When we do bottom-up dp, we do it in Topological Order.

int wt[n]; // Weights
int val[n]; // Value
int W; // Our capacity is given by W
int dp[n+1][W+1]; // We have n+1 because we want to be able to choose or NOT choose item (n-1), and our update is one step ahead
cin >> wt[i] // for 0...n-1
 
for (int i=0;i<=n;i++) {
	for (int w=0;w<=W;w++) {
		if (i == 0 || w == 0) {
			dp[i][w] = 0;
		} else if (w - wt[i] >= 0) {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1]);
		} else {
            dp[i][j] = dp[i-1][j];
		}
	}
}
 
cout << dp[n][W] << endl; // Answer

Note: The example above uses 0-indexing. If you use 1=indexing, you should use wt[i] instead of wt[i-1]; Notice I use for example wt[i-1], and when we cin >> wt[i] its from 0...n-1. If you choose to do the update with wt[i], make sure to cin 1...n, and then the update is for wt[i].

Optimized space. We need to go from W...0 because else the weights are going to be in different sizes.

// making and initializing dp array
int dp[W + 1];
memset(dp, 0, sizeof(dp));
 
for (int i = 1; i < n + 1; i++) {
	for (int w = W; w >= 0; w--) {
		if (wt[i - 1] <= w) {
			// finding the maximum value
			dp[w] = max(dp[w], dp[w - wt[i - 1]] + val[i - 1]);
		}
	}
}
return dp[W]; // returning the maximum value of knapsack

Other Example

Given a list of weights , determine all sums that can be constructed using the weights.

We can recursively calculate this using the recurrence

possible[0][0] = true;
for (int k = 1; k <= n; k++) {
	for (int x = 0; x <= W; x++) {
		if (x-w[k] >= 0) possible[x][k] |= possible[x-w[k]][k-1];
		possible[x][k] |= possible[x][k-1];
	}
}

However, here is a better implementation that only uses a one-dimensional array possible[x] that indicates whether we can construct a subset with sum x.

The trick is to update the array from right to left for each new weight:

possible[0] = true;
for (int k = 1; k <= n; k++) {
	for (int x = W; x >= 0; x--) {
		if (possible[x]) possible[x+w[k]] = true;
	}
}