前端javascript实现01背包问题
2024-03-05 本文已影响0人
一一秋风
01背包问题是背包问题中最简单最基础的一类问题，问题描述如下：给定一组物品，每个物品都有两个属性：价值和重量。同时，存在一个背包，该背包有一个固定的容量限制。每个物品只有一个，可以选择放入背包或不放入背包。目标是确定哪些物品应该放入背包中，以便背包中物品的总价值最大，同时不超过背包的容量限制。
01背包问题是一个经典的动态规划问题，其解决方法通常采用动态规划算法。在动态规划算法中，我们定义一个二维数组dp，其中dp[i][j]表示在前i个物品中，容量为j的背包所能装下的最大价值。根据问题的约束条件，我们可以得到状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
其中，dp[i-1][j]表示不将第i个物品放入背包时的最大价值，dp[i-1][j-weight[i]] + value[i]表示将第i个物品放入背包时的最大价值。因此，dp[i][j]的值就是这两种情况中的较大值。
通过填充dp数组，我们可以得到最终的解，即dp[n][W]，其中n是物品的数量，W是背包的容量限制。该值表示在给定物品和背包容量限制下，能够装入背包的物品的最大价值。
总的来说，01背包问题是一个典型的优化问题，通过动态规划算法可以在多项式时间内得到最优解。同时，它也是动态规划算法中的一个经典案例，对于理解动态规划算法的思想和应用具有重要意义。
假设有三个物品啊，a,b,c，a价值3重量2； b价值5重量3； c价值6重量4;当前有一个背包为6的书包，问最多能背多少价值的物品，并求出所背的物品组合。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
let weight = [2,3,4];
let value = [3,5,6];
let bagWeight = 6;
function bagProblem(weight,value,bagWeight){
const dp = new Array(weight.length).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-weight[i]]+value[i],dp[i-1][j])
}
}
}
return dp
}
function getYou(dp){
let x = new Array(weight.length).fill(0);
let temp=bagWeight
for(let i=weight.length-1;i>0;i--){
if(dp[i][temp] == dp[i-1][temp]){
x[i]=0;
}else{
x[i]=1;
temp=temp-weight[i]
}
}
if(dp[0][temp] == 0 ){
x[0]=0
} else{
x[0]=1;
}
return x;
}
console.log(bagProblem(weight,value,bagWeight))
console.log(getYou(bagProblem(weight,value,bagWeight)))
</script>
</body>
</html>
111.png
所以最大可以背的价值为9，为背ac两件物品
