陈柏诚 • 2年前
#include <bits/stdc++.h>
using namespace std;
int m,n,w[1001],c[1001];
//这里是二维数组版本来做0/1背包
int f[1001][1001];
//f[x][y]中,x是物品数量,y是重量。f[x][y]是指在数量为x,重量为y的情况下,最大价值
int main()
{
cin>>m>>n;
for(int i=1; i<=n; i++)
{
scanf("%d%d",&w[i],&c[i]);
//输入重量和价值
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
//从重量和数量都为一开始枚举,之后不断累积
if(j>=w[i]) //保证枚举的重量符合条件,不符合就不选,符合才选(所以叫0/1背包)
{
f[i][j]=max(f[i-1][j-w[i]]+c[i],f[i-1][j]);//符合的话还要从选和不选再选最大值
}
else
{
f[i][j]=f[i-1][j];//不符合直接不选,用上一组最大的即可
}
}
}
printf("%d\n\n\n\n\n\n\n\n\n",f[n][m]);//最后输出x=n,y=m的情况,也就是答案
cout<<"你听懂了吗";
return 0;
}
评论: