Description
In a strange shop there are n types of coins of value A1, A2 ... An. C1, C2, ... Cn denote the number of coins of value A1, A2 ... Anrespectively. You have to find the number of different values (from 1 to m), which can be produced using these coins.
Input
Input starts with an integer T (≤ 20), denoting the number of test cases.
Each case starts with a line containing two integers n (1 ≤ n ≤ 100), m (0 ≤ m ≤ 105). The next line contains 2n integers, denoting A1, A2... An, C1, C2 ... Cn (1 ≤ Ai ≤ 105, 1 ≤ Ci ≤ 1000). All Ai will be distinct.
Output
For each case, print the case number and the result.
Sample Input
2
3 10
1 2 4 2 1 1
2 5
1 4 2 1
Sample Output
Case 1: 8
Case 2: 4
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 #define mod 100000007 6 int a[1001],c[101],dp[100001],b[101]; 7 int main() 8 { 9 int n,k,t,i,j,r; 10 scanf("%d",&t); 11 for(i=1; i<=t; i++) 12 { 13 memset(dp,0,sizeof(dp)); 14 scanf("%d%d",&n,&k); 15 for(j=1; j<=n; j++)scanf("%d",&b[j]); 16 for(j=1; j<=n; j++)scanf("%d",&c[j]); 17 int nu=0,re,rs; 18 for(j=1; j<=n; j++) 19 { 20 re=b[j],rs=c[j]; 21 c[j]*=b[j]; 22 while(rs) 23 { 24 if(re<c[j]) 25 a[nu++]=re,c[j]-=re; 26 else a[nu++]=c[j]; 27 rs>>=1; 28 re<<=1; 29 } 30 } 31 for(j=0; j<nu; j++) 32 { 33 for(r=k; r>=0; r--) 34 { 35 if(dp[r]&&r+a[j]<=k) 36 dp[r+a[j]]=1; 37 if(r==0&&a[j]<=k) 38 dp[a[j]]=1; 39 } 40 41 } 42 int sum=0; 43 for(r=0; r<=k; r++)sum+=dp[r]; 44 cout<<"Case "<<i<<": "; 45 cout<<sum<<endl; 46 } 47 48 }
C - Coin Change (III)（多重背包 二进制优化）,布布扣,bubuko.com
C - Coin Change (III)（多重背包 二进制优化）
原文：http://www.cnblogs.com/ERKE/p/3582219.html
