ナップザック問題に興味があり、分岐限定アルゴリズムで解決したいと考えています。
上限は、アイテム 1..n を値/重量比で降順に並べ替え、分割アイテム s (ナップザックに完全に収まらない最初のアイテム) を見つけ、以下を計算することで計算できることを知っています。
(C はナップザックの容量、w(j) はアイテム j の重量)
(ナップザックにまだ収まる s の割合を計算する)
(最初の s-1 アイテムのすべての値を合計し、s の値の分数を追加します)
しかし、私が理解できないのは、上限を保持したまま 3 番目の方程式の 2 番目の部分を切り捨てることができる理由です。
誰かがヒント、説明、またはそれを説明する文献の参照を教えてくれることを願っています.