3

ナックパック問題についてのタスクがあります。しかし、knackpack の各サブジェクトには、2 セットの重み値パラメーターがあります。例えば：

  1. ビール 1kg 15$、2kg 20$
  2. 水 5kg 30$、10kg 40$

...等

また、アイテムごとに 1 セットの重み値パラメーターのみを選択できます。

だから、私が見る解決策：

  1. 2 つの配列からペアの重量と値の一意の組み合わせをすべて生成しました。2 n 個の組み合わせがあります。
  2. すべての組み合わせについて、knackpack アルゴリズムを適用し、最大値を持つソリューションを選択します。これが最適なソリューションです。

問題について - アイテムが 10 ～ 15 個程度あれば正常です。しかし、このタスクを 1000 個のアイテムで解決する必要があるため、2 1000 個のユニークな組み合わせになります。

一意の結合を生成:

E=[[],[]]
weight1 = [1 2 3 4 5]
weight2 = [6 7 8 9 10]
for choices in itertools.product([0, 1], repeat=len(off)):
E[0].append([(on[j] if choice else off[j]) for j, choice in enumerate(choices)])
value1 = [10 20 30 40 50]
value2 = [60 70 80 90 100]
for choices in itertools.product([0, 1], repeat=len(off)):
E[1].append([(on[j] if choice else off[j]) for j, choice in enumerate(choices)])

30 個のアイテムに対してこれを行うと、VDS がダウンします。

この問題の解決策を提案してください。

4

1 に答える 1

3

ブルート フォースで NP 完全問題を解決したい場合、さらにアイテム数が多い場合。理論的には機能しますが、それを行うには永遠が必要です。あなたの問題はpythonには関係ありませんが、理論的なコンピューターサイエンスに関係しています。

ナップザック問題のウィキペディアのページには、解決方法に関するいくつかのアイデアが含まれています。動的計画法を使用したり、解の近似を検索したりすることもできます。

動的計画法のアプローチは、問題が最適な部分構造を持つという事実に基づいています。つまり、n-1 変数問題の最適解から n 変数問題の最適解を構築することが可能です。

于 2013-07-16T09:52:18.497 に答える