本文主要是介绍hdu 2844 Coins(多重背包 可达不可达)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=2844
题意：
一位同学想要买手表，他有n种硬币，每种硬币已知有num[i]个。已知手表的价钱最多m元，问她用这些钱能够凑出多少种价格来买手表。
思路：多重背包。但不能直接转化为01背包求，因为数据太多，TLE无疑。。可以增加一个一维数组use[ i ],记录到达i元时j种钱用的次数。
#include <stdio.h>
#include <string.h>bool dp[100010];
int use[100010];//i元钱时某种钱用的次数
int n,m;
int val[110],num[110];void solve()
{memset(dp,0,sizeof(dp));dp[0] = 1;int count = 0;for(int i = 1; i <= n; i++){memset(use,0,sizeof(use)); //每次初始化第i种钱用了0次for(int j = val[i]; j <= m; j++)//顺序枚举钱数{if(dp[j-val[i]] && !dp[j] && use[j-val[i]] < num[i]){dp[j] = 1;use[j] = use[ j-val[i] ]+1;//到达j元用的i种钱的次数是到达 j-val[i]元用的次数加1count++;}}}printf("%d\n",count);
}
int main()
{while(~scanf("%d %d",&n,&m)){if(n == 0 && m == 0)break;for(int i = 1; i <= n; i++)scanf("%d",&val[i]);for(int i = 1; i <= n; i++)scanf("%d",&num[i]);solve();}return 0;}
这篇关于hdu 2844 Coins(多重背包 可达不可达)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
