hdu-cins

http://acm.hdu.edu.cn/showproblem.php?pid=2844
 
Problem Description
WWchacmers coins.They have coins of value A 1，A 2，A 3…An Silverlad dollar.One day Hbix opened prse and found there coins.Hededed to to buy averynitwatttttwatinina nearara.Onearbyshshshsheeeeeeeeeeeeeexxprprprexxxthethethetheaaaaaaaaaaaaaaaaatttttttttttttshshshshshshshshshshshshshshshshshshshshshshaaaaaaaaaaaaaaaaanow t he exact price of the watch.
You are to write a program which reads n，m，A 1，A 2，A 3…An and C 1，C 2，C 3…Cn corelding to the number of Tony coins A 1，A 2，A 3…An then cacaculate how many press(form 1 to to to to to to to to to to Tonypanese)cany.cars Coinse。
 
 
Input
The input contains several test cases.The first line of each test case contains two integers n(1≦n≦100).m(m≦100000).The second line 2 n integers，denoting A 1，A 3.An，C 1,000,，.C 2,ewers 1,Cece 1000
 
 
Output
For each test case output the answer on a single line.
 
 
Sample Input
3 10 1 2 4 1 1 2 1 2 5 1 4 1 1 0
 
 
Sample Output
8 4
 
この問題は多重リュックサックの問題で、面倒くさいです。他の人のコードを見て、バイナリに変換する思想を使いました。
 
分析:
 

#include<iostream>
using namespace std;
int main()
{
    int i,j,k;
    int n,m;
    int dp[100044];
    int val[100004];
    int num[100004];
    while(cin>>n>>m)
    {
          if((n==0)&&(m==0))
          break;
          for(i=0;i<n;i++)
          cin>>val[i];
          for(i=0;i<n;i++)
          cin>>num[i];
          for(i=0;i<100000;i++)
          dp[i]=-9999999;
          dp[0]=1;
          for(i=0;i<n;i++)
          {
              if(val[i]*num[i]>=m)
              {
                  for(j=val[i];j<m;j++)
                  dp[j]=max(dp[j],dp[j-val[i]]+val[i]);
              }
              else
              {
                  for(k=1;k<=num[i];k=k*2)
                  {
                      for(j=m;j>=val[i]*k;j--)
                      {
                          dp[j]=max(dp[j],dp[j-val[i]*k]+val[i]*k);
                      }
                      num[i]=num[i]-k;
                  }
                  if(val[i]>0)
                  {
                     for(j=m;j>=val[i]*num[i];j--)
                     dp[j]=max(dp[j],dp[j-val[i]*num[i]]+val[i]*num[i]);
                  }
              }

          }
          int count=0;
          for(j=1;j<=m;j++)
          {
              if(dp[j]>=0)
              count++;
          }
         cout<<count<<endl;
    }
    return 0;
}