背包问题

河马嘴不大

发布于 2022-12-24 12:19:23

3070

发布于 2022-12-24 12:19:23

假设编号分别为a,b,c,d,e的五件物品，重量分别是2,2,6,5,4，价值分别是6,3,5,4,6，现在有一个承重为10的背包，如何装入物品具有最大价值？

首先注意的是该表是从左下开始填的，左边紫色列标示物品编号，并对应的有重量与价值，第一行标示背包重量。(b, 5)表示b、c、d、e四个物品放入大小为5的背包中的最大值。(a, 10)就是abcde五种商品放入容量为10的背包中的最大价值，这正好就是题目的答案。

现在我们开始学怎么填这张表，先随便挑一个表格(a，9)，此时背包容量为9，可以选abcde五种物品，我们要找出容量的最大值，根据上述思路分为放入物品a和不放入物品a两种情况。

情况a: 假如放入物品a, 则背包容量变为9-2=7，还剩b,c,d,e四种物品。所以该情况下的最大值 = (b,7) + 物品a的价值6，即9+6
情况b: 假如不放入物品a, 背包容量不变为9，还剩b,c,d,e四种物品。所以该情况下的最大值 = (b, 9)，即10

所以现在(a, 9) = max( (b,7)+6, b(9) ) = max(9+6，10) = 15。

同样的步骤填满其他的表格即可。

function packageMaxValue(weight, value, size){
    // 省略参数合法性校验
    let bagMatrix = []
    for(let w = 0; w <= size; w++) {
        // js不能直接创建二维数组，所以在此初始化数组
        bagMatrix[w] = []
        for (let j = 0; j < 5; j++) {
            // 背包的容量为0，那么一个东西也装不下，此时的值肯定也是为0
            if(w === 0) {
                bagMatrix[w][j] = 0
                continue
            }
            // 背包的容量小于物品j的重量，那么就没有上述情况a了
            if(w < weight[j]){
                bagMatrix[w][j] = bagMatrix[w][j-1] || 0
                continue
            }
            bagMatrix[w][j] = Math.max((bagMatrix[w-weight[j]][j-1] || 0) + value[j], bagMatrix[w][j-1] || 0)
        }
    }
    return bagMatrix
}

let weight = [4, 5, 6, 2, 2]
let value = [6, 4, 5, 3, 6]

console.log(packageMaxValue(weight, value, 10))

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-11-16，如有侵权请联系 cloudcommunity@tencent.com 删除

max