| Time Limit: 3000MS | Memory Limit: 30000K | |
| Total Submissions: 32309 | Accepted: 10986 |
Description
Input
Output
Sample Input
3 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0
Sample Output
8 4
题意：给出3种硬币的面额和数量，能拼成不大于m的多少种；
多重背包可解，因为只要求行或不行就可以了，所以就两种状态在01和完全背包的时候没必要求可行解，只要确定行或不行就ok了，所以直接与dp[j - a[i]] 或运算，
注意的是，位运算真的好快，把dp设成int，用关系运算||,是超时的，改成位运算的|直接3000ms卡过；
改成bool型直接2204ms;
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 using namespace std; 6 const int MAX = 100000 + 10; 7 bool dp[MAX]; 8 int a[100 + 10],c[100 + 10]; 9 int n,m; 10 void ZeroOnePage(int cost) 11 { 12 for(int i = m; i >= cost; i--) 13 { 14 dp[i] |= dp[i - cost]; 15 } 16 } 17 void CompletePage(int cost, int mount) 18 { 19 for(int i = cost; i <= m; i++) 20 dp[i] |= dp[i - cost]; 21 } 22 void MultiplePage(int cost, int mount) 23 { 24 if(cost * mount >= m) 25 { 26 CompletePage(cost, mount); 27 return ; 28 } 29 int k = 1; 30 while(k < mount) 31 { 32 ZeroOnePage(k * cost); 33 mount -= k; 34 k <<= 1; 35 } 36 if(mount > 0) 37 ZeroOnePage(mount * cost); 38 return ; 39 } 40 int main() 41 { 42 while(scanf("%d%d", &n, &m) != EOF) 43 { 44 if(n == 0 && m == 0) 45 break; 46 for(int i = 1; i <= n; i++) 47 scanf("%d", &a[i]); 48 for(int i = 1; i <= n; i++) 49 scanf("%d", &c[i]); 50 memset(dp, 0, sizeof(dp)); 51 dp[0] = 1; 52 for(int i = 1; i <= n; i++) 53 if(c[i]) 54 MultiplePage(a[i], c[i]); 55 int sum = 0; 56 for(int i = 1; i <= m; i++) 57 if(dp[i]) 58 sum++; 59 printf("%d\n",sum); 60 } 61 62 return 0; 63 }
这种解法看不懂
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 using namespace std; 6 const int MAX = 100000 + 10; 7 int dp[MAX],used[MAX],a[100 + 10],c[100 + 10]; 8 int n,m; 9 int main() 10 { 11 while(scanf("%d%d", &n, &m) != EOF) 12 { 13 if(n == 0 && m == 0) 14 break; 15 for(int i = 1; i <= n; i++) 16 scanf("%d", &a[i]); 17 for(int i = 1; i <= n; i++) 18 scanf("%d", &c[i]); 19 memset(dp, 0, sizeof(dp)); 20 dp[0] = 1; 21 int sum = 0; 22 for(int i = 1; i <= n; i++) 23 { 24 memset(used, 0, sizeof(used)); 25 for(int j = a[i]; j <= m; j++) 26 { 27 if(dp[j] == 0 && dp[j - a[i]] && used[j - a[i]] < c[i]) 28 { 29 sum++; 30 dp[j] = 1; 31 used[j] = used[j - a[i]] + 1; 32 } 33 } 34 } 35 printf("%d\n",sum); 36 } 37 38 return 0; 39 }
原文：http://www.cnblogs.com/zhaopAC/p/5046215.html
