野生前端的數(shù)據(jù)結(jié)構(gòu)練習(xí)（12）貪心算法

參考代碼可見：https://github.com/dashnowords/blogs/tree/master/Structure/GreedyAlogrithm

一.貪心算法

貪心算法屬于比較簡單的算法，它總是會(huì)選擇當(dāng)下最優(yōu)解，而不去考慮單次遞歸時(shí)是否會(huì)對(duì)未來造成影響，也就是說不考慮得到的解是否是全局最優(yōu)。在很多實(shí)際問題中，尋找全局最優(yōu)解的代價(jià)是非常大的，這時(shí)候就可以通過求次優(yōu)解來解決問題，這種思想其實(shí)在軟件工程中很常見，例如React中著名的DOM Diff算法中需要對(duì)比兩棵DOM樹，樹的完全對(duì)比時(shí)間復(fù)雜度為O(n^3)，而React團(tuán)隊(duì)通過只比較同層節(jié)點(diǎn)的策略將問題簡化為O(n)，也就是說得到的結(jié)果從全局角度來說并不一定是絕對(duì)最優(yōu)的，但是它可以在大多數(shù)情況下表現(xiàn)并不差。

下面通過幾個(gè)簡單例子來理解貪心算法（題目來自《數(shù)據(jù)結(jié)構(gòu)與算法Javascript描述》一書）。

二.貪心算法求解背包問題

貪心算法求解背包問題實(shí)際上很像人工求解，如果你是一個(gè)大盜，自己帶著背包在寶庫挑東西，總不能拿一張草稿紙出來開始動(dòng)態(tài)規(guī)劃或手動(dòng)遞歸吧，那等你求出結(jié)果來估計(jì)警察也來了，可能的做法例如：

1. 不做衡量，拿起什么放什么，放不進(jìn)去或者沒有更多東西了，然后離開。
2. 從最貴的開始挑，能放進(jìn)去就放，放不進(jìn)去就接著挑別的，最后背包塞不下更多或者沒東西了，然后離開。
3. 簡單計(jì)算一下性價(jià)比（一般可以以【價(jià)值】/【體積】來衡量），然后按性價(jià)比從高到低開始挑，能放進(jìn)去就放，放不進(jìn)去就下一個(gè)，最后背包塞不下更多或者沒東西了，離開。

這幾種方式都可以作為貪心算法的一部分參與計(jì)算，得到的結(jié)果也不一定是一樣的，但都可以認(rèn)為是一種局部最優(yōu)解，同時(shí)也可能是全局最優(yōu)解。

示例算法實(shí)現(xiàn)：

/**
 * 貪心算法求解背包問題局部最優(yōu)解
 */
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章練習(xí)題1：使用暴力技巧求解最長公共子串

3.1 題解：

暴力求解公共字符串的方法，從較短的字符串整體開始找起，逐步縮小步長，例如長字符串為long_str,較短的字符串稱為short_str,假設(shè)short_str的長度為6，先查看short_str是否整個(gè)包含在long_str中，如果是則返回，如果不是，再將步長設(shè)置為5,然后查看short_str[0,5), short_str[1,6)這兩個(gè)字符串是否在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++){
            //相當(dāng)于拿一個(gè)不斷縮短的尺子逐段截取來查看截取的片段是否被長字符串包含，
            //一旦找到則就是最長公共子串
            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章練習(xí)題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;
}

/**
 * 顯示結(jié)果
 */
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);