Можно использовать задачу о ранце с указанным количеством весов
У меня проблема с рюкзаком с указанным объемом рюкзака по весу и весу.
Мне нужен алгоритм, который упаковывает веса в рюкзак, когда вместимость ранца равна C, необходимое количество весов равно N, и есть список весов. Сортировка весов не имеет значения. Было бы лучше, если бы алгоритм был рекурсивным.
Например:
У меня есть рюкзак, ведьма может держать только 3 веса, и они должны весить 10, и у меня есть эти веса: 9, 8, 7, 2, 1. Правильный (и единственный) ответ - 7, 2, 1.
Было бы лучше, если кто-то напишет псевдокод, но это нормально, если это какой-либо из распространенных языков программирования.
PS Любые советы его также оценили:)
[РЕДАКТИРОВАТЬ] Мне нужен алгоритм, который дает ответ с точным подсчетом весов N, который весит точно C.
2 ответа
Это проблема ранцев 0-1, которая может быть решена с помощью динамического программирования за псевдоплиномиальное время.
См. Статью о проблеме ранца в Википедии, где приведены инструкции по ее решению с помощью динамического программирования.
Посмотрите эти слайды лекций по CS для ознакомления и псевдокода.
http://en.wikipedia.org/wiki/Knapsack_problem должен помочь вам. У них также есть псевдокод для алгоритмов.