Обратная задача о рюкзаке

[yuyoyuppe]

Здравствуйте, пытаюсь решить следующую задачу методом динамического программирования:
Дан набор предметов с заданным весом и ценой, при этом вес предмета - действительное число, а цена - натуральное. Нужно определить минимальную вместимость рюкзака с суммарной ценностью большей либо равной заданному значению.
У задачи 2 варианта: каждый предмет можно брать n раз, либо 0-1 раз.

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

Искал решение в интернете, смотрел книгу "Введение в исследование операций", но всегда натыкался только на прямую задачу.

[Shadow]

Я когда не знаю что делать, делаю то, что знаю. Методом деления интервала пополам задавал бы стоимости объема рюкзака и решал бы $\log_2(n)$ нормальные задачи о рюкзаке. Где $n$ разница между минимальной и максимальной стоимости объема. И сравнивал бы стоимость функции с заданой.
Не уверен насколько хорошее, но все таки решение. Пусть другие скажут.

[Shadow]

Где $n$ - вес оптимального предмета (с оптимальное соотношение вес-цена). Кладем в рюкзак предмет пока не достигнем заданную ценность. И готов интервал - где можно и где нельзя

[deep blue]

Действуя в лоб, почти сразу получаем задачу о рюкзаке. Запишем задачу формально:

$$ax \ge C$$

$$\min mx$$

где $a$ - целочисленный положительный вектор стоимостей, $x$ - вектор решения, $m$-действительный вектор весов, $C$-граничная стоимость.
Уже видно, что это практически и есть задача о рюкзаке, дальнейшее дело техники и вкуса. Для того, чтоб ее привести к стандартной форме, можно сделать замену $x(i)=n-y(i)$. Получим:

$$\max my$$

$$ay \le-C+nS$$

$S$-сумма всех стоимостей, поэтому $-C+S \ge 0$. Найдя решение просто делаем обратную замену. Да, и разумеется игреки должны быть не больше n это легко учесть в методе ДП.