JavaScript算法模式——动态规划和贪心算法

  • 时间:
  • 浏览:0

  动态规划(Dynamic Programming,DP)是两种将复杂化问题报告 报告 分解成更小的子问题报告 报告 来防止的优化算法。下面有某些用动态规划来防止实际问题报告 报告 的算法:

最少 硬币找零

  给定一组硬币的面额,以及要找零的钱数,计算出符合找零钱数的最少 硬币数量。这俩,美国硬币面额有1、5、10、25这两种面额,肯能要找36美分的零钱,则得出的最少 硬币数应该是有另一个25美分、有另一个10美分和有另一个1美分共有另一个硬币。你这俩 算法要防止的好多好多 诸都可不可不都可以 类的问题报告 报告 。亲戚亲戚大家儿来看看何如用动态规划的最好的法律妙招来防止。

  对于每两种面额,亲戚亲戚大家儿都分别计算所需用的硬币数量。具体算法如下:

  1. 肯能删改用1美分的硬币,一共需用36个硬币
  2. 肯能用5美分的硬币,则需用7个5美分的硬币 + 有另一个1美分的硬币 = 8个硬币
  3. 肯能用10美分的硬币,则需用另一个10美分的硬币 + 有另一个5美分的硬币 + 有另一个1美分的硬币 = 另一个硬币
  4. 肯能用25美分的硬币,则需用有另一个25美分的硬币 + 有另一个10美分的硬币 + 有另一个1美分的硬币 = 另一个硬币

  对应的示意图如下:

  方案4的硬币总数最少 ,有日后 为最优方案。

  具体的代码实现如下:

function minCoinChange(coins, amount) {
    let result = null;
    if (!amount) return result;

    const makeChange = (index, value, min) => {
        let coin = coins[index];
        let newAmount = Math.floor(value / coin);
        if (newAmount) min[coin] = newAmount;
        if (value % coin !== 0) {
            makeChange(--index, value - coin * newAmount, min);
        }
    };

    const arr = [];
    for (let i = 0; i < coins.length; i++) {
        const cache = {};
        makeChange(i, amount, cache);
        arr.push(cache);
    }

    console.log(arr);
    let newMin = 0;
    arr.forEach(item => {
        let min = 0;
        for (let v in item) min += item[v];
        if (!newMin || min < newMin) {
            newMin = min;
            result = item;
        }
    });
    return result;
}

  函数minCoinChange()接收一组硬币的面额,以及要找零的钱数。亲戚亲戚大家儿将里面例子中的值传入:

const result = minCoinChange2([1, 5, 10, 25], 36);
console.log(result);

  得到如下结果:

[
  { '1': 36 },
  { '1': 1, '5': 7 },
  { '1': 1, '5': 1, '10': 3 },
  { '1': 1, '10': 1, '25': 1 }
]
{ '1': 1, '10': 1, '25': 1 }

  里面的数组是亲戚亲戚大家儿在代码中打印出来的arr的值,用来展示两种不同面额的硬币作为找零硬币时,实际所需用的硬币种类和数量。最终,亲戚亲戚大家儿会计算arr数组中硬币总数最少 的那个方案,作为minCoinChange()函数的输出。

  当然在实际应用中,亲戚亲戚大家儿可不可不都可以把硬币抽象成任何你需用的数字,你这俩 算法能给出你满足结果的最小组合。

背包问题报告 报告

  背包问题报告 报告 是有另一个组合优化问题报告 报告 ,它被描述为:给定有另一个具有固定容量的背包capacity,以及一组具有价值(value)和重量(weight)的物品,找出有另一个最优方案,使得装在背包的物品的总重量不超过capacity,且总价值最大。

  假设亲戚亲戚大家儿有以下物品,且背包的总容量为5:

物品# 重量 价值
1 2 3
2 3 4
3 4 5

  亲戚亲戚大家儿用矩阵来防止你这俩 问题报告 报告 。首先,亲戚亲戚大家儿把物品和背包的容量组成如下矩阵:

物品(i)/重量(w) 0 1 2 3 4 5
0 0 0 0 0 0 0
1 (w=2, v=3) 0 0

a: 3+[0][2-2]=3+0

b: [0][2]=0

max(3+0,0)=3

a: 3+[0][3-2]=3+0

b: [0][3]=0

max(3+0,0)=3

a: 3+[0][4-3]=3+0

b: [0][4]=0

max(3+0,0)=3

a: 3+[0][5-3]=3+0

b: [0][5]=0

max(3+0,0)=3

2 (w=3, v=4) 0 0 3

a: 4+[1][3-3]=4+0

b: [1][3]=3

max(4+0,3)=4

a: 4+[1][4-3]=4+0

b: [1][4]=3

max(4+0,3)=4

a: 4+[1][5-3]=4+3

b: [1][5]=3

max(4+3,3)=7

3 (w=4, v=5) 0 0 3 4

a: 5+[2][4-4]=5+0

b: [2][4]=4

max(5+0,4)=5

a: 5+[2][5-4]=5+0

b: [2][5]=7

max(5+0,7)=7

  为了便于理解,亲戚亲戚大家儿将矩阵kS的第一列和第一行忽略(肯能它们表示的是容量0和第0个物品)。有日后 ,按照要求往矩阵的格子里填数。肯能当前的格子能放下对应的物品,存在以下两种请况:

  • a - 装在当前物品,有日后 剩余的重量再装在前有另一个物品
  • b - 不装在当前物品,装在前有另一个物品

  在里面的表格中,

  1. 当背包的重量为1时,都可不可不都可以 物品能装在,好多好多 也有0,你这俩 很好理解。
  2. 当背包的重量为2时,物品1可不可不都可以装在,都可不可不都可以 存在两种请况:装在物品1(价值为3),剩余的重量(背包的重量2减去物品1的重量2,结果为0)再装在前有另一个物品;不装在物品1,装在前有另一个物品[0][2],价值为0。好多好多 最大价值好多好多 max(3, 0)=3。
  3. ......
  4. 当背包的重量为5时,装在物品2,两种请况:装在物品2(价值为4),剩余的重量(背包的重量5减去物品2的重量3,结果为2)再装在前有另一个物品,是[1][2],对应的价值是3;不装在物品2,,装在前有另一个物品[1][5],价值为3。好多好多 最大价值好多好多 max(4+3, 3)=7。
  5. ......

  肯能当前物品都可不可不都可以装在背包,则忽略它,用前有另一个值代替。亲戚亲戚大家儿可不可不都可以按照里面描述的过程把剩余的格子都填满,另有另一个表格中最后有另一个单元格里的值好多好多 最优方案。

  下面是具体的实现代码:

function knapSack(capacity, weights, values, n) {
    const kS = [];

    // 将ks初始化为有另一个空的矩阵
    for (let i = 0; i <= n; i++) {
        kS[i] = [];
    }

    for (let i = 0; i <= n; i++) {
        for (let w = 0; w <= capacity; w++) {
            // 忽略矩阵的第1列和第1行
            if (i === 0 || w === 0) {
                kS[i][w] = 0;
            }
            else if (weights[i - 1] <= w) {
                const a = values[i - 1] + kS[i - 1][w - weights[i - 1]];
                const b = kS[i - 1][w];
                kS[i][w] = Math.max(a, b);
            }
            else {
                kS[i][w] = kS[i - 1][w];
            }
        }
    }

    console.log(kS);
}

  对于const a,其价值分为两每种,第一每种好多好多 它被委托人的价值(values[i - 1]),第二每种是用背包剩余的重量(w - weights[i - 1])装在前有另一个物品(kS[i - 1])。对于const b,好多好多 找前有另一个能装在你这俩 重量的物品(kS[i - 1][w])。有日后 取这两种请况下的最大值。

  测试一下knapSack()函数,

const capacity = 5;
const weights = [2, 3, 4];
const values = [3, 4, 5];
knapSack(capacity, weights, values, weights.length);

  下面是矩阵kS的输出结果:

[
  [ 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 3, 3, 3, 3 ],
  [ 0, 0, 3, 4, 4, 7 ],
  [ 0, 0, 3, 4, 5, 7 ]
]

 最长公共子序列(LCS)

  找出有另一个字符串序列的最长子序列的长度。所谓最长子序列,是指有另一个字符串序列中以相同顺序老出,但无须求连续的字符串序列。这俩下面有另一个字符串:

  字符串1:acbaed

  字符串2:abcadf

  则LCS为acad。

  和背包问题报告 报告 的思路这俩,亲戚亲戚大家儿用下面的表格来描述整个过程:

    a b c a d f
  0 0 0 0 0 0 0
a 0 1 1 1 1 1 1
c 0 1 1 2 2 2 2
b 0 1 2 2 2 2 2
a 0 1 2 2 3 3 3
e 0 1 2 2 3 3 3
d 0 1 2 2 3 4 4

  矩阵的第一行和第一列都被设置为0,剩余的每种,遵循下面两种请况:

  • 肯能wordX[i - 1]和wordY[j - 1]相等,则矩阵对应的单元格的值为单元格[i - 1][j - 1]的值加1。
  • 肯能wordX[i - 1]和wordY[j - 1]不相等,则找出单元格[i - 1][j]和单元格[i][j - 1]之间的最大值。

  下面是具体的实现代码:

function lcs(wordX, wordY) {
    const m = wordX.length;
    const n = wordY.length;
    const l = [];
    for (let i = 0; i <= m; i++) {
        l[i] = [];
        for (let j = 0; j <= n; j++) {
            l[i][j] = 0;
        }
    }
    for (let i = 0; i <= m; i++) {
        for (let j = 0; j <= n; j++) {
            if (i === 0 || j === 0) {
                l[i][j] = 0;
            } else if (wordX[i - 1] === wordY[j - 1]) {
                l[i][j] = l[i - 1][j - 1] + 1;
            } else {
                const a = l[i - 1][j];
                const b = l[i][j - 1];
                l[i][j] = Math.max(a, b);
            }
        }
    }
    console.log(l);
    console.log(l[m][n]);
}

  亲戚亲戚大家儿将矩阵打印出来,结果如下:

const wordX = ['a', 'c', 'b', 'a', 'e', 'd'];
const wordY = ['a', 'b', 'c', 'a', 'd', 'f'];
lcs(wordX, wordY);
[
  [ 0, 0, 0, 0, 0, 0, 0 ],
  [ 0, 1, 1, 1, 1, 1, 1 ],
  [ 0, 1, 1, 2, 2, 2, 2 ],
  [ 0, 1, 2, 2, 2, 2, 2 ],
  [ 0, 1, 2, 2, 3, 3, 3 ],
  [ 0, 1, 2, 2, 3, 3, 3 ],
  [ 0, 1, 2, 2, 3, 4, 4 ]
]
4

   矩阵中最后有另一个单元格的值为LCS的长度。那何如计算出LCS的具体内容呢?亲戚亲戚大家儿可不可不都可以设计有另一个相同的solution矩阵,用来做标记,肯能wordX[i - 1]和wordY[j - 1]相等,则将solution矩阵中对应的值设置为'diagonal',即里面表格中背景为灰色的单元格。有日后 ,根据[i][j]和[i - 1][j]不是相等标记为'top'或'left'。有日后 通过printSolution()最好的法律妙招来找出LCS的内容。修改事先 的代码如下:

function printSolution(solution, wordX, m, n) {
    let a = m;
    let b = n;
    let x = solution[a][b];
    let answer = '';
    while (x !== '0') {
        if (solution[a][b] === 'diagonal') {
            answer = wordX[a - 1] + answer;
            a--;
            b--;
        } else if (solution[a][b] === 'left') {
            b--;
        } else if (solution[a][b] === 'top') {
            a--;
        }
        x = solution[a][b];
    }
    return answer;
}

function lcs(wordX, wordY) {
    const m = wordX.length;
    const n = wordY.length;
    const l = [];
    const solution = [];
    for (let i = 0; i <= m; i++) {
        l[i] = [];
        solution[i] = [];
        for (let j = 0; j <= n; j++) {
            l[i][j] = 0;
            solution[i][j] = '0';
        }
    }
    for (let i = 0; i <= m; i++) {
        for (let j = 0; j <= n; j++) {
            if (i === 0 || j === 0) {
                l[i][j] = 0;
            } else if (wordX[i - 1] === wordY[j - 1]) {
                l[i][j] = l[i - 1][j - 1] + 1;
                solution[i][j] = 'diagonal';
            } else {
                const a = l[i - 1][j];
                const b = l[i][j - 1];
                l[i][j] = Math.max(a, b);
                solution[i][j] = l[i][j] === l[i - 1][j] ? 'top' : 'left';
            }
        }
    }

    return printSolution(solution, wordX, m, n);
}

  测试结果:

const wordX = ['a', 'c', 'b', 'a', 'e', 'd'];
const wordY = ['a', 'b', 'c', 'a', 'd', 'f'];
console.log(lcs(wordX, wordY)); // acad

   贪心算法遵循两种近似防止问题报告 报告 的技术,期盼通过每个阶段的局部最优选折 ,从而达到全局的最优。它不像动态规划算法那样计算更大的格局。

最少 硬币找零

  亲戚亲戚大家儿来看看何如用贪心算法防止前面提到过的最少 硬币找零问题报告 报告 。

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

const result = minCoinChange([1, 5, 10, 25], 36);
console.log(result); // [ 25, 10, 1 ]

  前提是coins数组肯能按从小到大排好序了,贪心算法从最大值日后日后刚现在开始尝试,肯能该值不满足条件(要找零的钱数),则继续向下找,直到找到满足条件的所有值。以上算法无须能满足所有请况下找出最优方案,这俩下面你这俩 请况:

const result = minCoinChange([1, 2, 5, 9, 10], 18);
console.log(result); // [ 10, 5, 2, 1 ]

  给出的结果[10, 5, 2, 1]无须是最优方案,最优方案应该是[9, 9]。

  与动态规划相比,贪心算法更简单、速率更高。有日后 其结果无须有另总是最理想的。有日后 综合看来,它相对执行时间来说,输出有另一个可不可不都可以接受的结果。

背包问题报告 报告

物品# 重量 价值
1 2 3
2 3 4
3 4 5

  在动态规划的例子里,假定背包的容量为5,最佳方案是往背包装在入物品1和物品2,总价值为7。在贪心算法中,亲戚亲戚大家儿需用考虑分数的请况,假定背包的容量为6,装在物品1和物品2事先 ,剩余容量为1,可不可不都可以装在1/4的物品3,总价值为3+4+0.25×5=8.25。亲戚亲戚大家儿来看看具体的实现代码:

function knapSack(capacity, weights, values) {
    const n = values.length;
    let load = 0;
    let val = 0;
    for (let i = 0; i < n && load < capacity; i++) {
        if (weights[i] <= capacity - load) {
            val += values[i];
            load += weights[i];
            console.log(`物品${i + 1},重量:${weights[i]},价值:${values[i]}`);
        } else {
            const r = (capacity - load) / weights[i];
            val += r * values[i];
            load += weights[i];
            console.log(`物品${i + 1}的${r},重量:${r * weights[i]},价值:${val}`);
        }
    }

    return val;
}

  从第有另一个物品日后日后刚现在开始遍历,肯能总重量小于背包的容量,则继续迭代,装在物品。肯能物品可不可不都可以删改地装在背包,则将其价值和重量分别计入到变量val和load中,共同打印装在物品的信息。肯能物品都可不可不都可以删改地装在背包,计算都都可不可不都可以装在的比例r,有日后 将你这俩 比例所对应的价值和重量分别计入到变量val和load中,共同打印物品的信息。最终输出总的价值val。下面是测试结果:

const capacity = 6;
const weights = [2, 3, 4];
const values = [3, 4, 5];
console.log(knapSack(capacity, weights, values));
物品1,重量:2,价值:3
物品2,重量:3,价值:4
物品3的0.25,重量:1,价值:8.25
8.25

  在动态规划算法中,肯能将背包的容量也设定为6,计算结果则为8。

最长公共子序列(LCS)

  最后亲戚亲戚大家儿再来看看何如用贪心算法防止LCS的问题报告 报告 。下面的代码返回了有另一个给定数组中的LCS的长度:

function lcs(wordX, wordY, m = wordX.length, n = wordY.length) {
    if (m === 0 || n === 0) {
        return 0;
    }
    if (wordX[m - 1] === wordY[n - 1]) {
        return 1 + lcs(wordX, wordY, m - 1, n - 1);
    }
    const a = lcs(wordX, wordY, m, n - 1);
    const b = lcs(wordX, wordY, m - 1, n);
    return a > b ? a : b;
}

const wordX = ['a', 'c', 'b', 'a', 'e', 'd'];
const wordY = ['a', 'b', 'c', 'a', 'd', 'f'];
console.log(lcs(wordX, wordY)); // 4