167 lines
4.6 KiB
Markdown
167 lines
4.6 KiB
Markdown
# Cut Rod Problem — Dynamic Programming
|
||
|
||
A complete implementation of the classic **Rod Cutting Problem** from *Introduction to Algorithms* (CLRS), with three algorithmic approaches and an interactive browser-based visualizer.
|
||
|
||
---
|
||
|
||
## The Problem
|
||
|
||
You have a rod of length **n** inches and a price table that tells you how much each cut length sells for. You want to cut the rod into pieces (or keep it whole) to **maximize total revenue**.
|
||
|
||
```
|
||
Length: 1 2 3 4 5 6 7 8 9 10
|
||
Price: 1 5 8 9 10 17 17 20 24 30
|
||
```
|
||
|
||
For a rod of length 4, the best strategy is two pieces of length 2 (5 + 5 = **$10**), not selling it whole for $9.
|
||
|
||
This is a classic **optimal substructure** problem: the best way to cut a rod of length n depends on the best ways to cut shorter rods — making it a perfect fit for dynamic programming.
|
||
|
||
---
|
||
|
||
## Algorithms
|
||
|
||
### 1. Naive Recursion — `simple_cut_rod(p, n)`
|
||
|
||
Tries every possible first cut at position i and recurses on the remainder.
|
||
|
||
```python
|
||
def simple_cut_rod(p, n):
|
||
if n == 0:
|
||
return 0
|
||
q = float('-inf')
|
||
for i in range(1, n + 1):
|
||
q = max(q, p[i] + simple_cut_rod(p, n - i))
|
||
return q
|
||
```
|
||
|
||
**Time complexity:** O(2ⁿ) — exponential. Each subproblem is recomputed from scratch.
|
||
|
||
---
|
||
|
||
### 2. Top-Down DP with Memoization — `memoized_cut_rod(p, n)`
|
||
|
||
Same recursion as above, but caches results in an array `r`. If `r[n]` has already been computed, return it immediately.
|
||
|
||
```python
|
||
def memoized_cut_rod(p, n):
|
||
r = [float('-inf')] * (n + 1)
|
||
return _memoized_cut_rod_aux(p, n, r)
|
||
```
|
||
|
||
**Time complexity:** O(n²) — each of the n subproblems is solved exactly once.
|
||
|
||
---
|
||
|
||
### 3. Bottom-Up DP — `bottom_up_cut_rod(p, n)`
|
||
|
||
Fills a table `r[0..n]` iteratively from the smallest subproblem up. For each rod length j, tries every first cut i from 1 to j and stores the best result.
|
||
|
||
```python
|
||
def bottom_up_cut_rod(p, n):
|
||
r = [0] * (n + 1)
|
||
for j in range(1, n + 1):
|
||
q = float('-inf')
|
||
for i in range(1, j + 1):
|
||
q = max(q, p[i] + r[j - i])
|
||
r[j] = q
|
||
return r[n]
|
||
```
|
||
|
||
**Time complexity:** O(n²) | **Space complexity:** O(n)
|
||
|
||
This is the approach animated in the visualizer.
|
||
|
||
---
|
||
|
||
## Complexity Comparison
|
||
|
||
| Approach | Time | Space | Notes |
|
||
|---|---|---|---|
|
||
| Naive recursion | O(2ⁿ) | O(n) call stack | Impractical for n > 30 |
|
||
| Top-down (memoized) | O(n²) | O(n) | Natural recursive structure |
|
||
| Bottom-up | O(n²) | O(n) | No recursion overhead, cache-friendly |
|
||
|
||
---
|
||
|
||
## Project Files
|
||
|
||
```
|
||
.
|
||
├── cut_rod.py # Python implementation (all 3 algorithms)
|
||
├── visualization.html # Interactive browser visualizer
|
||
└── Cut Rod Problem/
|
||
└── Cut Rod Problem/
|
||
├── Program.cs # Original C# implementation
|
||
└── Data.txt # Price table (33 prices, space-separated)
|
||
```
|
||
|
||
### `Data.txt` — Price Table
|
||
|
||
```
|
||
1 5 8 9 10 17 17 20 24 30 33 31 31 31 40 39 20 45 42 46 70 76 77 80 85 90 95 100 110 120 111 200 678
|
||
```
|
||
|
||
Prices for lengths 1 through 33 inches.
|
||
|
||
---
|
||
|
||
## Running the Python Version
|
||
|
||
```bash
|
||
python3 cut_rod.py
|
||
```
|
||
|
||
You will be prompted for a rod length. Switch between algorithms by uncommenting the desired line in `main()`:
|
||
|
||
```python
|
||
best_price = memoized_cut_rod(prices, n) # default
|
||
# best_price = bottom_up_cut_rod(prices, n)
|
||
# best_price = simple_cut_rod(prices, n) # slow for n > 25
|
||
```
|
||
|
||
**Example output for n = 10:**
|
||
```
|
||
Enter number of Inches: 10
|
||
Best Revenue is upto : 30
|
||
Time Elapsed : 0.000021875s
|
||
```
|
||
|
||
---
|
||
|
||
## Running the Visualizer
|
||
|
||
Open `visualization.html` directly in any modern browser — no server or dependencies needed.
|
||
|
||
```bash
|
||
open visualization.html # macOS
|
||
start visualization.html # Windows
|
||
xdg-open visualization.html # Linux
|
||
```
|
||
|
||
### Controls
|
||
|
||
| Control | Action |
|
||
|---|---|
|
||
| Rod Length | Set the rod length (1–25). Resets the animation. |
|
||
| Speed | Adjust playback speed (1× slow → 10× fast). |
|
||
| ▶ Play | Run the animation automatically. |
|
||
| ⏸ Pause | Pause at the current step. |
|
||
| ⏭ Step | Advance one step forward. |
|
||
| ⏮ Back | Go one step backward. |
|
||
| ↺ Reset | Restart from the beginning. |
|
||
|
||
---
|
||
|
||
## Example: Rod of Length 10
|
||
|
||
The algorithm finds that the maximum revenue is **$30**, achieved by keeping the rod uncut (selling the full 10-inch piece at $30).
|
||
|
||
For a rod of length 7, the optimal is **3 + 4 = $17** (8 + 9 = $17, compared to selling whole for $17 — same either way, but the s-table reveals the first cut chosen).
|
||
|
||
---
|
||
|
||
## References
|
||
|
||
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). *Introduction to Algorithms* (3rd ed.), Section 15.1 — Rod cutting.
|