• 首先我的結(jié)對伙伴給我提出了一個這樣的問題：
• 使用分支界限法求解“背包問題”的步驟。
• 當時我是這樣回答他的：
• ub=v+(W-w)x(v(i+1)/w(i+1))
• 這個問題我在課上也沒有理解清楚，因為我不知道ub是怎么算出來的。。。（雖然公式給了我，但我還是不理解）所以我準備周五去問問小助教這個問題如何求解，問題答案將在這周博客內(nèi)容里體現(xiàn)。
• 我問過小助教之后，他從PPT下拉出來了備注（我居然忽略了備注）
• 于是我就把電腦抱回去自己看了。

對于分支界限法的疑惑

• 1、ub是什么，為什么背包沒裝物品的時候ub可以是100，也可以是60？
• 2、為什么當背包中只存在物品1的時候，ub是會發(fā)生改變的？

問題的答案（自己理解的）

• 1、ub是理論上的最優(yōu)上界，就是我要放的東西（假如說是物品1）要把背包放滿能值多少錢。
• 那么為什么會等于100呢？物品1重量不是4嗎？最多不是只能放兩個ub=80嗎？
• 是的，沒錯，但我們這里說ub是理論上的最優(yōu)上界。我們要考慮的僅僅是背包的容量還有物品的單價，不去考慮物品的總重量（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)已經(jīng)不再是物品2的值了，而是v(i+1)等于物品3的v3=25、w(i+1)等于物品3的w3=5。
• 所以此時公式應(yīng)該是：40+(10-4)×5=70。

感想

• 其實PPT下面的備注說的已經(jīng)非常的清楚，但是我還是希望我能用自己理解的方式寫在博客中。
• 而且我一開始真的沒看懂PPT上面的備注······