Learn Unbounded Knapsack — Free DSA Tutorial

Problem Idea

Unbounded knapsack changes one rule from the 0-1 version: each item type has no supply limit, so you're free to take the same item as many times as it fits — like buying stamps in any denomination as many times as you like.

Example: Problem Idea

#include <iostream>
using namespace std;
int main() {
	cout << "Unbounded knapsack: same item can be taken multiple times, like unlimited stamp denominations";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Unbounded knapsack: same item can be taken multiple times, like unlimited stamp denominations");
	}
}

print("Unbounded knapsack: same item can be taken multiple times, like unlimited stamp denominations")

#include <stdio.h>
int main() {
	printf("Unbounded knapsack: same item can be taken multiple times, like unlimited stamp denominations");
	return 0;
}

Difference from 0-1

The state and objective look the same as 0-1 knapsack, but because an item can be reused, considering item i doesn't remove it from future consideration the way it does in 0-1 knapsack.

Example: Difference from 0-1

#include <iostream>
using namespace std;
int main() {
	cout << "Same state and goal as 0-1 knapsack, but taking item i doesn't remove it from future consideration";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Same state and goal as 0-1 knapsack, but taking item i doesn't remove it from future consideration");
	}
}

print("Same state and goal as 0-1 knapsack, but taking item i doesn't remove it from future consideration")

#include <stdio.h>
int main() {
	printf("Same state and goal as 0-1 knapsack, but taking item i doesn't remove it from future consideration");
	return 0;
}

DP Transition

After taking an item, the transition can still consider that very same item again for the leftover capacity, rather than moving strictly on to the next item — that's the one line of code that separates unbounded from 0-1 knapsack.

Example: DP Transition

#include <iostream>
using namespace std;
int main() {
	int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 6;
	int dp[7] = {0};
	for (int w = 1; w <= capacity; w++)
		for (int i = 0; i < 3; i++)
			if (weights[i] <= w) dp[w] = max(dp[w], dp[w-weights[i]] + values[i]);
	cout << "Same item reconsidered for leftover capacity, best value: " << dp[capacity];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] weights = {2,3,4}, values = {3,4,5};
		int capacity = 6;
		int[] dp = new int[7];
		for (int w = 1; w <= capacity; w++)
			for (int i = 0; i < 3; i++)
				if (weights[i] <= w) dp[w] = Math.max(dp[w], dp[w-weights[i]] + values[i]);
		System.out.println("Same item reconsidered for leftover capacity, best value: " + dp[capacity]);
	}
}

weights, values, capacity = [2,3,4], [3,4,5], 6
dp = [0]*(capacity+1)
for w in range(1, capacity+1):
    for i in range(3):
        if weights[i] <= w:
            dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
print("Same item reconsidered for leftover capacity, best value:", dp[capacity])

#include <stdio.h>
int main() {
	int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 6;
	int dp[7] = {0};
	for (int w = 1; w <= capacity; w++)
		for (int i = 0; i < 3; i++)
			if (weights[i] <= w && dp[w-weights[i]] + values[i] > dp[w]) dp[w] = dp[w-weights[i]] + values[i];
	printf("Same item reconsidered for leftover capacity, best value: %d", dp[capacity]);
	return 0;
}

Coin-Like Problems

This 'reuse allowed' shape is exactly the structure behind coin-change (using unlimited coins to reach a target amount) and rod-cutting (cutting a rod into pieces to maximize total value), which is why they're usually taught right after this topic.

Example: Coin-Like Problems

#include <iostream>
using namespace std;
int main() {
	cout << "Coin change (reach a target amount) and rod-cutting share this exact 'reuse allowed' DP shape";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Coin change (reach a target amount) and rod-cutting share this exact 'reuse allowed' DP shape");
	}
}

print("Coin change (reach a target amount) and rod-cutting share this exact 'reuse allowed' DP shape")

#include <stdio.h>
int main() {
	printf("Coin change (reach a target amount) and rod-cutting share this exact 'reuse allowed' DP shape");
	return 0;
}

Practice

Whenever a problem statement allows an item, denomination, or piece to be reused without limit, that's the signal to reach for the unbounded knapsack DP pattern instead of the 0-1 version.

Example: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Item/denomination/piece reusable without limit? That's the signal for unbounded knapsack DP";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Item/denomination/piece reusable without limit? That's the signal for unbounded knapsack DP");
	}
}

print("Item/denomination/piece reusable without limit? That's the signal for unbounded knapsack DP")

#include <stdio.h>
int main() {
	printf("Item/denomination/piece reusable without limit? That's the signal for unbounded knapsack DP");
	return 0;
}

Unbounded Knapsack

Problem Idea

Difference from 0-1

DP Transition

Coin-Like Problems

Practice

Chapter Quiz — Complete all 12 topics to unlock

Login to run this code