Можно использовать задачу о ранце с указанным количеством весов

Question

У меня проблема с рюкзаком с указанной вместимостью рюкзака по весу и весу.

Мне нужен алгоритм, который упаковывает веса в рюкзак, когда рюкзак емкость равна C, необходимые весаcount - это N и есть список весов.Сортировка весов не имеет значения.Было бы лучше, если бы алгоритм был рекурсивным.

Например:
У меня есть рюкзак, ведьма может держать только 3 веса, и они должны весить 10, а у меня есть эти веса: 9, 8, 7, 2,1. Правильный (и единственный) ответ - 7, 2, 1.

Было бы лучше, если бы кто-то написал псевдокод, но это нормально, если он является одним из распространенных языков программирования.

PSЛюбые советы также приветствуются:)

[РЕДАКТИРОВАТЬ] Мне нужен алгоритм, который дает ответ с точно N счетчиком весов, который весит точно C.

Answer 1

Это проблема ранца 0-1, которая может быть решена с помощью динамического программирования за псевдоплиномиальное время.

См. статью о проблеме ранца в Википедии для получения инструкций о том, как решить проблемуиспользуя динамическое программирование.

См. эти слайды лекций по CS * для ознакомления и псевдокода.

Answer 2

http://en.wikipedia.org/wiki/Knapsack_problem должен помочь вам.У них также есть псевдокод для алгоритмов.