【演算法】動態規劃系列【一】【背包問題】

• 2022 年 3 月 15 日
• 筆記
• 【電腦02組】Java

情景設計

假設我們是職業小偷，背包出門偷東西

我們假設背包的承受重量是4kg

擺在我們面前的有三種商品

A.音響【3000元，4kg】

B.筆記型電腦電腦【2000元，3kg】

C.吉他【1500元，1kg】

當然小孩子才做選擇，成年人選擇全都要【開個玩笑】

由於我們的背包空間是有限的，所以只能選擇偷最高價值的商品

簡單演算法

最簡單的都是把所有的可能性都列出來

【1】放棄偷竊【0元，0kg】

【2】偷吉他【C】【1500元，1kg】

【3】偷音響【A】【3000元，4kg】

【4】筆記型電腦電腦【B】【2000元，3kg】

【5】偷吉他和音響【CA】【裝不下】

【6】偷吉他和筆記型電腦電腦【CB】【3500元，4kg】

【7】偷音響和筆記型電腦電腦【AB】【裝不下】

【8】全部偷走【ABC】【裝不下】

這樣雖然可行，但是速度太慢了，等我們考慮完，估計警察已經在背後站半天了

放到演算法時間複雜度大約是，簡直慢如蝸牛

動態規劃

這個是就要引出動態規劃

我們先來看看動態規劃演算法的工作原理

動態規劃簡單地說就是先解決子問題，再解決母問題

當然這個概念比較難理解，請同學們慢慢看

我們回到剛才的問題

網格的各行為商品，各列為不同容量( 1~4kg)的背包。所有這些列你都需要，因為它們將幫助你計運算元背包的價值。

首先來看第一行，意味著我們要嘗試偷吉他【但是到底偷不偷不一定，別忘了初心，我們是為了偷走最高價值的商品】

第一個單元格表示背包的容量為一kg。

吉他的重量也是一kg，這意味著可以裝入背包

這個單元格包含吉他，價值為1500美元

與這個單元格一樣，每個單元格表示背包的容量為2kg，可以裝下吉他

同學們可能對這個表格雲里霧裡，但是這裡是假設只有吉他可以偷

這裡同學們肯定會認為我在搞什麼無聊的事情

但別忘了，我們之前說過

動態規劃簡單地說就是先解決子問題，再解決母問題

當前這張圖是表示，如果有一個容量4kg的背包，可在其中裝入的商品的最大價值為1500美元

當然肯定這不是最終的答案

接下來我們放入音響

在每一行可偷得商品都為當前行的商品以及之前各行的商品

這表示我們現在只能偷影響和吉他

第一行第一列表示

背包容量為1kg時，之前可裝入商品的最大價值

第二行第一列表示

我們要用1kg的背包，在同時能偷吉他和音響的情況下，現在可裝入的商品的最大價值

我們得出的結論是背包的容量只有1kg的時候，我們偷不了音響

所以這時候我們能偷的最貴東西仍然是1500元

後面的結論是一樣的

到第二行第四列的時候，我們發現背包容量為4kg的時候

最大的價值更新為3000元

最後我們加入筆記型電腦電腦

但是這時候問題來了

背包容量為3kg的時候，我們可以偷的東西選擇性變大了，我們可以放棄吉他而去偷筆記型電腦電腦，所以最大的價值更新為2000元

總算來到了最後的問題

對於容量為4kg的背包，情況很有趣

這是非常重要的部分

當前最大價值為3000元，你可以不偷音響，而偷筆記型電腦電腦，但只價值2000元

那我們勢必面臨一個問題

3000元的音響 VS 2000元的筆記型電腦電腦+1kg的空餘容量

同學們發現沒有，之前在1kg的容量中我們可加入的最大價值是多少？

答案是1500元

這個時候就可以作比較了

3000元【音響】 VS 2000元【筆記型電腦電腦】+1500元【吉他】

同學們現在是否明白了為什麼要計算小背包可裝入了商品的最大價值

這樣餘下的空間我們不必再花大量的時間去做計算

答案如下，將吉他和筆記型電腦電腦裝入背包時價值最高，為3500美元

同學們聽到這裡可能還是有點疑惑，其實每個單元格的價值，使用的公示都相同

cell[i][j]=上一個單元的價值cell[i-1][j]VS當前商品的價值+剩餘空間的價值

你可以使用這個公式來計算每個單元格的價值,最終的網格將與前一個網格相同。

現在你明白了為何要求解子問題吧?你可以合併兩個子問題的解來得到更大問題的解。

拓展內容

增加一件商品

我們再玩點刺激的，加入第四件商品，一個iphone【2000元，1kg】

此時我們要不要推到重來？

根本不需要，動態規劃主筆計算最大的值，我們之前做的事情，完全可以繼續做

在第四行，加入iphone

當然為了方便同學們看清楚

我再重新列一下

A.音響【3000元，4kg】

B.筆記型電腦電腦【2000元，3kg】

C.吉他【1500元，1kg】

D.一個iphone【2000元，1kg】

這裡我就不再演示了，直接給出答案，請同學們自己去學著寫寫看

打亂行的順序

肯定有同學會問，如果我打亂順序，是否會影響最大價值

這肯定是不會的，那按這種說法豈不是，變成我【先偷吉他後偷電腦】會比【先偷電腦後偷吉他】貴了

也可以給大家演示一下

同學們也可以逐步按列填充，不按行填充，這是一樣的

增加一件小商品

如果加入的是項鏈D.項鏈【1000元，0.5kg】

那就加大了同學們的負擔了，需要做更精細的表格

偷部分商品

比方說我們偷雜貨鋪，裡面有大米，麵粉，鹽之類的

但這種東西不可能偷全部，因為不可能整袋抗走，不然估計還沒出門就被打死了

這個時候不可能用動態規劃，而要改用貪心演算法

背包沒裝滿

同學們肯定會問，最優解可能導致背包沒裝滿嘛，完全可能

我都不用給大家演示數據，大家想想

五塊鐵塊，和一顆鑽石

你的背包又只夠裝半塊鐵塊的

那你偷什麼呢，肯定偷鑽石呀

那你裝滿了嗎，沒有呀

同學們編程一定要注意不要脫離生活，不然有時候得出來的結論往往容易和賣菜的阿姨都懂的常識相違背