вариант задачи о ранце

Question

У меня есть 'n' количество сумм (неотрицательные целые числа). Мое требование состоит в том, чтобы определить оптимальный набор сумм, чтобы сумма комбинации была меньше или равна заданному фиксированному пределу, а сумма была как можно большей. Не существует ограничений на количество сумм, которые могут быть включены в оптимальный набор.

для примера: суммы составляют 143,2054,546,3564,1402, а заданный лимит составляет 5000.

Насколько я понимаю, проблема с рюкзаком имеет 2 атрибута для каждого предмета (вес и стоимость). Но указанная выше проблема имеет только один атрибут (количество). Я надеюсь, что это сделает вещи проще? :)

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

Answer 1

это все еще непростая проблема, но если вы хотите (или должны) сделать что-то подобное, возможно, эта тема вам немного поможет:

найти два или более чисел из списка чисел, которые складываются на определенную сумму

, где я решил это следующим образом , а NikiC изменил его , чтобы он был быстрее . Единственное отличие: это было получение точной суммы, а не «как можно ближе», но это были бы лишь небольшие изменения в коде (и вам пришлось бы перевести ее на язык, который вы используете).

взгляните на комментарии в моем коде, чтобы понять, что я пытаюсь сделать в краткой форме:

• вычисление всех возможных комбинаций данных частей и суммирование их
• если результат - сумма, которую я ищу, сохраните решение в массиве
• , сортируйте все возможные решения, чтобы получить решение, использующее наименьшее количество частей

, поэтому вам придется изменить:

• сохраните решение, если оно меньше суммы, которую вы ищете
• сортировка решений по общему количеству вместо количества использованных деталей

Answer 2

Книга "Проблемы с рюкзаком" Ганс Келлерер, Ульрих Пферши и Дэвид Пизингер называют это Задачей подмножества сумм и посвящают ей целую главу (гл. 4).Глава очень всеобъемлющая и охватывает алгоритмы, а также результаты вычислений.

Несмотря на то, что эта проблема является частным случаем проблемы с рюкзаком, она все еще NP-трудна.