本系列文章同步分享於個人Blog - InformisTry - HankLee

前言

今天要把一個舊問題拉出來再提一次，那就是 -- Knapsack Problem；上一次是在第八天提到可以用Brute Force來解決這個問題（複習)，今天我們就來講講怎麼用Dynamic Programming來解決這個問題。

Dynamic Programming下的Knapsack Problem

Knapsack Problem是指當有一堆不同重量不同價值的物品，如何從這堆物品中選出最有價值的項目放入一個大小有限的背包(knapsack)中。在第八天，我們提到可以用Brute Force的概念，將這堆物品透過條列式的方式，將所有排列組合都條列出來，再從中去選擇符合背包大小且價值最高的組合。而後來針對這個問題又衍生出了Dynammic Programming的解決方式，在使用Dynamic Programming解決這個問題的時候，同樣是把大問題變成小問題，假設現在有一個背包，其容量(W)為5，那我們在進行Dynamic Programming的時候，就會從容量為0開始計算放進去的物品的價值合計，然後再來是容量為1，依此類推，最後我們就可以算出容量為5的時候哪個組合是最有價值的。

一步一步找出答案

在進行Dynamic Programming之前，要先準備好下面這個表格（就跟Edit Distance一樣）：

• 範例：w為物件大小，v為物件價值；Ｗ為背包容量
• 紅色的0是因為當背包的容量為0時，其背包內物品的價值也是0(因為放不了任何東西)。
  

有了這個表格後，我們又要怎麼去填入每一個cell（Ｖ）的值呢？跟前面的Coin-Row Problem和Edit Distance一樣，在每一個cell填值進去都是有其條件的，配合這個條件就可以來進行Dynamic Programming：

1. 當W減去w的值若大於等於0 ➜ V[x, y] = Max(V[x, y-1], v + V[x-w, y-1])
2. 當W減去w的值若小於0 ➜ V[x, y] = V[x, y-1]
   

在進行Dynamic Programming的過程中，都是一步一步去比較去計算，然後透過這些步驟，就可以取得最後的結果：75。那重點又來了，又要怎麼回推出要放哪個物件呢？ 讓我們繼續看下去：

當選擇出其中一個項目之後，就需要把容量扣除，才能透過backtracking取得結果，所以在這個範例中，最後選擇的是w1和w5，其價值為75。

小結

Knapsack Problem也可以用Dynamic Programming來解決。

預告

明天我們將會進入最後一個主題 - 貪婪的技術(Greedy Techniques)。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin