追加プロパティ付きナップザックアルゴリズム

Question

1つのプロパティがある場合、そこに何が起こっているのか分かります。 1つ以上のプロパティがある場合、ナップザックの問題を理解することに問題があります。

私は2つのプロパティを持つナップサックアルゴリズムを使用するプログラムを記述する必要があります。教師は私たちに言った、それは3dアレイで行われなければなりません。私はそのような配列がどのように見えるか想像できません。

のは、ここで言ってみましょうが、私の入力です：

4 3 4 // number of records below, 1st property of backpack, 2nd property of backpack 
1 1 1 // 1st property, 2nd property, cost 
1 2 2 // 1st property, 2nd property, cost 
2 3 3 // 1st property, 2nd property, cost 
3 4 5 // 1st property, 2nd property, cost 

と出力は、次のようになります。

4 // the cheapest sum of costs of 2 records 
1 3 // numbers of these 2 records 

出力の説明：レコードの 2セットは入力の第1 'ラインにさんに合います：

（2） - レコードの数4

3 4 5 

レコードの第一セットは（4 < 5）安いですので、我々はそれを選びました。そのようなレコードが存在するかどうかを調べるだけでなく、私が合計したレコードも見つけなければなりません。

しかし、今のところ、私は理解する必要があります、どのように3次元アレイのようになります。あなたの何人かが私の手助けをして、レイヤーごとに、私のイメージのように、どのように見えますか？おかげさまで

Answer 1

あなたは不可能な何かやろうとしている - あなたの問題です。

ディメンションの数を増やすと、アイテムに追加のプロパティが追加されます。そのため、テーブルの左柱側（prop1）の代わりに、長方形（prop1x）またはブロック面(prop1 x prop2 x prop3などがあります。しかし、表の行側を定義する既存の制約は、同じ次元数を持つ必要があります。 一次元だけでなく、。だから、決して 3次元ブロックに2つのプロパティの問題を置くことができるでしょう、代わりに4Dブロックが必要です。 3つのプロパティの6Dブロックなど。

Answer 2

3次元テーブルを使用しているとします。A[x][y][z]=k、x：合計1番目のプロパティ。 y：合計2番目のプロパティ。 z：合計3番目のプロパティ。 k：最小コスト（最大報酬、報酬を使用することをお勧めします）

アイテムを反復処理します。現在のアイテムが（p1、p2、p3、報酬）（報酬= - 費用）であるとします。各(x,y,z,k)のために、あなたの更新式：

A[x+p1][y+p2][z+p3] = max(A[x+p1][y+p2][z+p3], A[x+p1][y+p2][z+p3] + reward) 

RHS上の第一項はスロットA[x+p1][y+p2][z+p3]に、大きい場合は、ナップザックの構成がまだ残っています。それ以外の場合は、ナップザックをA[x+p1][y+p2][z+p3]に加えて現在のアイテムで更新します。

この切断物がクリアであることを望みます。