Zakład produkujący gwoździe otrzymuje drut do produkcji w kawałkach po 30cm. Kawałki te cięte są na krótsze: 11cm, 8cm, 5cm. Pociąć je trzeba tak, aby otrzymać:
12tys. gwoździ po 11cm
24tys. gwoździ po 8cm
27tys. gwoździ po 5cm
I zminimalizować odpad.
X1
X2
X3
X4
X5
X6
X7
X8
X9
Sposoby cięcia
I
II
III
IV
V
VI
VII
VIII
IX
11
2
1
0
12tys
8
3
24tys
5
4
6
27tys
Odpad
C
M
Zb
sinfullove