[Из песочницы] Немного об укладке рюкзака
Многим известна так называемая задача об укладке рюкзака. Вкратце напомню: из кучи предметов нужно выбрать такие, чтобы рюкзак был напихан под завязку и его еще можно было уволочь. Говоря более формально, необходимо из данного набора A пар чисел a (i)b (i), выбрать такие, чтобы сумма чисел, а не превосходила наперед заданного S, а сумма чисел b была максимальной. Σa (n) ≤ S, Σb (n)=max. Исходный набор: Σ a 3 14 25 26 32 2 28 23 1 9 163 b 11 12 5 30 31 25 19 27 32 33 225 Читать дальше →
