动态规划:01背包问题
一、什么是01背包问题?
举个例子,你要去一个水果摊拿水果,每种水果都有对应的两种属性:占用的体积V和蕴含的价值W。而你的背包体积为N。老板说:每种水果只能拿一个!因此对于咱们肯定得想一种搭配方式使得拿的水果总体积不超过背包容积,但是价值总和达到最大!
核心思想:
f[i][j]:表示所有选法集合中,只从前i个物品中选,并且总体积不大于j的选法的集合,它的值是这个集合中每一个选法的最大值。
对于01背包问题选择方法的集合可以分成2种:
①不选第i个物品,并且总体积不大于j的集合所达到的最大值:f[i-1][j]
②选择1~i个物品,并且总体积不大于j的集合所达到的最大值f[i][j]
对于第二种情况我们很难计算,因此需要思考从另一个角度解决问题。当选择1~i个物品,总体积不大于j的集合的最大值可以转化成选择1~i-1个物品,总体积不大于j-V[i]的集合+最后一个物品的价值:f[i-1][j-V[i]]+w[i]
因此总结:f[i][j]= Max{f[i-1][j],f[i-1][j-v[i]]+w[i]}!!!
二、01背包例题
#ACWing 2
代码:
二维数组:
#include <iostream>
using namespace std;
const int N=1010;
int v[N],w[N],f[N][N];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
printf("%d",f[n][m]);
return 0;
}
##注意 :为什么i和j从1开始遍历,因为如果i或j不管哪个为0,f[i][j]其实都等于0!!
一维数组: 优化版
#include <iostream>
using namespace std;
const int N=1010;
int v[N],w[N],f[N];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
printf("%d",f[m]);
return 0;
}
如何优化:
从二维做法中可以看出f[i] [j]最大值的更新只用到了 f[i-1] [j],即 f[i-2][j] 到 f[0][j] 是没有用的。
所以第二层循环可以直接从v[i] 开始。
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= m; j++) {
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
二维优化到一维后:
如果删掉f[i]这一维,结果如下:如果j层循环时递增的,则是错误的
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= m; j++) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
模拟结果:
可以看出处于 i == 1 这一层,即物品只有一件,不存在单件物品满足价值为6,8,10的,所以已经出错了。
为什么一维情况下枚举背包容量需要逆序?
在二维情况下,状态f[i][j]是由上一轮i - 1的状态得来的,f[i][j]与f[i - 1][j]是独立的。而优化到一维后,如果我们还是正序,则有f[较小体积]更新到f[较大体积],则有可能本应该用第i-1轮的状态却用的是第i轮的状态。
例如,一维状态第i轮对体积为 3 的物品进行决策,则f[7]由f[4]更新而来,这里的f[4]正确应该是f[i - 1][4],但从小到大枚举j这里的f[4]在第i轮计算却变成了f[i][4]。当逆序枚举背包容量j时,我们求f[7]同样由f[4]更新,但由于是逆序,这里的f[4]还没有在第i轮计算,所以此时实际计算的f[4]仍然是f[i - 1][4]。
如果 j 层循环是逆序的:
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
模拟结果:
模拟一下发现没有错误,即逆序就可以解决这个优化的问题了
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击