算法题目整理分析--背包问题反向理解

问题:给一个固定大小,能够携重W的背包以及一组有价值重量的物品,找出一个最佳的方案,使得装入包中的物品重量不超过W且总价值最大

背包问题,正常的解题思路,参考这两篇文章

JS算法之背包问题 javascript背包问题详解

答案和解题描述基本都一样,但是有个地方很模糊不好理解。我现在是想针对答案,反向理解一下。

    var weights = [2,2,6,5,4]
    var values =  [6,3,5,4,6]
    var maxWeight = 10

    function bestWeights(weights, values, w) {
        var n = weights.length - 1;//获取物品个数
        var f = [[]];//定义f的矩阵

        for (var j = 0; j <= w; j++) {
            if (j < weights[0]) {//容量当不下物品0的重量,价值为0
                f[0][j] = 0;
            } else {
                f[0][j] = values[0];//否则容量为物品0的价值
            }
        }

        for (var j = 0; j <= w; j++) {
            for (var i = 1; i <= n; i++) {
                if (!f[i]) {//创建新的一行
                    f[i] = [];
                }
                if (j < weights[i]) {//等于之前的最优值
                    f[i][j] = f[i - 1][j];
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - weights[i]] + values[i]);
                }
            }
        }
        return f[n][w];
    }
    bestWeights(weights,values, maxWeight)

首先通过第一个for循环,创建第一行是要创建一个基础比较对象。所以第一行暂时是最优解

for (var j = 0; j <= w; j++) {
    if (j < weights[0]) {//容量当不下物品0的重量,价值为0
        f[0][j] = 0;
    } else {
        f[0][j] = values[0];//否则容量为物品0的价值
    }
}

然后通过两层遍历,查询比较最优解。基本思路就是

  • 1:如果重量大于j,就说明当前物品放不进去,就用上一条的最优解
  • 2:如果重量不大于j,就有一个选择性,将当前模块放进去还是 用上一个最优解。就是这一行Math.max(f[i - 1][j], f[i - 1][j - weights[i]] + values[i])
  • f[i - 1][j - weights[i]] + values[i] 这是最核心的一段,也是最不好理解的部分。j本身代表的也是重量。j - weights[i]是将当前重量列减去 当前模块的重量。然后取上一行的对应值。 核心思路就是,如果上一行最优解的 j - weights[i] 是个大于等于0的值,说明该位置 足够放下新的 指定重量

随机浏览