动态规划

是一种将复杂问题分解成更小的子问题来解决的优化技术。

用动态规划解决问题时，要遵循三个重要步骤：

（1）、定义子问题

（2）、实现要反复执行来解决子问题的部分

（3）、识别并求解出边界条件\

1、最少硬币找零问题

最少硬币找零问题是给出要找零的钱数，以及可用的硬币面额d1…dn及其数量，找到所需最少的硬币个数。

例如：有以下面额（硬币）：d1=1,d2=5,d3=10,d4=25

如果要找36美分的零钱，我们可以用1个25、1个10、1个1美分。

下面将这个解答转化成算法:

function MinCoinChange(coins_) {
    let coins = coins_;
    let cache = {};
    this.makeChange = function(amount) {
        let me = this;
        if(!amount) {
            return [];
        }
        if(cache[amount]) {
            return cache[amount];
        }
        let min = [], newMin, newAmount;
        for(let i = 0; i<coins.length; i++) {
            let coin = coins[i];
            newAmount = amount - coin;
            if(newAmount >= 0) {
                newMin = me.makeChange(newAmount);
            }
            if(newAmount >= 0 && 
                (newMin.length < min.length - 1 || !min.length ) &&
                (newMin.length || !newAmount) 
            ) {
                min = [coin].concat(newMin);
            }
        }
        return cache[amount] = min;
    }
}
var minCoinChange = new MinCoinChange([1,5,10,25]);
console.log(minCoinChange.makeChange(36));

2、背包问题

背包问题是一个组合优化问题。描述如下：给定一个固定大小、能够携重W的背包，以及一组有价值和重量的物品。

在物品不重复情况下，找出一个最佳解决方案，使得装入背包的物品总重量不超过W，且总价值最大。

比如：
糖果：重量2 价值3，饼干：重量3 价值4，牛奶：重量4 价值5。

考虑背包只能携带重量只有5。对于这个例子，最佳方案是往背包里装糖果和饼干，这样，总重量为5，总价值为7。
转化为算法如下（返回的是价值量）：

function knapSack(capacity, weights, values, n) {
    let i, w, a, b, kS = [];
    for(i = 0; i <= n; i++) {
        kS[i] = [];
    }
    for(i = 0; i <= n; i++) {
        for(w = 0; w <= capacity; w++) {
            if(i == 0 || w == 0) {
                kS[i][w] = 0;
            } else if (weights[i-1] <= w) {
                a = values[i-1] + kS[i-1][w-weights[i-1]];
                b = kS[i-1][w];
                kS[i][w] = (a > b) ? a : b;
            } else {
                kS[i][w] = kS[i-1][w];
            }
        }
    }
    findValues(n, capacity, kS, weights, values);
    return kS[n][capacity];
}
let findValues = (n, capacity, kS, weights, values) => {
    let i = n, k = capacity;
    console.log('解决方案包含以下物品');
    while(i > 0 && k > 0) {
        if(kS[i][k] !== kS[i-1][k]) {
            console.log('物品' + i + '，重量:' + weights[i-1] + ',价值:' + values[i-1]);
            i--;
            k = k - kS[i][k];
        } else {
            i--;
        }
    }
}
let values = [3,4,5],
    weights = [2,3,4],
    capacity = 6,
    n = values.length;
console.log(knapSack(capacity, weights, values, n));

二、贪心算法

贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择（当前最好的解）。从而达到全局最优。它不像DP（动态规划）那样计算更大的格局。

我们来看看如何用贪心算法解决“最少硬币找零问题”和“背包问题”。

1、最少硬币找零问题

用贪心算法解决。大部分情况下的结果是最优的，不过对有些面额而言，结果不会是最优的。

function MinCoinChange(coins_) {
    let coins = coins_;
    this.makeChange = function(amount) {
        let change = [],
            total = 0;
        for(let i = coins.length; i >= 0; i--) {
            let coin =coins[i];
            while (total + coin <= amount) {
                change.push(coin);
                total += coin;
            }
        }
        return change;
    };
}

不得不说贪心版本比DP简单多了。

这个解法很简单，从最大面额的硬币开始，拿尽可能多的这种硬币找零。当无法再拿更多这种价值的硬币时，开始拿第二大价值的硬币，依次继续.

1 2	let minCoinChange = new MinCoinChange([1,5,18,25]); console.log(minCoinChange.makeChange(36)); // [25,10,1]

然而，因为是从最大面额开始，如果上面面额改为[1,5,18,25]。会得到结果[25,5,5,1]，如果用DP的解法，会得到最优结果[18,18]

2、分数背包问题

分数背包问题和DP的稍有不同。分数背包问题中，我们可以装入分散的物品。

比如：我们考虑的容量为6的情况下，DP返回的是8，分数背包返回的是8.25。

function knapSack(capacity, weights, values, n_) {
    let n  = n_,
    load = 0, i = 0, val = 0;
    for(i = 0; i < n && load <= capacity; i++) {
        if(weights[i] <= (capacity - load)) {
            val += values[i];
            load += weights[i];
            console.log(i, val);
        } else {
            let r = (capacity - load) / weights[i];
            val += r * values[i];
            load += weights[i];
            console.log(i);
        }
    }
    return val;
}
let values = [3,4,5],
    weights = [2,3,4],
    capacity = 6,
    n = values.length;
console.log(knapSack(capacity, weights, values, n));

主要就是如果物品不能完整装入背包，计算能够装入部分的比例。

结语：一个程序猿还是需要掌握一点算法知识，这是不会错的。