link:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=417#problem/S
http://acm.hdu.edu.cn/showproblem.php?pid=2844
题目大意:有n个物品,每个物品的价值为[i],meige物品的数量
为c[i],问用所有的硬币能够在m的范围内,最多可以组成多少组不同的值。
典型的多重背包问题(应该也可以用母函数做,不过不是很会),背包九讲上有具体解析
下面代码留着当模板,哦吼吼吼~~~~
code:

#include <stdio.h>
#include <string.h>
#define MAX 100005
int v[101],w[101],c[101],dp[MAX],N,M;

int maxx(int a,int b)
{
return a>b?a:b;
}

void bag01(int v,int w)/*01背包*/
{
int i;
for(i=M;i>=w;i–)
dp[i]=maxx(dp[i],dp[i-w]+v);
}

void bagall(int v,int w)/*完全背包*/
{
int i;
for(i=w;i<=M;i++)
dp[i]=maxx(dp[i],dp[i-w]+v);
}

void multbag(int v,int w,int c)/*多重背包*/
{
if(c*v>=M)
bagall(v,w);
else
{
int k=1;
while(k<c)
{
bag01(k*v,k*w);
c-=k;
k*=2;
}
bag01(c*v,c*w);
}
}

int main()
{
int i,cnt;
while(scanf(“%d%d”,&N,&M)&&(N||M))
{
for(i=1;i<=N;i++)
{
scanf(“%d”,&v[i]);
w[i]=v[i];
}
for(i=1;i<=N;i++)
scanf(“%d”,&c[i]);
memset(dp,0,sizeof(dp));
for(i=1;i<=N;i++)
{
multbag(v[i],w[i],c[i]);
}
for(i=1,cnt=0;i<=M;i++)
if(dp[i]==i)
cnt++;
printf(“%d\n”,cnt);
}
return 0;
}

 

发表评论

电子邮件地址不会被公开。

Post Navigation