我对背包问题很感兴趣，我想用分支定界算法来解决它。
我知道上限可以通过按价值/重量比对项目 1..n 进行排序，找到中断项目 s（第一个不完全适合背包的项目）并计算以下内容来计算：
（C是背包的容量，w(j)是物品j的重量）
（计算仍然适合背包的 s 分数）
（将前 s-1 项的所有值相加，并加上 s 值的一小部分）
但是，我不明白为什么我们可以将第三个等式的第二部分舍入，仍然保持我们的上限。
我希望有人能给我一个提示，一个解释或一些文献参考来解释这一点。
问问题
1866 次