前端与算法-动态规划之01背包问题浅析与实现

去年因为工作中的某个应用场景，需要使用到动态规划，为此花了些时间啃了啃背包算法

为啥去年的东西，今年才写粗来，也许大概是懒吧

动态规划 Dynamic Programming

先简单说下什么是动态规划

引用维基百科的一句话 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法 ，通俗的理解就是，将一个复杂的问题拆解成相似的多个子问题，然后依次解决各个子问题，同时因为子问题的相似性，在计算过程中，需要同时将子问题的结果保存起来，在下一个同样的子问题时，直接查找即可，这样在同样的问题上就不会再次花费计算时间，其核心思想就是拆解与记录

那么什么情况下可以使用动态规划呢 ？ 需具备以下特征

1. 有最优子结构，如果一个问题最优的解决方案可以通过最优它的子问题的解决方案来获取，那么这个问题就有最优子结构的属性，简单的理解就是用子问题的最优解来构造原问题的最优解

2. 子问题无后效性，即子问题的解一旦算出，就不会受到后续的子问题的影响而发生改变

3. 子问题重叠性质，即每次产生的子问题都不是一个全新的问题，是在前一个子问题的基础上变化而来的，所以子问题之间需要具有重叠性，这也是动态规划高效率的一个原因

总结如下：

• 有最优解的结构
• 找到子问题
• 以“自底向上”的方式计算最优解的值
• 可以从已计算的信息中构建出最优解的路径

背包问题

先看一个场景:给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高？

那么为解决这一类问题的算法就称为背包算法。

适用于背包问题的场景需要具备以下特征

• 有一个固定容量的背包
• 商品有两个属性，体积和价值
• 求背包能容纳下的最大价值或放入的具体商品

背包问题与动态规划

我们可以将背包的容量(v)拆解，分为0到v不同的背包，那么子问题就是，容量为(0-v)的背包，我们要算出对应的各个背包所能容纳下的最大价值，聪明的小伙伴这时候一定想起了上面我们介绍的动态规划，没错！背包问题的最优解法就是动态规划，它完全符合动态规划的特征。

背包算法分类

背包算法分类主要分为三种，其他的场景是在这三种的基础上混合和扩展

1. 01背包，每种物品仅有一件，可以选择放或不放
2. 完全背包，每种物品有无限件，每种物品可以取n件
3. 多重背包，每件物品数量都是有限的

目前只了解01背包算法，下面就只针对01背包算法做介绍

01背包

01背包：有N件物品和一个容量为V的背包。每种物品均只有一件,可以选择放或不放，第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解

算法的核心是状态转移方程: f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

至于这个方程怎么得来的，暂时超粗我的能力范围啦~欢迎懂得小伙伴教教

解释一下上面的方程： f[i][v] 表示前i件物品恰放入一个容量为v的背包可以获得的最大价值，即算出子问题 f[i][v] 的解。

举个栗子，有编号分别为a,b,c,d,e的五件物品，它们的重量分别是3,6,3,8,6，它们的价值分别是4，6,6,12，10现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值

根据状态转移方程，我们先弄个表格，用于观察子问题的解

第一步， f[a][1] ，a物品放入容量为1的背包中，求其最大价值，为方便描述就简称 a1单元格，很显然放不下，那么解为0

再算 a2单元格，根据方程 f[a][2]=max{f[a-1][2],f[a-1][2-c[a]]+w[a]} = max{0,0} 可得 a2 = 0

再算 a3, 根据方程 f[a][3]=max{f[a-1][3],f[a-1][3-c[a]]+w[a]} = max{0,0+4} 可得 a3 = 4

依次算出 a行的值，接下来到b行的

f[b][1]=max{f[b-1][1],f[b-1][1-c[b]]+w[b]} = max{0,0+} 可得 b1 = 0

f[b][3]=max{f[b-1][3],f[b-1][3-c[b]]+w[b]} = max{4,0} 可得 b1 = 4

f[b][6]=max{f[b-1][6],f[b-1][6-c[b]]+w[b]} =max{f[a][6],f[a][6-6]+6} = max{4,0+6} 可得 b1 = 6

f[b][9]=max{f[b-1][9],f[b-1][9-c[b]]+w[b]} =max{f[a][9],f[a][9-6]+6} = max{4,4+6} 可得 b1 = 10

依次类推，直到把表填满

那么可以知道容量为10的背包，最大的价值为16，那么对应的是那些物品呢？可通过回溯法，找回对应的商品，从表格右下角开始找起

实例讲解-红包组合

场景

最优红包组合：用户在下单结算的时候，在用户的n多个红包中，为用户算出最优的红包组合，合并给用户一起使用，红包有两个要素：红包金额、红包最低使用金额，且组合的红包中，红包最低使用金额的总和不能大于订单金额，那么哪几个红包组合才是最大的优惠呢？该问题简单一句话概括就是：

根据下单金额 W 从 N 个红包中选出一个或多个红包，算出当前下单金额下最优的红包组合

问题分析

这是一个背包问题，满足01背包的特征，将下单金额看成是背包容量，每个红包是一个物品，物品的价值是红包的金额，物品的重量是红包的最低适用金额，子问题就是，求金额(0-w)下适用的最优红包组合

红包对象

{
    "amount": "39.00", // 红包金额-商品的价值
    "rangeBegin": "6000.00", // 红包最低适用金额-商品的重量
}
复制代码

具体代码实现如下

/**
* @description
* 01背包算法
* @private
* @param {any} dataList 红包列表 
* @param {any} all 下单金额
* @returns 
*/
private knapsack(dataList, all) {
    const returnList = [];
    for (let i = 0; i < dataList.length; i++) {
        // 构建二维数组
        returnList[i] = [];
        for (let j = 0; j < all; j++) { // 分割背包
            const currentBagWeight = j + 1; // 此时背包重量
            const currentWeight = dataList[i].rangeBegin; // 此时物品重量
            const currentValue = dataList[i].amount; // 此时的价值
            const lastW = currentBagWeight - currentWeight; // 此时背包重量减去此时要添加的物品后的重量

            // 求子问题最优解，并记录
            let fV = lastW >= 0 ? currentValue : 0;
            fV = fV + (i > 0 && returnList[i - 1][lastW - 1] ? returnList[i - 1][lastW - 1] : 0);
            const nV = i > 0 && returnList[i - 1][j] ? returnList[i - 1][j] : 0;
            returnList[i][j] = Math.max(fV, nV);
        }
    }

    // 回溯算法，算出选择的商品
    let y = all - 1;
    const selectItem = [];
    let i = dataList.length - 1;

    while (i > -1) {
        if (returnList[i][y] === (returnList[i - 1] && returnList[i - 1][y - dataList[i].rangeBegin] || 0) + dataList[i].amount) {
            selectItem.push(dataList[i]);
            y -= dataList[i].rangeBegin;
        }
        i--;
    }

    return selectItem;
}
复制代码