UniLecs #168. Рюкзак

Задача: у вас есть рюкзак вместимостью S кг, а также различные предметы с разными весами.

Необходимо найти максимальный вес рюкзака, который можно собрать из заданных предметов.

Входные данные: Sum - вместимость рюкзака, натуральное число от 1 до 10^5. Weights[] - массив весов заданных предметов, где weights(i) - натуральное число от 1 до 10^5. Размер массива от 1 до 1000.

Вывод: максимальный вес рюкзака

Пример:

Sum = 18; Weights= [3 7 10 16]

Answer = 17

Идея: для решения этой задачи воспользуемся методом динамического программирования. Заведем массив d[], где d[i] = 1, если можно набрать вес в точности равный i, а иначе 0.

Последовательно будем перебирать предметы с весом w. Далее разобъем решение на подзадачи: будем перебирать рюкзаки разной вместимости, начиная с вместимостью sum заканчивая w. Проверяем можно ли заполнить рюкзак с вместимостью i предметами, которые в сумме дают в точности вес i.

Реализация:

https://gist.github.com/unilecs/b69011175a9302514a29584e0b1754b5

Play-test: https://dotnetfiddle.net/ykPFUp