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/

Some more advanced versions

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

Definition

dp[i][w] = maximum value using the first i items, i.e. items with indices 0 .. i-1, with capacity w.

• This formula makes the base case code clean

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

Forward propagation

int dp[n+1][W+1]; // initially all zeros
for (int i = 0; i < n; i++) {
    for (int w = 0; w <= W; w++) {
        dp[i + 1][w] = max(dp[i + 1][w], dp[i][w]); // Do not take the item
        if (w + wt[i] <= W) { // Take the item (if it fits)
            dp[i + 1][w + wt[i]] = max(dp[i + 1][w + wt[i]], dp[i][w] + val[i]);
        }
    }
}
// The maximum value is in dp[n][W]
return dp[n][W];

I didn't do this in a long time and forgot the order to iterate through i first, then w...

Though it doesn’t matter. It matters for 1D DP.

When to choose between forward and backward propagation?

Forward: dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i-1]] + val[i-1]);

Backward:

 from (i, w):
  dp[i+1][w]       = max(dp[i+1][w], dp[i][w]);              // skip
  dp[i+1][w+wt[i]] = max(dp[i+1][w+wt[i]], dp[i][w]+val[i]); // take

You need to visualize a dp table

Optimized space. We need to go from W...0 because if we do 0...W, we are going to overwrite the weight value, and double count the usage of item i.

// 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:

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

Tree Knapsack

Tree Knapsack

• https://leetcode.com/problems/maximum-profit-from-trading-stocks-with-discounts/?envType=daily-question&envId=2025-12-16
  • holy crap this was hard for me