本系列文章同步分享於個人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. 將所有可能性的總負重與小背包的限重Ｗ進行比較，留下符合限重的組合。
3. 從留下的組合中找出總價值最高的組合。

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

Knapsack Algorithm的範例時間

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

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

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

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

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

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

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

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

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

小結

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

預告

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

References

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