野生前端的資料結構練習（12）貪心演算法
參考程式碼可見： GreedyAlogrithm" rel="nofollow,noindex" target="_blank">https://github.com/dashnowords/blogs/tree/master/Structure/GreedyAlogrithm
一.貪心演算法
貪心演算法 屬於比較簡單的演算法，它總是會選擇當下最優解，而不去考慮單次遞迴時是否會對未來造成影響，也就是說不考慮得到的解是否是 全域性最優 。在很多實際問題中，尋找全域性最優解的代價是非常大的，這時候就可以通過求次優解來解決問題，這種思想其實在軟體工程中很常見，例如 React 中著名的 DOM Diff 演算法中需要對比兩棵DOM樹，樹的完全對比時間複雜度為 O(n^3) ，而React團隊通過只比較同層節點的策略將問題簡化為 O(n) ，也就是說得到的結果從全域性角度來說並不一定是絕對最優的，但是它可以在大多數情況下表現並不差。
下面通過幾個簡單例子來理解 貪心演算法 （題目來自 《資料結構與演算法Javascript描述》 一書）。
二.貪心演算法求解揹包問題
貪心演算法求解揹包問題實際上很像人工求解，如果你是一個大盜，自己帶著揹包在寶庫挑東西，總不能拿一張草稿紙出來開始動態規劃或手動遞迴吧，那等你求出結果來估計警察也來了，可能的做法例如：
- 不做衡量，拿起什麼放什麼，放不進去或者沒有更多東西了，然後離開。
- 從最貴的開始挑，能放進去就放，放不進去就接著挑別的，最後揹包塞不下更多或者沒東西了，然後離開。
- 簡單計算一下價效比（一般可以以【價值】/【體積】來衡量），然後按價效比從高到低開始挑，能放進去就放，放不進去就下一個，最後揹包塞不下更多或者沒東西了，離開。
這幾種方式都可以作為貪心演算法的一部分參與計算，得到的結果也不一定是一樣的，但都可以認為是一種區域性最優解，同時也可能是全域性最優解。
示例演算法實現：
/**
* 貪心演算法求解揹包問題區域性最優解
*/
function ksack(values, weights, capacity, n) {
var load = 0;
var i =0;
var w = 0;
while (load < capacity && i < n){
if(weights[i] <= (capacity-load)){
w += values[i];
load += weights[i];
}else{
var r = (capacity - load) / weights[i];
w += r * values[i];
load += weights[i];
}
i++;
}
return w;
}
var items = ["A","B","C","D"];
var values = [50, 140, 60 ,60];
var weights = [5, 20, 10, 12];
var n = 4;
var capacity = 30;
console.log(ksack(values,weights, capacity, n))
三.最長公共子串
書中第14章練習題1：使用暴力技巧求解最長公共子串
3.1 題解：
暴力求解公共字串的方法，從較短的字串整體開始找起，逐步縮小步長，例如長字串為 long_str ,較短的字串稱為 short_str ,假設 short_str 的長度為6，先檢視 short_str 是否整個包含在 long_str 中，如果是則返回，如果不是，再將步長設定為5,然後檢視 short_str[0,5) , short_str[1,6) 這兩個字串是否在 long_str 中，以此類推，過程和找零問題很相似。
3.2 參考程式碼：
/**
* 貪心演算法尋找公共子串
*/
function greedy_lsc(str1, str2) {
//保證str2是長度較短的序列
if (str1.length < str2.length) {
let temp = str1;
str1 = str2;
str2 = temp;
}
let stepLength = str2.length;
//從長到短列舉
while(stepLength >= 0){
for(let i = 0; i < str2.length - stepLength; i++){
//相當於拿一個不斷縮短的尺子逐段擷取來檢視擷取的片段是否被長字串包含，
//一旦找到則就是最長公共子串
let checking = str2.slice(i, i+stepLength);
if (contains(str1,checking)) {
return checking;
}
}
stepLength--;
}
}
//str2是否是str1的子串
function contains(str1, str2) {
return str1.indexOf(str2) !== -1;
}
//測試
let str1 = 'aabcdefsssefce';
let str2 = 'abssefsssse';
console.log(greedy_lsc(str1,str2));
四.找零問題
書中第14章練習題3：使用貪心演算法求解找零問題，要求不能用10美分，需要找零30美分。
4.1 題解：
書中有例題，沒什麼難度，就不展開講了，僅提供參考程式碼。
4.2 參考程式碼：
/**
* 貪心演算法求解零錢問題
* 要求：不能使用10美分
*/
function makeChange(money, coins) {
let remain = money;
if (remain / 25 > 0) {
coins[2] = parseInt(remain / 25, 10);
remain = remain - coins[2]*25;
}
if (remain / 5 > 0) {
coins[1] = parseInt(remain / 5 , 10);
remain = remain - coins[1]*5;
}
coins[0] = remain;
}
/**
* 顯示結果
*/
function showChange(coins) {
if (coins[2] > 0) {
console.log('25美分-' + coins[2]);
}
if (coins[1] > 0) {
console.log('5美分-' + coins[1]);
}
if (coins[0] > 0) {
console.log('1美分-' + coins[0]);
}
}
var origAmt = 30;
var coins = [];
makeChange(origAmt, coins);
showChange(coins);