js实现01背包问题

source 发布于2019-08-21 10:56 / 964人阅读

摘要：背包是动态规划中比较简单的一个问题，其中的关键在于找到状态转换方程。表示四个物品放入大小为的背包中的最大值。就是五种商品放入容量为的背包中的最大价值，这正好就是题目的答案。

01背包是动态规划中比较简单的一个问题，其中的关键在于找到状态转换方程。

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

思路分析

首先假设有一个国王且手下有大臣A和大臣B，聪明的国王将这个问题分为放入物品a和不放入物品a两种情况。然后国王告诉大臣A假如已经放了物品a, 那么剩下b,c,d,e四件商品放入大小为8的背包中的最大价值（其中8来自于总重量10减去物品a的重量2），然后再告诉大臣B假如没有放入物品a, 那么在b,c,d,e四件商品中放入大小为10的背包中的最大价值。

而国王只需要比较两个大臣的答案就可以得到最终答案。大臣A采用同样方法把任务分给手下有A1和A2两个人，大臣B同理。依次下去，即可得到最终的答案。

以上可以看出，关键步骤是将问题分解为放入物品a与不放入物品a两种情况中的最大值，并推广的所有的物品。这也是01的由来。

用图形表示出来就是下面这张表。

首先注意的是该表是从左下开始填的，左边紫色列标示物品编号，并对应的有重量与价值，第一行标示背包重量。(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。

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

代码实现

下面是方法2的js实现

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))

参考：
动态规划之01背包问题（最易理解的讲解）

GPU服务器海外云主机背包问题 java背包凑钱问题背包c语言实现 php 实现背包算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/86439.html

背包问题学习笔记

摘要：状态转移方程背包问题的状态转移方程是其中即表示前件物品恰放入一个容量为的背包可以获得的最大价值。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。 01背包 01背包的概念有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。从这个题目中可以看出，01背包的特点就是：每种物品仅有一件，可以选择放或...

xiao7cn 2019-08-20 18:05 评论0 收藏0
01背包问题（动态规划算法）

摘要：背包问题题目给定种物品和一个容量为的背包，物品的体积是，其价值为。用子问题定义状态其状态转移方程是。 P01: 01背包问题题目给定 N 种物品和一个容量为 V 的背包，物品 i 的体积是 wi，其价值为 ci 。(每种物品只有一个)问：如何选择装入背包的物品，使得装入背包中的物品的总价值最大？面对每个物品，我们只有选择放入或者不放入两种选择，每种物品只能放入一次。我们用之前同...

tuniutech 2019-08-23 10:52 评论0 收藏0
javascript算法基础之01背包，完全背包，多重背包实现

摘要：背包给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。 01背包给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。 const tList = [1, 2, 3, 4, 5] // 物品体积 const vList = [3, 4, 10, 7, 4] // 物品价值 const...

seanlook 2019-08-23 14:25 评论0 收藏0
经典动态规划--01背包问题

摘要：背包问题具体例子假设现有容量的背包，另外有个物品，分别为，，。最后，就是动态规划的思路了。而前个物体放入容量为的背包，又可以转化成前个物体放入背包的问题。背包问题具体例子：假设现有容量10kg的背包，另外有3个物品，分别为a1，a2，a3。物品a1重量为3kg，价值为4；物品a2重量为4kg，价值为5；物品a3重量为5kg，价值为6。将哪些物品放入背包可使得背包中的总价值最大？首先...

warkiz 2019-08-19 11:06 评论0 收藏0
王者编程大赛之三 — 01背包

摘要：动态规划概念动态规划过程每次决策依赖于当前状态，又随即引起状态的转移。相关文章王者编程大赛之一王者编程大赛之二蓄水池王者编程大赛之四约瑟夫环王者编程大赛之五最短路径首发于樊浩柏科学院服务目前每月会对搬家师傅进行评级，根据师傅的评级排名结果，我们将优先保证最优师傅的全天订单。 showImg(https://img3.fanhaobai.com/2017/12/2017-ziro...

Cympros 2019-07-01 12:36 评论0 收藏0