ナップサック問題のアルゴリズムについて

Question

すみません、プログラムの話ではないです。
ナップサック問題の解説サイトそもそも使えません。つまり、wi>w
w
i

w
の場合は、こちらの場合分けを無視する、または V(i−1,w−wi)=−∞
V
(
i
−
1
,
w
−
w
i
)

−
∞
と考えてください。

と書かれておりますが、例えば1番め、2番めの重さが1、1、価値もそれぞれ1,1であったとして

3番めの重さが3、価値が100であった場合でも無視されてしまうのでしょうか？

もう一つ質問ですが、ナップサック問題のアプローチ方法は色々あるかもしれませんが、大体の場合これが答え、という風に決まっていますか？

Comments

[tiitoi]

「つまり、」から「と書かれておりますが、」の間の部分が崩れてしまって読めないので修正おねがいします

Answer 1

※ただし、wi が w より大きい場合は、i 番目の荷物はそもそも使えません。つまり、wi>w の場合は、こちらの場合分けを無視する、または V(i−1,w−wi)=−∞ と考えてください。

原文はこうですが、上記に対する質問者さんの疑問

例えば1番め、2番めの重さが1、1、価値もそれぞれ1,1であったとして3番めの重さが3、価値が100であった場合でも無視されてしまうのでしょうか？

には肝心な情報が抜け落ちているように感じます(Wがいくつの前提で、何番目が無視されることが疑問なのか)が、おそらく「W=3のとき3番名が無視されてしまうと答えが出ない」ということではないでしょうか？もしそうだとすると・・・

3番目が無視されるかどうかはV(i, w)の__w__によって違い、

(A) V(3, 1), V(3, 2)の計算の際には無視される。
(B) V(3, 3)の計算の際には無視されない。

と考えればよいです。なおリンク先のサイトの表にはV(i, 0)の列がありませんが、その値が0であることは自明なので(B)を計算できます。

大体の場合これが答え、という風に決まっていますか？

「答え」が「採用すべきアルゴリズム」のことなのか「解が曖昧でない」ということなのかはっきりわかりませんでした。後者なら「価値の最大値は一意に決まり、荷物の選び方は複数あり得る」と思います。前者だとすると、残念ながら自分には充分知識がないので回答は他の方にお譲りします。

なお、ナップサック問題のバリエーション(あるいは派生問題?)の中には効率よく最適解を求めるのが困難なものもあり「とりあえず有限時間でそこそこよさそうな解を得る」ために(GAなどの)非決定的アルゴリズムによるアプローチがあるといった話は聞いたことがあります。

---

ご参考：

荷物#	重量	価値
1	1	1
2	1	1
3	3	100

で、W = 3の場合、V(i, w)の表はこのサイトのアルゴリズムに沿って順に埋めると次のようになります。

	w=0	w=1	w=2	w=3
i=0	0	0	0	0
i=1	0	1	1	1
i=2	0	1	2	2
i=3	0	(※1)1	(※1)2	(※2)100

※1:前述の(A)
※2:前述の(B)