HDU Coins【多重バックパック問題】

考え方:
時計の価格はm元で、硬貨の中でいくつかの硬貨を選んでいくつかの異なる総価値pを構成します(そしてその総価値pを(1->m)の間に)
ACコード:

#include<stdio.h>
#include<string.h>
int dp[100005],c[105],v[105];
int m;
void CompletePack(int c,int w)
{
     int i;
     for(i=c;i<=m;i++)
		 if(dp[i]<dp[i-c]+w)
		 {
			 dp[i]=dp[i-c]+w;
		 }	
}
void ZeroOnePack(int c,int w)
{
     int i;
	 for(i=m;i>=c;i--)
		 if(dp[i]<dp[i-c]+w)
		 {
			 dp[i]=dp[i-c]+w;
		 }
}
void MultiPack(int c,int w,int amount)
{
     int k;
	 if(c*amount>m)
	 {
	       CompletePack(c,w);
		   return ;
	 }
	 k=1;
	 while(k<amount)
	 {
	       ZeroOnePack(k*c,k*w);
		   amount-=k;
		   k*=2;
	 }
	 ZeroOnePack(amount*c,amount*w);
}
int main()
{
    int n;
	int i,j;
	int count;
	int flag[100005];
	while(scanf("%d%d",&n,&m)!=-1&&(n+m))
	{
	     for(i=1;i<=n;i++)
			 scanf("%d",&v[i]);
		 for(i=1;i<=n;i++)
			 scanf("%d",&c[i]);
		 memset(dp,0,sizeof(dp));
		 for(i=1;i<=n;i++)
			 MultiPack(v[i],v[i],c[i]);
		 j=1;
		 for(i=m;i>=1;i--)
			 if(dp[i])flag[j++]=dp[i];/*  1->m          0       */
	     count=j-1;/*            ，           */
		 for(i=2;i<=j-1;i++)
			 if(flag[i]==flag[i-1])count--;/*  flag        ，            ，    1*/
		 printf("%d
",count);
	}			
    return 0;
}