AKSZ-背包
2024-06-30 15:09:10
发布于:广东
背包问题
0/1背包模型
有一个容量为的背包,在个物品中选择一些物品装入
每一个物品有一定的价值,同时占用一定的空间
问如何选取才能保证在背包装满之前使物品总价值最大
求解思路
用v
存储各个物品的占用空间,w
存储各个物品的价值
设dp[i][j]
表示在前i
个物品中容量不超过j
时的最大价值
对于dp[i][j]
的求解方式:
有两种选择:装或不装
要是不装,则有dp[i][j]=dp[i-1][j]
(继承之前的状态)
要是装,则有dp[i][j]=dp[i-1][j-v[i]]+w[i]
(表示用这个物品占用对应的空间,并取得相应的价值)
二者取最大,则可推出状态转移方程式为:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
初始化:全部初始化为0即可
答案:dp[k][V]
另提一嘴:滚动数组优化
一种空间优化策略
观察可得,状态转移方程式只需要用到上一行
所以不妨用两行数组交替求解
代码如下:
int now=0,last=1,dp[2][maxn];
for(int i=1;i<=n;i++){
now^=1;last^=1;
for(int j=1;j<=V;j++){
if(j>=v[i])dp[now][j]=max(dp[last][j],dp[last][j-v[i]]+w[i]);
else dp[now][j]=dp[last][j];
}
}
还没完!降维打击听说过没?
直接用一维数组解决二维!
for(int i=1;i<=m;i++)for(int j=t;j>=v[i];j--){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
关键在于从右向左滚,此时左边是last
,右边是now
答案是dp[t]
无限/完全背包模型
有一个容量为的背包,在个物品中选择一些物品装入
每一个物品有一定的价值,同时占用一定的空间,且可以任意选取数量
问如何选取才能保证在背包装满之前使物品总价值最大
求解思路
用v
存储各个物品的占用空间,w
存储各个物品的价值
设dp[i][j]
表示在前i
个物品中容量不超过j
时的最大价值
对于dp[i][j]
的求解方式:
有两种选择:装或不装
要是不装,则有dp[i][j]=dp[i-1][j]
(继承之前的状态)
要是装,则有dp[i][j]=dp[
i
][j-v[i]]+w[i]
(表示用这个物品占用对应的空间,并取得相应的价值)
二者取最大,则可推出状态转移方程式为:
dp[i][j]=max(dp[i-1][j],dp[
i
][j-v[i]]+w[i])
初始化:全部初始化为0即可
答案:dp[k][V]
区别:是dp[i]
不是dp[i-1]
啊!
滚动数组优化代码
两行:
for(int i=1;i<=m;i++){
now^=1;last^=1;
for(int j=1;j<=t;j++){
if(j>=v[i])dp[now][j]=max(dp[last][j],dp[now][j-v[i]]+w[i]);
else dp[now][j]=dp[last][j];
}
}
单行:从左往右滚就行
for(int i=1;i<=m;i++)for(int j=v[i];j<=m;j++){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
这里空空如也
有帮助,赞一个