本系列文章同步分享於個人Blog → InformisTry-HankLee
接連兩天分別介紹了Selection Sort和Bubble Sort兩種排序的演算法,有沒有人開始覺得 『排個序也需要這麼麻煩的嗎?』 ,我自己在學習的過程中是覺得很有趣,就這麼單單是排序這件事情,卻可以有這麼多種不同的方式來達成目的,其實還是有很多種不同的Sort演算法,只是由於其他Sort演算法的分類不在Brute Force當中,因此我們將會在未來陸陸續續跟大家介紹。
今天我們就來說明同樣歸類為Brute Force的演算法 -- Knapsack Algorithm。
兩天前說Brute Force其實是一種暴力破解法,因此當然對於暴力破解一個問題就是要夠兇夠狠,直接產生所有的可能性,然後再從中找出最好的解答,這樣才夠暴力,而這種方式就叫做Exhaustive Search;基本上這種方式可能會有人覺得很笨很無趣,但很不巧地,可能有先問題還真的只有用這種方式反而可以更有效地取得解答。
假設現在有n個物品,每個物品都有它的重量(weight)和價值(value),要把這些物品裝進一個限重W的小背包,而在符合限重的前提下裝進最有價值的物品組合,這個就是所謂的Knapsack Problem
。而Exhaustive Search就可以用來解決這個問題啦,流程如下:
好吧~說起來真的很『常識』,而他就真的這麼平常。
我們舉個例子來說明好了:
假設現在有個小背包限重(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時,最花時間的過程會在排列組合
,而針對n個物品進行排列組合,總共會取得2^n
個結果,以上方例子來說,4
個物品總共產生出16
種可能性(2^4
),而這一個步驟就是影響Knapsack Algorithm的關鍵所在,因此Knapsack Algorithm的時間複雜度即為O(2^n)
。
Knapsack的問題還有另外一種演算法可以解決,我們未來在介紹。
O(2^n)
。明天我們將會介紹第四個屬於Brute Force的演算法-DFS和BFS。
Exhaustive Search那裡:
可能有先問題還真的只有用這種方式反而可以更有效地取得解答 => 些
碰巧看到的xD