POJ1276 Cash Machine(多重背包问题)
三种解法：多重背包转化为完全背包和01背包；多重背包通过二进制化化为01背包；通过计数法优化为2重循环。
code1: 47MS
#include <cstdio>#include <cstring>int main(){ int i, j, cash, n, v[15], nums[15]; int opt[100010]; int cnt[100010]; while(~scanf("%d%d",&cash,&n)) { for(i=0; i<n; ++i) scanf("%d%d",&nums[i],&v[i]); for(i=0; i<=cash; ++i) opt[i] = 0; for(i=0; i<n; ++i) { memset(cnt, 0, sizeof(int)*(cash+1)); for(j=v[i]; j<=cash; ++j) { if(opt[j] <opt[j-v[i]]+v[i]&&cnt[j-v[i]]<nums[i]) { cnt[j] = cnt[j-v[i]]+1; opt[j] = opt[j-v[i]] + v[i]; } } } printf("%d\n",opt[cash]); } return 0;}