Задание 4. Решение задачи "Рюкзак" методом динамического программирования

Необходимо реализовать "альтернативный" ("двойственный") метод из тех двух, про которые я рассказывал на лекции. Формат входных и выходных данных - такой же, как для задания 1. Пример тестового набора прилагается.