Dynamic Programming

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 $O(n^2)$

How to think of the problem

Think of it like a bag of coins, where each coin has a weight, but each coin also has value ($1,$2, etc). You want to maximize the bag’s value while staying within the constraints of the weight.

Resources

• https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

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

In CS341, we saw a 1-indexed version, which to me is more intuitive

• In the example above, we use 1-indexed for dp, but 0-indexed for the actual values, which makes it super confusing
• So in general, just use 1-indexed for both the DP and the values!!
• Use the 0-th index as the base case
  • https://leetcode.com/problems/edit-distance/submissions/1233333790/
• The issue is that arrays are generally 0-indexed if they already give it to you, which makes it kind of annoying

more generally

I find that 1-indexed is easier, due to setting up the base case at i==0.

1-indexed solution

int wt[n+1]; // Weights
int val[n+1]; // 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 (i), and our update is one step ahead
cin >> wt[i] // for 1...n
 
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][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i]);
		} else {
            dp[i][w] = dp[i-1][w];
		}
	}
}
 
cout << dp[n][W] << endl; // Answer

0-indexed

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-1] >= 0) {
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i-1]] + val[i-1]);
		} else {
            dp[i][w] = dp[i-1][w];
		}
	}
}
 
cout << dp[n][W] << endl; // Answer

• The example above uses 0-indexing. If you use 1=indexing, you should use wt[i] instead of wt[i-1], and val[i] instead of val[i-1]

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 $[w_1,w_2,...,w_n]$, determine all sums that can be constructed using the weights.

We can recursively calculate this using the recurrence $dp(x,k)=dp(x-w_k,k-1)\vee dp(x,k-1)$

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;
	}
}