题意：有n种硬币，给出每种硬币的面值和个数，问这些硬币能组成多少种小于m的面值。
状态化的多重背包，二进制拆01背包超时，教主本意是要用单调队列来做，不过由于时间限制比较宽松所以可以转完全背包来做。
想法就是新建一个数组来存每种状态中用了多少个第 i 种硬币，在用第 i 种硬币更新状态时，同时更新这个记录数组。
代码如下：
#include<stdio.h> #include<string.h> int bag[100005],used[100005],worth[105],amount[105]; int main() { int n,m,i,j,cnt; while(scanf("%d%d",&n,&m),n||m) { for(i=1;i<=n;i++) scanf("%d",&worth[i]); for(i=1;i<=n;i++) scanf("%d",&amount[i]); memset(bag,0,sizeof(bag)); bag[0]=1; cnt=0; for(i=1;i<=n;i++) { memset(used,0,sizeof(used)); for(j=worth[i];j<=m;j++) { if(!bag[j]&&bag[j-worth[i]]&&used[j-worth[i]]+1<=amount[i]) { bag[j]=1; used[j]=used[j-worth[i]]+1; cnt++; } } } printf("%d\n",cnt); } return 0; }
POJ 1742Coins 多重背包转完全背包,布布扣,bubuko.com
原文：http://www.cnblogs.com/zhen94/p/3580742.html