3

入力があるとしましょう：

10 // saying 1st property should be 10(in total)
10 // saying 2d property should be 10 (in total)
5 // saying theres 5 records below
// (1st property) (2nd property) (cost)
2 5 8 
7 3 10 
4 2 9
4 3 5
8 5 15

この場合、出力は次のようになります。

22 // lowest possible cost
1 3 4 // indexes of records, we've been using (indexing starts with 1)

 2  5  8
 4  2  9
 4  3  5
+---------
 10 10 22

これらのプロパティを 10 と 10 にする方法がない場合、プログラムは -1 を出力します。ナップザックの問題を解決する方法は知っていますが、この問題を解決する方法はわかりません。

4

1 に答える 1

2

ナップザック問題の同じアプローチを使用できますが、2D マトリックスの代わりに、3D テーブル、各パラメーターの次元 (2 つの制約 + インデックス) があります。

再帰式は似ていますが、もちろん両方のパラメーターに対して行われます。

f(item,cost1,cost2) = max {
               f(item-1,cost1,cost2), 
               f(item,cost1-firstCost[i],cost2-secondCost[i]) + profit[i]
                          }

(基本句も同様ですが、追加の次元があります。)

于 2012-11-15T18:54:35.663 に答える