01背包问题js解法

最新推荐文章于 2025-04-07 13:20:53 发布

G1useppE

最新推荐文章于 2025-04-07 13:20:53 发布

阅读量1.8k

点赞数

分类专栏：算法文章标签：动态规划 leetcode 算法

本文链接：https://blog.csdn.net/G1useppE/article/details/124609355

版权

算法专栏收录该内容

20 篇文章

订阅专栏

本文介绍了使用JavaScript解决01背包问题的思路和代码实现。通过动态规划算法，找到背包中物品价值最大化的组合。当背包容量小于物品重量时，不放入该物品，确保最优解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目：

有N件物品和⼀个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能⽤⼀次，求解将哪些物品装⼊背包⾥物品价值总和最⼤。

背包最⼤重量为4。物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问背包能背的物品最⼤价值是多少？

代码：

let weight = [1,3,4]
let value = [15,20,30]
let bagWeight = 4

function bagProblem(weight,value,bagWeight) {
    const dp = new Array(weight.length+1).fill(0).map(()=>new Array(bagWeight+1).fill(0))
    for(let j = weight[0] ; j <= bagWeight ; j++) {
        dp[0][j] = value[0]
    }
    for(let j = 0 ; j <= bagWeight ; j++) {
        for(let i = 1 ; i < weight.length ; i++) {
            if(j < weight[i]) {
                dp[i][j] = dp[i-1][j]
            }else {
                dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
            }
        }
    }
    return dp[weight.length-1][bagWeight]
}

console.log(bagProblem(weight,value,bagWeight))  //35

注意事项：

1.先遍历物品和背包重量都可以，对结果没有影响；

2.当j小于weight[i]时，此时说明背包容量的大小小于物体重量，放不下，因此背包存放的最大价值dp[i][j]就等于没放入这个物体时的最大价值dp[i-1][j];

3.for(let j = weight[0] ; j <= bagWeight ; j++) { dp[0][j] = value[0] } 初始化的意思就是：

dp[0][j] ，即： i 为 0 ，存放编号 0 的物品的时候，各个容量的背包所能存放的最⼤价值。

那么很明显当 j < weight[0] 的时候， dp[0][j] 应该是 0 ，因为背包容量⽐编号 0 的物品重量还⼩。

当 j >= weight[0] 是， dp[0][j] 应该是 value[0] ，因为背包容量放⾜够放编号 0 物品。