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]元用的次数加1
count++;
}
}
}
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;
}