题目：/contest/106/problem/C
题目告诉你有n克面粉，m种馅料，然后每种馅料有ai克，bi克馅料和ci克面粉做的面包可以买di元，也可以不放馅料，那么c0克面粉做的面包可以卖d0元，求最多可以赚多少钱
背包问题，对于n克面粉最多可以做min(n/ci,ai/bi)个面包或n/c0个面包，那么bi克馅料就分成min(n/ci,ai/bi)种馅料，转换成01背包，容量为n，费用为ci，价值为wi
代码：
View Code
#include<stdio.h>
#include<string.h>
int main()
{
int n,m,x,y,z,all,min,i,j;
int c[10001],w[10001],dp[10001];
while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF)
{
i=0;
min=n/x;
while(min--)
{
c[i]=x;
w[i]=y;
i++;
}
while(m--)
{
scanf("%d%d%d%d",&all,&x,&y,&z);
min=n/y;
if(min>all/x)
min=all/x;
while(min--)
{
c[i]=y;
w[i]=z;
i++;
}
}
m=i;
memset(dp,0,sizeof(dp));
dp[0]=0;
for(i=0;i<m;i++)
{
for(j=n;j>=c[i];j--)
{
if(dp[j]<dp[j-c[i]]+w[i])
dp[j]=dp[j-c[i]]+w[i];
}
}
int max=0;
for(i=0;i<=n;i++)
{
if(max<dp[i])
max=dp[i];
}
printf("%d\n",max);
}
return 0;
}
如果觉得《Codeforce C. Buns》对你有帮助，请点赞、收藏，并留下你的观点哦！
