07/08/07 14:46:50
>>226
A 価値 9 重さ 8 価値/重さ 1.125
B 価値 10 重さ 9 価値/重さ 1.111...
最大重量 20
のとき、そのアルゴリズムによれば
A 2個 価値 18 重さ 16
だけど
A 1個 B 1個 価値 19 重さ 17
B 2個 価値 20 重さ 18
で、価値/重さの大きいものを全く含まない組み合わせの方が総価値が高くなる
07/08/07 14:46:50
>>226
A 価値 9 重さ 8 価値/重さ 1.125
B 価値 10 重さ 9 価値/重さ 1.111...
最大重量 20
のとき、そのアルゴリズムによれば
A 2個 価値 18 重さ 16
だけど
A 1個 B 1個 価値 19 重さ 17
B 2個 価値 20 重さ 18
で、価値/重さの大きいものを全く含まない組み合わせの方が総価値が高くなる