Packing a 10 kg bag with the most valuable snacks: for each snack, you check whether packing it beats leaving it out, for every weight limit.
Clues that point here
→ Choose a subset under a budget or capacity
→ "Can these numbers sum to target?"
→ Coin change (fewest coins or number of ways)
→ Partition into equal sums
Not this pattern when
✕ Items can be split into fractions (greedy works)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Knapsack DP · template
int[] dp = new int[capacity + 1]; // 0/1 knapsack, 1D
for (int i = 0; i < n; i++) {
for (int c = capacity; c >= weight[i]; c--) { // backwards: each item used once
dp[c] = Math.max(dp[c], dp[c - weight[i]] + value[i]);
}
}
return dp[capacity];
// unbounded knapsack: loop c forwards so items can repeat