0-1 背包动态规划解法详解
2025-08-20 22:09:06
发布于：江西
学 0-1 背包学了不知道多久，可算给我把一维滚动数组的解法研究明白了。qwq
问题
有 个物品，给定其价值与质量，其中第 个物品的价值与质量分别记作 与 。现在要从这些物品中选取若干个（每个物品只能选一次）并放入一个背包，要求这些物品的质量之和不能超过背包的最大容量 。求能取到的最大价值和。
思路
考虑到 的时间复杂度，尝试枚举每一种选择方案找最大值并不是什么好主意。贪心无法取得全局最优解，而模拟退火相信就算我会也懒得写。因此该问题的较简便实用正解应该是使用动态规划。
定义 表示从前 个物品里挑选且背包容量为 时可取到的最大价值。显然，若背包可用容量不够取当前物品，则只能不取当前物品并继承上一个物品的最大价值；否则最大价值就是取与不取的情况的最大值。
即本题的二维状态转移方程为
在初始值上，当背包容量为 或物品数为 时，很显然总价值也为 ，于是 ， 的初始值皆为 。我们可以写出如下解法：
int Knapsack_01(int W,int prices[],int weights[],int n)
//此处记背包的最大容量为 W，共有 n 个物品 ，prices[] 存储物品价值，weights[] 存储物品质量
{
int dp[n+2][W+2];
for(int i=0;i<=n+1;i++) dp[i][0]=0;
for(int i=0;i<=W+1;i++) dp[0][i]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=W;j++)
{
if(j>=weights[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i]]+prices[i]);
///当前容量可以选第 i 件物品，则在选与不选之间取最大价值
else dp[i][j]=dp[i-1][j];
//否则只能不选第 i 件物品
}
}
return dp[n][W];
}
时间复杂度：
空间复杂度：
但是，若数据范围太大了，这种解法会 MLE。
考虑优化。我们可以让dp[][]改用short类型，但这治标不治本，若数据范围再大一些一样无法通过，某些情况下还有溢出的风险。
我们发现，在原本的状态转移方程中， 都是从 转移而来的，存储 等其他维度并的数据并不必要。于是我们可以考虑使用一维滚动数组直接省去 这个维度。
int Knapsack_01(int W,int prices[],int weights[],int n)
{
int dp[W+2];
fill(dp,dp+W+2,0);
for(int i=1;i<=n;i++)
for(int j=W;j>=weights[i];j--) dp[j]=max(dp[j],dp[j-weights[i]]+prices[i]);
return dp[W];
}
时间复杂度：
空间复杂度：
解释一下滚动数组究竟是怎么处理这些数据的。每次 的时候，当前要处理的是第 个物品的选择，而dp[]数组里存的恰好是用于转移的处理完上一个物品的数据（也就是第 个物品），于是直接用数组中已有的数据转移即可，不再需要额外存储。
为了解释为什么 要从高到低遍历，我们首先要知道，j-weights[i]的值永远不会大于当前的 。从高到低遍历时，已经转移的部分在 之上，由于j-weights[i]的值在 之下，dp[j-weights[i]]不会访问到已经转移过的部分，保证了其永远是未转移后的上一轮的状态；从低到高遍历，则此时已经转移的部分都在 以下，又因为j-weights[i]的值的范围，就会访问到已经转移的部分，进而出现错误。
注意，如果需要给出选择方案，一维滚动数组的解法会比较麻烦，建议使用二维数组的解法。
这里空空如也
有帮助，赞一个