AcWing 2. 01背包问题
原题链接
简单
作者:
永远热爱
,
2021-05-10 19:53:08
,
所有人可见
,
阅读 276
#include<iostream>
using namespace std;
const int N=1010;
int f[N][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=1;j<=m;j++)
{
if(j>=v[i]) //如果第i块石头能够放在背包,我不确定他放在背包里面就一定是最大的,因为我放在了背包里面就可能会使我必须放弃前面的空间,但是我前面空间所装的石头的价值可能比装了这一石头的价值高所以取max
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); //这个必须要求最大值max 比如题目中f[3][3]如果不取max,就是4,如果取了max,就是6; 如果我放第三个也就是3 那么我的钱是4,如果我不放3,我的钱就是6;
else // 如果放不进去 那么背包中前i-1件物品值的钱与前i件物品一样
f[i][j]=f[i-1][j];
}
}
cout<<f[n][m]<<endl;
return 0;
}