《弄懂動態規劃》揹包問題講解（一）

《弄懂動態規劃》揹包問題（二）程式碼實現

動態規劃功能強大，它能夠解決子問題並使用這些答案來解決大問題。

但僅當每個子問題都是離散的，即不依賴於其他子問題時，動態規劃才管用

。

可以偷商品的一部分嗎

假設你在雜貨店行竊，可偷成袋的扁豆和大米，但如果整袋裝不下，可開啟包裝，再將揹包倒滿。在這種情況下，不再是要麼偷要麼不偷，而是可偷商品的一部分。如何使用動態規劃來處理這種情形呢？

答案是沒法處理。使用動態規劃時，要麼考慮拿走整件商品，要麼考慮不拿，而沒法判斷該不該拿走商品的一部分。

但使用貪婪演算法可輕鬆地處理這種情況！首先，儘可能多地拿價值最高的商品；如果拿光了，再儘可能多地拿價值次高的商品，以此類推。

例如，假設有如下商品可供選擇。

藜麥比其他商品都值錢，因此要儘量往揹包中裝藜麥！如果能夠在揹包中裝滿藜麥，結果就是最佳的。

旅遊行程最最佳化

假設你要去倫敦度假，假期兩天，但你想去遊覽的地方很多。你沒法前往每個地方遊覽，因此你列個單子。

對於想去遊覽的每個名勝，都列出所需的時間以及你有多想去看看。根據這個清單，你能確定該去遊覽哪些名勝嗎？

這也是一個揹包問題！但約束條件不是揹包的容量，而是有限的時間；不是決定該裝入哪些商品，而是決定該去遊覽哪些名勝。請根據這個清單繪製動態規劃網格，再接著往下讀。

網格類似於下面這樣。

你畫對了嗎？請填充這個網格，決定該遊覽哪些名勝。答案如下。

處理相互依賴的情況

假設你還想去巴黎，因此在前述清單中又添加了幾項。

去這些地方遊覽需要很長時間，因為你先得從倫敦前往巴黎，這需要半天時間。如果這3個地方都去玩，是不是要4。5天呢？

不是的，因為不是去每個地方都得先從倫敦到巴黎。到達巴黎後，每個地方都只需1天時間。因此玩這3個地方需要的總時間為3。5天（半天從倫敦到巴黎，每個地方1天），而不是4。5天。

將埃菲爾鐵塔加入“揹包”後，盧浮宮將更“便宜”：只要1天時間，而不是1。5天。如何使用動態規劃對這種情況建模呢？

沒辦法建模。動態規劃功能強大，它能夠解決子問題並使用這些答案來解決大問題。

但僅當每個子問題都是離散的，即不依賴於其他子問題時，動態規劃才管用

。這意味著使用動態規劃演算法解決不了去巴黎玩的問題。

練習

假設你要去野營。你有一個容量為6磅的揹包，需要決定該攜帶下面的哪些東西。其中每樣東西都有相應的價值，價值越大意味著越重要：

水（重3磅，價值10）；

書（重1磅，價值3）

食物（重2磅，價值9）；

夾克（重2磅，價值5）；

相機（重1磅，價值6）。

請問攜帶哪些東西時價值最高？

歡迎把你的程式碼留在評論區