【板+背包】多重背包 HDU Coins

http://acm.hdu.edu.cn/showproblem.php?pid=2844

【题意】

• 给定n种价值为Ci,个数为Wi的硬币，问在1~V中的这些数中哪些数能由这些硬币组成？

【思路】

• 多重背包，二进制优化，时间复杂度为O(V*log∑ni)

【Accepted】

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<string>

 #include<algorithm>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 int n,v;

 int c[maxn],w[maxn];

 int dp[maxn];

 void ZOP(int cost,int wei)

 {

     for(int i=v;i>=cost;i--)

     {

         dp[i]=max(dp[i],dp[i-cost]+wei);

     }

 }

 void CPP(int cost,int wei)

 {

     for(int i=cost;i<=v;i++)

     {

         dp[i]=max(dp[i],dp[i-cost]+wei);

     }

 }

 void MTP(int cost,int wei,int cnt)

 {

     if(v<=cnt*cost)

     {

         CPP(cost,wei);

         return;

     }

     int k=;

     while(k<=cnt)

     {

         ZOP(k*cost,k*wei);

         cnt-=k;

         k*=;

     }

     ZOP(cnt*cost,cnt*wei);

 }

 int main()

 {

     while(~scanf("%d%d",&n,&v))

     {

         if(n==&&v==) break;

         for(int i=;i<n;i++)

         {

             scanf("%d",&c[i]);

         }

         for(int i=;i<n;i++)

         {

             scanf("%d",&w[i]);

         }

         memset(dp,,sizeof(dp));

         for(int i=;i<n;i++)

         {

             MTP(c[i],c[i],w[i]);

         }

         int cnt=;

         for(int i=;i<=v;i++)

         {

             if(dp[i]==i)

             {

                 cnt++;

             }

         }

         printf("%d\n",cnt);

     }

     return ;

 }

背包模板