вариант задачи о рюкзаке

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

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

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

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


algorithm combinations
person jcs    schedule 08.09.2011    source источник
comment
Он ограничен пределом. Поэтому, если n разумно, это можно решить довольно быстро. (т.е. каково максимальное значение n?)   -  person flight    schedule 08.09.2011
comment
Ответ: 143 + 546 + 1402 + 2054 = 4145.   -  person Pete Wilson    schedule 08.09.2011
comment
@Пит 3564 + 1402 = 4966   -  person Ricky Bobby    schedule 08.09.2011
comment
@ Рики Бобби - правда, но парень должен положить в рюкзак как можно больше предметов (во всяком случае, как я это читал). Хммм. Ну, может быть, нет. Если задача состоит в том, чтобы вложить в рюкзак как можно больше веса, то, конечно, вы правы.   -  person Pete Wilson    schedule 08.09.2011
comment
@ Пит, правда, я пропустил эту часть вопроса: D   -  person Ricky Bobby    schedule 08.09.2011
comment
@jcs - в этих комментариях много подсказок, так что вы сможете легко решить эту проблему.   -  person Pete Wilson    schedule 08.09.2011
comment
Просто установите значение = вес в стандартной задаче о рюкзаке, если вы хотите максимизировать вес. Если вы хотите максимизировать количество элементов, установите значение = 1.   -  person Jean-François Corbett    schedule 08.09.2011
comment
@quasiverse - максимального предела n нет, но я не вижу, чтобы он превышал 200.   -  person jcs    schedule 08.09.2011
comment
@Ricky Bobby - проблема в том, чтобы положить в рюкзак как можно больше веса, а не столько предметов.   -  person jcs    schedule 08.09.2011

Ответы (2)


arrow_upward
1
arrow_downward

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

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

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

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

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

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

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

arrow_upward
0
arrow_downward

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

Хотя эта задача является частным случаем задачи о рюкзаке, она по-прежнему является NP-трудной.

person NPE    schedule 08.09.2011