Жадные алгоритмы. Задача о рюкзаке.

Определение

Задача о рюкзаке: есть N предметов, стоимость i-ого предмета vi, масса wi. Найти набор предметов с наибольшей стоимостью, не превосходящей массы W.

Идея

1. Отсортировать предметы в по цене за единицу массы ( vi / wi ) в порядке убывания.
2. Идём по отсортированному массиву, если предмет помещается берём, иначе пропускаем.

N = 3 W = 40 w1 = 10; v1 = 60 w2 = 20; v2 = 100 w3 = 20; v3 = 100

По жадному алгоритму 160 (w1, w2) Настоящий ответ 200 (w2, w3)