Table of Contents
前言
今天要把一個舊問題拉出來再提一次,那就是 – 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為物件價值;W為背包容量
- 紅色的
0
是因為當背包的容量為0
時,其背包內物品的價值也是0(因為放不了任何東西)。
有了這個表格後,我們又要怎麼去填入每一個cell(V)的值呢?跟前面的Coin-Row Problem和Edit Distance一樣,在每一個cell填值進去都是有其條件的,配合這個條件就可以來進行Dynamic Programming:
- 當W減去w的值若大於等於0 ➜
V[x, y] = Max(V[x, y-1], v + V[x-w, y-1])
- 當W減去w的值若小於0 ➜
V[x, y] = V[x, y-1]
在進行Dynamic Programming的過程中,都是一步一步去比較去計算,然後透過這些步驟,就可以取得最後的結果:75
。那重點又來了,又要怎麼回推出要放哪個物件呢? 讓我們繼續看下去:
當選擇出其中一個項目之後,就需要把容量扣除,才能透過backtracking取得結果,所以在這個範例中,最後選擇的是w1和w5
,其價值為75
。
小結
Knapsack Problem也可以用Dynamic Programming來解決。
預告
明天我們將會進入最後一個主題 - 貪婪的技術(Greedy Techniques)。