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;}