AcWing 2. 01背包问题
原题链接
简单
作者:
永远热爱
,
2021-05-10 20:51:41
,
所有人可见
,
阅读 352
那个优化中的值可能不对 但是那个为什么要逆序的思想要理解
#include<iostream>
using namespace std;
const int N=1010;
int f[N],v[N],w[N];
//1 划分定义 f[i][j] 从前i个物品中选,空间是j,能装最多的钱数。
// 2 找关系 就是 f[i][j]能从哪里来 f[i][j]=f[i-1][j];代表着第i个物品要么是值0
//元要么是装不下了,f[i][j]=f[i-1][j-v[i]]+w[i] 代表着我能将第i个物品装进背包
// 3 初始化 f[i][0]=0; f[0][j]=0; 上面的f[N][N] 已经把这两种情况都包含了
int main()
{
int n,m;
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]<<endl;
//第一轮 2 3 4 5 6 7 8 9 f[7]=7;
// 第二轮 要借助上一轮的值 也就是 2 3 4 5 6 7 8 9 这其中一个但是我只有一维,如果按着顺序来
//第二轮可能是 比如f[3]=f[1]+3=5;,v[i]==2,w[i]=3;v[i]=4,w[i]=5;f[7]=f[3]+5=10;这个用到的实际上是第二轮也就是i=2时的f[3],
//但是 实际上 第二轮的值必须借助的是第一轮的值也就是f[7]=f[3]+5=9;
return 0;
}