Я думаю, что это может быть разновидностью проблемы с несколькими рюкзаками (или, может быть, даже может быть сведена к ней), но я не уверен. Вот проблема:Вариация на алгоритм ранца
У вас есть набор предметов с известными значениями и весами. У вас также есть набор ранцев, и каждый рюкзак может содержать фиксированное количество предметов (разные рюкзаки могут содержать различное количество предметов). Максимизируйте общую стоимость предметов в рюкзаках во время пребывания под определенным весом.
Обратите внимание, что отдельные рюкзаки не имеют ограничения по весу. Каждый рюкзак имеет только «количество элементов, которые могут содержать». Единственным другим ограничением является общий вес предметов.
Любые идеи? (за исключением грубой силы). Заранее спасибо! :)
EDIT: один важное ограничение я забыл включить:
Предметы, которые не обязательно могут быть помещены в любую сумку. По сути, их значение становится равным нулю, если они помещаются в сумку, с которой они не совместимы. Вы можете представить общий случай, когда каждый элемент имеет значение, зависящее от его сумки, но для моего случая его значение будет либо 0, либо нормальное значение, в зависимости от сумки.
Это домашнее задание? Если это так, мы должны пометить как таковой. Что вы пробовали? –
Uh - домашнее задание? :) Вероятно, здесь будет какая-то ненависть. – SinisterRainbow
Это «Рюкзак», если вы относитесь ко всем разным рюкзакам как к одному рюкзаку, это то же самое. Есть много способов приблизиться к Knapsack. Я уверен, что вы можете найти их, если вы выполните поиск в Google. – twain249