对于分支界限法的理解（补出门门票-week13，结对伙伴对我提的问题的答案）

首先我的结对伙伴给我提出了一个这样的问题：
使用分支界限法求解“背包问题”的步骤。
当时我是这样回答他的：
ub=v+(W-w)x(v(i+1)/w(i+1))
这个问题我在课上也没有理解清楚，因为我不知道ub是怎么算出来的。。。（虽然公式给了我，但我还是不理解）所以我准备周五去问问小助教这个问题如何求解，问题答案将在这周博客内容里体现。
我问过小助教之后，他从PPT下拉出来了备注（我居然忽略了备注）
于是我就把电脑抱回去自己看了。

对于分支界限法的疑惑

1、ub是理论上的最优上界，就是我要放的东西（假如说是物品1）要把背包放满能值多少钱。
那么为什么会等于100呢？物品1重量不是4吗？最多不是只能放两个ub=80吗？
是的，没错，但我们这里说ub是理论上的最优上界。我们要考虑的仅仅是背包的容量还有物品的单价，不去考虑物品的总重量（40），只考虑单价的重量（10）。于是ub=10x10=100。
那么为什么当我们不放物品1的时候ub=60呢？
这就要用到公式了：ub=v+(W-w)x(v(i+1)/w(i+1))
当我们不放物品1时，第二顺位要放的物品是物品2，所以公式中的v(i+1)就等于物品2的价值（42），w(i+1)就等于物品2的重量（7）。
而因为我们什么东西也没有放。
所以v=0，w=0，W还是不变等于10。
所以当我们不放物品1时ub=10x6=60。
2、当背包中只存在物品1时，ub之所以会变化是因为接下来要放的东西不同了。
在ub=76的时候，背包中接下来要放的是物品2。
也就是说，此时的v(i+1)=42、w(i+1)=7。
但物品2的重量加上物品1的重量等于11，超过了背包容量（10）。所以我们接下来要放物品3。
那么当我们要放物品3时，此时v(i+1)和w(i+1)已经不再是物品2的值了，而是v(i+1)等于物品3的v3=25、w(i+1)等于物品3的w3=5。
所以此时公式应该是：40+(10-4)×5=70。