Skip to content

p2.md

Latest commit

 

History

History
15 lines (10 loc) · 650 Bytes

p2.md

File metadata and controls

15 lines (10 loc) · 650 Bytes

Problem

Exercises 15.1-2
Show, by means of a counterexample, that the following "greedy" strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be pi / i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1 ≤ i ≤ n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n - i.

Solution

Consider a rod of length 3

i 1 2 3
pi / i 1 5 4
pi 1 10 12

11 (Greedy: 1, 2) < 12 (Optimal: 3)