【舌尖上的演算法】Day24 -- Dynamic Programming - Knapsack

2020 IT邦鐵人賽

Posted by Hank Lee on Thursday, October 1, 2020

3 Minutes Read

Table of Contents

本系列文章同步分享於IT邦幫忙第12屆鐵人賽

前言

今天要把一個舊問題拉出來再提一次,那就是 – 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(因為放不了任何東西)。 Dynamic Programming-Knapsack-1

有了這個表格後,我們又要怎麼去填入每一個cell(V)的值呢?跟前面的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-Knapsack-2

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

Dynamic Programming-Knapsack-3

當選擇出其中一個項目之後,就需要把容量扣除,才能透過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