-3

私はここと同じ問題を抱えています: Variation on knapsack - 最小合計値が 'W' を超えており、制約が追加されています。

詳細：

アイテムのグループがあり、各アイテム (i) には重量 (w_i) と値 (v_i) と価格 (p_i) があります。これらのアイテムのサブグループを次のように選択する必要があります。

  • 総集計値を最小化する

st

  1. 合計総重量は少なくともWです。
  2. 合計総価格は最大でPです。

最後の制約を無視すると、これは 0/1 ナップザック問題と同等であり、上記の質問に記載されているamitのように解決できます。最後の制約を追加しても、動的計画法を使用して解決できますか?

どんなヒントでも大歓迎です。

4

2 に答える 2

0

これは NP 困難な問題であるため、すべてのケースをテストするだけで済みます。

于 2012-06-11T17:37:20.833 に答える
0

明らかな解決策は、動的計画法の状態で 2 つの変数 W (現在の重量) と P (現在の価格) を使用して、m[W][P] がこれら 2 つのパラメーターで最良の値を与えるようにすることです。これにより、O(nP * 重みの合計) で実行されるアルゴリズムが得られます。

(重みの合計) * P または W * (価格の合計) が大きいかどうかに応じて、補完的な解決策 (amit の回答のように W と P を反転する) を検討することもできます。

于 2012-06-11T22:20:02.010 に答える