オペレーションズリサーチのナップザックについてです。

質問

こんばんは。
今度試験があるのですが、まったくわかりません・・・。

サイズが９のナップザックに以下の４個のアイテムを選択してメリットの総和が最大になるようにしたい。下記の表を埋めて、持っていくアイテムを見つけよ。

　　　　　アイテム　　１　２　３　４
　　　　　メリット　　５　７　４　６
　　　　　サイズ　　　３　５　２　４

０ １ ２ ３ ４ ５ ６ ７ ８ ９
G1(Y) ０
X1 ０
G2(Y) ０
X2 ０
G3(Y) ０
X3 ０
G4(Y) 記入不要
記入不要

よろしくお願いします。

回答No.2

Tacosan

多分, 横方向がサイズですね. 「サイズが 0 のとき」, 「サイズが 1 のとき」, ... の意味かな.
ちょっと記号の整理: アイテム i のサイズを s_i, メリットを m_i とします.
ここで, 例えば全体のサイズが k のときにアイテム 1 を入れるとすると残りのサイズは k - s_1 となり, 得られるメリットの合計は「サイズ k - s_1 のときの最大メリット」に m_1 を加えた値となります. 他の全てのアイテムに対して同様のことを行い, メリットの合計が最大になる選び方が「サイズ k に対する最適な選び方」となります. この操作は, サイズ 0, 1, ..., k-1 までの答えがわかっていれば簡単に行うことができます.
ということで, これをサイズが 9 になるまで実行すればいいはず. あ, 同じアイテムを複数選んでよいかどうかは知りませんので, 問題から判断してください.
このように, 「より小さい問題」に対する答えを記憶しておいて, それを使って大きな問題に対する答えを構築してゆくのが動的計画法 (DP) だ... ってのはいいね (←確認)?
え～, 一般論としてはこの通りなんだけど, G4(Y) で「記入不要」となっているのが意味不明だなぁ....

回答No.1

Tacosan

記号の意味くらい教えてくれないと書きようがないんだけどなぁ....
まあ, こんな表を作っていることからして, ただの DP かな?

補足

回答ありがとうございます。

DPだと思います！！問題に記号の意味が書いてないんです・・・。
バカですいません・・・。