本文主要是介绍Coins HDU - 2844 （多重背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Coins
题目链接：HDU - 2844
题意：有N种面值不同的硬币，面值为Ai的硬币有Ci枚，问不超过M元的前提下，能组合成几种价格；
看作是体积是M的背包，看最后求出的有几个dp[i]=i的；
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int dp[maxn], A[110], C[110];
int main(){int n, m;while(scanf("%d%d", &n, &m), n||m){memset(dp, 0, sizeof(dp));for(int i=1; i<=n; i++){scanf("%d", &A[i]);}for(int i=1; i<=n; i++){scanf("%d", &C[i]);}for(int i=1; i<=n; i++){if(A[i]*C[i]>=m){for(int j=A[i]; j<=m; j++){dp[j]=max(dp[j], dp[j-A[i]]+A[i]);}}else{int k=1;while(k<=C[i]){for(int j=m; j>=k*A[i]; j--){dp[j]=max(dp[j], dp[j-k*A[i]]+k*A[i]);}C[i]-=k;k<<=1;}for(int j=m; j>=C[i]*A[i]; j--){dp[j]=max(dp[j], dp[j-C[i]*A[i]]+C[i]*A[i]);}}}int cnt=0;for(int i=1; i<=m; i++){if(dp[i]==i) cnt++;}printf("%d\n", cnt);}return 0;
}
这篇关于Coins HDU - 2844 （多重背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
