✳flâneur — a map of the web's best reading

Knapsack Problem - 演算法筆記

web.ntnu.edu.tw · 2,292 words · saved by 1 readers

背包問題是「最佳化」問題。我們可以用各種最佳化演算法，快速求得近似解，例如「 Linear Programming 一次規劃」、「 Genetic Algorithm 基因演算法」。不過這已經脫離本篇文章的主旨了，就請讀者自行研究吧！

knapsack problem - 演算法筆記 knapsack problem knapsack problem 將一群物品儘量塞進背包裡面，令背包裡面的物品總價值最高。背包沒有容量限制，無論物品是什麼形狀大小，都能塞進背包；但是背包有重量限制，如果物品太重，就會撐破背包。 以數學術語來說，背包問題就是選擇一個最理想的物品子集合，在符合重量限制的前提下、求得最大的利益！ 背包問題有很多變形，接下來將會一一介紹。 fractional knapsack problem fractional knapsack problem fractional是「分數」的意思。一個物品可以切下一部分、只取幾分之幾放進背包。 我們很容易就可以制定一個greedy策略：價值與重量的比值最高的物品，優先放進背包。 總是用當下最好的物品填滿背包空隙，最後沒有留下任何空隙。每一份背包空間，都是最有價值的物品，就算是交換物品也無法增加總價值──顯然是最佳解。 時間複雜度O(N)。N是物品數量。 0/1 knapsack problem 0/1 knapsack problem 「0/1」的意思是：每種物品只會放進背包零個或一個。一個物品要嘛整個不放進背包、要嘛整個放進背包。物品無法切割。 大家看到這個問題，第一個直覺通常是貪心法：優先挑選價值最高的物品。然而，價值高的物品，放進背包之後，有可能留下很大的空隙

Explore this link on the map →

related reading