Задача о погрузке судна (задача о ранце)

Пусть имеется судно грузоподьемностью х, требуется перевезти  n-типов предметов, s_i-стоимость i-го типа,o_i-вес i-го предмета. Нужно набрать предметов на максимальную стоимость и удовлетворить условие грузоподъемности.

Z_i=число предметов i-го типа. Тогда

S_i=1ⁿz_i*o_i<=x;                                L_n(z₁,...z_n)=S_i v_i*z_i     цена груза

    суммарный вес груза               z_i>=0,целочисленное

Если откинуть условие целочисленности, то задача решается просто

Пусть max(v_i/o_i)=v_k/o_k    тогда

                    max L_n=x*v_k/o_k

Можно показать, что округление решения для задачи с непрерывным изменением переменных до ближайшего целого может дать неоптимальное решение.

Пусть имеется 3 типа предметов:

o₁=49,o₂=50,o₃=51, v₁=20,v₂=75,v₃=100. Пусть x=100 (грузоподъемность).

Тогда max v_i/o_i=100/51=1.96

Нужно взять один предмет 3-го типа и один 1-го типа. Общая стоимость-120, вес-100. Но оптимальным решением является два предмета 2-го типа, так как общий вес будет 100,а стоимость- 150.