これは複数のナップザック問題のバリエーションかもしれないと思っています。ここに問題があります:ナップザックアルゴリズムのバリエーション
既知の値と重みを持つ項目があります。あなたはまた、一連のナップザックを持っており、各ナップザックは一定数のアイテムを保持することができます(異なるナップザックは異なる数のアイテムを保持できるかもしれません)。所定の体重を維持しながら、ナップザックのアイテムの合計価値を最大化します。
個々のナップザックには重量制限がないことに注意してください。各ナップザックには、「含めることができるアイテム数」の制限しかありません。唯一の他の制限は、アイテムの総重量です。
(もちろんブルートフォース以外)。前もって感謝します! :)
編集:私は含めるのを忘れてひとつの重要な制限:
アイテムは、必ずしもすべての袋に入れることができません。基本的に、それらの値が互換性のないバッグに入れられると、その値はゼロになります。あなたは、各アイテムがそのバッグに依存する値を持つ一般的なケースを想像することができますが、私の場合、その値はバッグに応じて0または通常の値のいずれかになります。
この課題はありますか?もしそうなら、我々はそのようにタグ付けするべきです。何を試しましたか? –
ああ、宿題ですか? :)おそらくここでいくつかの憎悪を取得するつもりです。 – SinisterRainbow
これは、すべての異なるナップザックを1つのナップザックとして扱うと、同じ「ナップザック」です。ナップザックを近似するには多くの方法がありますが、Google検索をすれば見つけることができます。 – twain249