POJ 1742 Coins（背包问题）

题意：给你一定数量和面值的纸币，在不超过总钱数m的情况下，用所给的纸币共能形成多少种钱数
思路：本来想到多重背包上面了，用多重背包写了一下，tle，后来用二进制优化，还是tle，后来看dis，说用优先队列，网上搜资料，没看懂，，后来看acmj1991的博客，说是用数组标记法，然后不懂神马是数组标记法。后来才知道，其实就是个常规的方法，不过很强大。具体来说，对于每件物品，循环钱数从自身价值一直到总价值，每次循环时判断，若该值没出现过，则ans加1.用flag[i]标记i这个值是否出现过，num[i]表示当前物品的价值，sum表示当前物品的数量，则if(flag[i - num[i]] && cnt[i - num[i]] < sum && !flag[i])成立时，ans加1。其中cnt[i]表示当前物品所形成的价值为i时所用的当前物品的数量。
代码：
[cpp]
#include <iostream> 
#include <cstdio> 
#include <string.h> 
using namespace std; 
 
#define CLR(arr,val) memset(arr,val,sizeof(arr)) 
const int N = 100010; 
int num[110]; 
bool flag[N]; 
int cnt[N]; 
int main(){ 
    //freopen("1.txt","r",stdin); 
    int n,totalvalue; 
    while(scanf("%d%d",&n,&totalvalue)&&n&&totalvalue){ 
      for(int i = 0;i < n;++i) 
          scanf("%d",&num[i]); 
      CLR(flag,false); 
      flag[0] = true; 
      int sum = 0,ans = 0; 
      for(int i = 0;i < n;++i){ 
         scanf("%d",&sum); 
         CLR(cnt,0); 
         for(int j = num[i];j <= totalvalue;++j){ 
             if(flag[j-num[i]] && cnt[j-num[i]] < sum && !flag[j]){ 
                flag[j] = true; 
                ans++; 
                cnt[j] = cnt[j-num[i]] + 1; 
             } 
         } 
      } 
      printf("%d\n",ans); 
    } 
    return 0; 
} 
作者：wmn_wmn

补充：软件开发 , C++ ,