DP（分组背包两种二进制优化） Problem S：Coins（HDU 2844）

Problem S

Time Limit : 2000/1000ms (Java/Other)   Memory Limit :32768/32768K (Java/Other)

Total Submission(s) : 12   Accepted Submission(s) : 0

Problem Description

Whuacmers use coins.They havecoins of value A1,A2,A3...An Silverland dollar. One day Hibix opened purse andfound there were some coins. He decided to buy a very nice watch in a nearbyshop. He wanted to pay the exact price(without change) and he known the pricewould not more than m.But he didn't know the exact price of thewatch.<br><br>You are to write a program which readsn,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coinsof value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can payuse these coins.

Input

The input contains severaltest cases. The first line of each test case contains two integers n(1 ≤ n ≤100),m(m ≤ 100000).The second line contains 2n integers, denotingA1,A2,A3...An,C1,C2,C3...Cn (1 ≤ Ai ≤ 100000,1 ≤ Ci ≤ 1000). The last test caseis followed by two zeros.

Output

For each test case output theanswer on a single line.

Sample Input

3 10

1 2 4 2 1 1

2 5

1 4 2 1

0 0

Sample Output

8

4

算法分析：

更好做法：点击打开链接

一道水题，分组背包思想，第一次普通算法超时，然后用了二进制优化，依旧超时，真是无语，上网重新学习了一篇二进制解法

//朴素算法
#include <bits/stdc++.h>

using namespace std;

int main()

{

   int n,m;

   while(scanf("%d%d",&n,&m)&&(n||m))

    {

       int i,j,k,a[102],c[102],f[100002];

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

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

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

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

         for(i=0;i<100002;i++)

           f[i]=0;

 

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

         for(j=m;j>=0;j--)

         for(k=0;k<=c[i];k++)

         if(j>=k*a[i])

           f[j]=max(f[j],f[j-k*a[i]]+k*a[i]);

           int ans=0;

           for(i=1;i<=m;i++)

           {

                if(f[i]==i])  ans++;

           }

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

    }

   return 0;

}

//这种二进制超时
#include <bits/stdc++.h>

using namespace std;

int main()

{

   int n,m;

   while(~scanf("%d%d",&n,&m)&&(n||m))

    {

       int a[102],c[102],f[100002],v[100002];

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

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

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

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

 

 

           //二进制优化

 

           int j=0;

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

          {

               int t=1;

               while(c[i]>=t)

               {

                   j++;

 

                   v[j]=a[i]*t;

                   c[i]-=t;

                  t*=2;

               }

               j++;

               v[j]=c[i]*a[i];//将c[i]以2为指数的堆：1，2，4.....2的（k-1）次方,c[i]-（2的k次方）+1

          }

        for(int i=0;i<100002;i++)

           f[i]=0;

           for(int i=0;i<j;i++)

                for(int k=m;k>=v[i];k--)

                f[k]=max(f[k],f[k-v[i]]+v[i]);

 

           int ans=0;

           for(int i=1;i<=m;i++)

           if(f[i]==i)  ans++;

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

    }

   return 0;

}

//这种二进制优化过了
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
        int i,j,k,p,a[105],c[105],f[100005];
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
            scanf("%d",&c[i]);

          memset(f,0,sizeof(f));
          f[0]=1;//初始化
          for(i=1;i<=n;i++)
          {
              k=1;
              while(c[i]>=k)//二进制优化
              {
                  p=k*a[i];
                  for(j=m;j>=p;j--)
                    if(f[j-p]==1)
                    f[j]=1;
                   c[i]-=k;
                   k*=2;
              }
              if(c[i])
              {
                p=a[i]*c[i];
                for(j=m;j>=p;j--)
                    if(f[j-p]==1)
                    f[j]=1;
              }
          }
            int ans=0;
            for(i=1;i<=m;i++)
            {
                if(f[i]==1)  ans++;
            }
            printf("%d\n",ans);
    }
    return 0;
}