iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 8
0

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

前言

接連兩天分別介紹了Selection Sort和Bubble Sort兩種排序的演算法,有沒有人開始覺得 『排個序也需要這麼麻煩的嗎?』 ,我自己在學習的過程中是覺得很有趣,就這麼單單是排序這件事情,卻可以有這麼多種不同的方式來達成目的,其實還是有很多種不同的Sort演算法,只是由於其他Sort演算法的分類不在Brute Force當中,因此我們將會在未來陸陸續續跟大家介紹。

今天我們就來說明同樣歸類為Brute Force的演算法 -- Knapsack Algorithm


真正的暴力 - Exhaustive Search

兩天前說Brute Force其實是一種暴力破解法,因此當然對於暴力破解一個問題就是要夠兇夠狠,直接產生所有的可能性,然後再從中找出最好的解答,這樣才夠暴力,而這種方式就叫做Exhaustive Search;基本上這種方式可能會有人覺得很笨很無趣,但很不巧地,可能有先問題還真的只有用這種方式反而可以更有效地取得解答。


Knapsack Algorithm是什麼?又是如何運作的呢?

假設現在有n個物品,每個物品都有它的重量(weight)和價值(value),要把這些物品裝進一個限重W的小背包,而在符合限重的前提下裝進最有價值的物品組合,這個就是所謂的Knapsack Problem。而Exhaustive Search就可以用來解決這個問題啦,流程如下:

  1. 針對這n個物品排列組合出所有的可能性(總負重及總價值)。
  2. 將所有可能性的總負重與小背包的限重W進行比較,留下符合限重的組合。
  3. 從留下的組合中找出總價值最高的組合。

好吧~說起來真的很『常識』,而他就真的這麼平常。


Knapsack Algorithm的範例時間

我們舉個例子來說明好了:

假設現在有個小背包限重(W)為15,而有4個物品(A, B, C, D)可以放入這個背包,其重量(w)與價值(v)分別為:

物品 重量 價值
A 7 $ 15
B 2 $ 10
C 6 $ 30
D 5 $ 50

經過上方所提到的流程第一步-找出所有可能性後,可以得到下表的結果:

組合 總重量 總價值
- 0 $ 0
A 7 $ 15
B 2 $ 10
C 6 $ 30
D 5 $ 50
A, B 9 $ 25
A, C 13 $ 45
A, D 12 $ 65
B, C 8 $ 40
B, D 7 $ 60
C, D 11 $ 80
A, B, C 15 $ 55
A, B, D 14 $ 75
A, C, D 18 $ 95
B, C, D 13 $ 90
A, B, C, D 20 $ 105

再來,第二步-比較背包限重(W<=15),留下符合的組合後,變成下表的結果:

組合 總重量 總價值
- 0 $ 0
A 7 $ 15
B 2 $ 10
C 6 $ 30
D 5 $ 50
A, B 9 $ 25
A, C 13 $ 45
A, D 12 $ 65
B, C 8 $ 40
B, D 7 $ 60
C, D 11 $ 80
A, B, C 15 $ 55
A, B, D 14 $ 75
A, C, D 超重 超重
B, C, D 13 $ 90
A, B, C, D 超重 超重

最後一步-找出當中價值最高的組合:

組合 總重量 總價值
- 0 $ 0
A 7 $ 15
B 2 $ 10
C 6 $ 30
D 5 $ 50
A, B 9 $ 25
A, C 13 $ 45
A, D 12 $ 65
B, C 8 $ 40
B, D 7 $ 60
C, D 11 $ 80
A, B, C 15 $ 55
A, B, D 14 $ 75
A, C, D 超重 超重
B, C, D 13 $ 90
A, B, C, D 超重 超重

這樣即可取得最佳組合-- B, C, D,其重量與價值分別為13和$ 90。


Knapsack Algorithm的時間複雜度(Time complexity)

在進行Knapsack Algorithm時,最花時間的過程會在排列組合,而針對n個物品進行排列組合,總共會取得2^n個結果,以上方例子來說,4個物品總共產生出16種可能性(2^4),而這一個步驟就是影響Knapsack Algorithm的關鍵所在,因此Knapsack Algorithm的時間複雜度即為O(2^n)

Knapsack的問題還有另外一種演算法可以解決,我們未來在介紹。


小結

  • Exhaustive Search就是先排列組合出所有可能性,再從中找出最佳解答。
  • Knapsnack Algorithm就是一種Exhaustive Search。
  • Knapsnack Algorithm的時間複雜度為O(2^n)

預告

明天我們將會介紹第四個屬於Brute Force的演算法-DFS和BFS。


References

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

上一篇
Day7 -- Brute Force - Bubble Sort
下一篇
Day9 -- Brute Force - DFS & BFS
系列文
舌尖上的演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0

Exhaustive Search那裡:
可能有問題還真的只有用這種方式反而可以更有效地取得解答 => 些
碰巧看到的xD

我要留言

立即登入留言