ранец с уникальными элементами

Question

Я пытаюсь решить следующие:

Задача о рюкзаке заключается в следующем: дано множество целых чисел S = {s1, s2, ..., зп}, и данная целевая число T, найти подмножество S , которое суммируется точно до T. Например, в пределах S = {1,2,5,9,10} существует подмножество, которое добавляется до T = 22, но не T = 23. Дайте правильный алгоритм программирования для ранца, который работает в O (nT) времени.

но единственный алгоритм, который я мог бы придумать, генерирует все комбинации от 1 до N и пытается суммировать сумму (экспоненциальное время).

Я не могу разработать решение динамического программирования, поскольку тот факт, что я не могу повторно использовать объект, делает эту проблему отличной от проблемы обмена монетами и от общей проблемы с рюкзаком.

Может кто-нибудь помочь мне с этим или хотя бы дать мне подсказку?

Answer 1

Время работы O(nT) дает вам подсказку: выполните динамическое программирование на двух осях. То есть, пусть f(a,b) обозначает максимальную сумму < = b, которая может быть достигнута с помощью первых целых чисел a.

f удовлетворяет рекуррентные

f(a,b) = max(f(a-1,b), f(a-1,b-s_a)+s_a) 

, поскольку первое значение является максимальным без использования s_a, а второй максимум, включая s_a. Отсюда следует, что алгоритм DP должен быть простым, так как должен выводиться правильное подмножество S.