题目介绍
01背包是背包问题中最基础,也是最重要的一个,后面很多问题的优化,都需要01背包的思想
01背包问题讲的是 有n件物品,每件物品最多选一件,且有相应的体积和价值,
在体积不超过v的情况下,使背包内物品价值最大
基本思路1
先按照y式dp分析法,分析一波
集合:f[i][j]表示在体积为j的情况下,选择i个物品,包内物品的最大价值
状态表示:
属性:max
状态计算:就是一个分类的过程,
不选第i个物品:如果不选的话直接等于f[i-1][j]
分成两部分
选第i个物品:选择第i个物品的话不好直接计算,采用曲线救国
曲线救国:
在当前体积能装下第i个物品的前提下
先算出dp[i-1][j-v[i]],再加上w[i],就得到了选第i个物品的价值最大值
代码实现1
//需要用到i-1的都从1开始使用数组
#include <iostream>
using namespace std;
const int N=1020;
int f[N][N],v[N],w[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>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]);
}
cout<<f[n][m];
}
思路优化
dp问题的优化一般都是将多维状态优化少几维,
通过分析可以发现01背包的每一项,只与前一项有关,像滚动数组
第i行的只和第i-1行有关,所以前面的可以不用存下来了
for(int j=1;j<=m;j++)
f[j]=max(f[j],f[j-v[i]]+w[i]);
如果代码写成这样j-v[i]本来应该对应的是i-1行,但是这样就会被i行的更新了
所以我们将j倒过来
代码实现2
#include <iostream>
using namespace std;
const int N=1020;
int f[N],v[N],w[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>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]);
cout<<f[m];
}