次のデータがあります：
item weight value value/weight
1 5 40 8
2 2 10 5
3 6 30 5
4 1 12 12
5 2 18 9
容量は 10 です。ノード 0 の上限を計算するにはどうすればよいですか? 次のようにノード 0 の上限を計算しています。
ub = v + [W-w] * [v/w]
ub = 0 + [10] * [8] = 80
または、値/重量が 12,9,8,5,5 の降順でアイテムを並べ替える必要がありますか? 上限を計算しますか？または、ソートせずに、上限を計算して次の項目に進むことなく、正しく実行していますか?
ソートなしの方法では、ノード0で最大上限を取得できません。そう思います。
ub = 0 + [10] * [12] = 120 // if sorted
ご協力ありがとうございます。