Многим известна так называемая задача об укладке рюкзака.
Вкратце напомню: из кучи предметов нужно выбрать такие, чтобы рюкзак был напихан под завязку и его еще можно было уволочь.
Говоря более формально, необходимо из данного набора 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 |
Читать дальше →
via Хабрахабр / Захабренные / Тематические / Посты http://habrahabr.ru/post/205890/
Комментариев нет:
Отправить комментарий