Rod Cutting Problem
HardUnbounded knapsack in disguise
Problem
Given prices for rod lengths, cut a rod of length n to maximize total price.
Like unbounded knapsack: for each length, try every first-cut and reuse the best for the remainder.
The idea
A cut of length i has weight i and value price[i], and you may cut as many as you like — that is exactly unbounded knapsack with capacity n. Recognising the restatement is the whole problem.
The trick
- Length is weight, price is value, rod length is capacity.
- Reuse allowed, so iterate capacity forwards.
0
∞
∞
∞
∞
∞
∞
0
1
2
3
4
5
6
Step 1 of 8. dp[a] = fewest coins to make amount a. Coins 1, 3, 4. dp[0] = 0, the rest start at ∞. Values: 0, ∞, ∞, ∞, ∞, ∞, ∞.
1/8
Optimal
timeO(amount·coins)spaceO(amount)
Unbounded knapsack.
1const dp = Array(amount + 1).fill(Infinity);2dp[0] = 0;3for (let a = 1; a <= amount; a++)4 for (const c of coins)5 if (c <= a) dp[a] = Math.min(dp[a], 1 + dp[a - c]);6return dp[amount] === Infinity ? -1 : dp[amount];Input
- array
- [0, ∞, ∞, ∞, ∞, ∞, ∞]
Memory
- a
- —
- a−c
- —
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- prices = [1,5,8,9,10,17,17,20]
- Output:
- 22
- Explanation:
- Best cuts of a length-8 rod earn 22.
Example 2
- Input:
- prices = [3,5,8,9]
- Output:
- 12
- Explanation:
- Four 1-inch pieces beat one big cut → 12.
Example 3
- Input:
- prices = [2,5,7,8]
- Output:
- 10
- Explanation:
- Best value is 10.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.