首页 > 代码库 > HDU 2844 Coins【多重背包】

HDU 2844 Coins【多重背包】

大意:

有n种物品

告诉你每种物品的价值和数量

问你能拼凑出1--m之内的多少个数

 

分析:

多重背包

 

代码:

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn = 100005; 7 int dp[maxn]; 8 int num[maxn], va[maxn]; 9 int vo[maxn];10 int n, m;11 int tot;12 13 int solve() {14     int cnt = 0;15     memset(dp, 0, sizeof(dp));16     for(int i = 1; i < tot; i++) {17         for(int j = m; j >= vo[i]; j--) {18             dp[j] = max(dp[j], dp[j - vo[i]] + vo[i]);19         }20     }21     for(int i = 1; i <= m; i++) {22         if(dp[i] == i) cnt++;23     }24     return cnt;25 }26 27 int main() {28     while(scanf("%d %d",&n, &m) && ( n + m ) ) {29         for(int i = 1; i <= n; i++) {30             scanf("%d",&va[i]);31         }32         for(int i = 1; i <= n; i++) {33             scanf("%d",&num[i]);34         }35         tot = 1;36         for(int i = 1; i <= n; i++) {37             for(int k = 1; k <= num[i]; k *= 2) {38                 vo[tot++] = k * va[i];39                 num[i] -= k;40             }41             if(num[i]) vo[tot++] = num[i] * va[i];42         }43         printf("%d\n",solve());44     }45     return 0;46 }
View Code

 

HDU 2844 Coins【多重背包】