随笔档案

  2011年2月16日

PKU 1742 Coins

楼教主男人八题的最简单一题，如果用传统的多重背包来解就是0(nmc)的复杂度，必然超时。

复习了一会儿背包九讲，研究出来了2种做法:

1.将c[i]分为二进制，例如15分为1 2 48个背包利用2^k个物品来背包，即可将c[i]优化到log(c[i])的程度。

2.还有一种称为是单调队列优化的方法，查阅了很多资料没有看到。

研究了解题报告后，大概方法是这样的，利用一个count[j]数组记录当前物品表达j这个状态时所需要的硬币数目，由于题目要求所枚举状态只需要知道是否可行，并不需要得到一个最优解，所以每次都只更新还没有更新过的状态，这样就不会出现某个状态用1个i硬币或2个i硬币都能表达的情况。

#include <iostream>
 
using namespace std;
 
int n, m;
 int v[MAXN], c[MAXN];
 bool f[100001];
 int coun[100001];
 
int main()
 {
     while(1)
     {
         scanf("%d%d", &n, &m);
         if(!n && !m) exit(0);
         memset(f, 0, sizeof(f));
         f[0] = 1;
         for(int i = 1; i <= n; i++)
             scanf("%d", v + i);
         for(int i = 1; i <= n; i++)
             scanf("%d", c + i);
         for(int i = 1; i <= n; i++)
         {
             for(int j = 1; j <= m; j++)
                 coun[j] = 0;
             for(int j = v[i]; j <= m; j++)
                 if(f[j - v[i]] && !f[j] && coun[j - v[i]] < c[i])
                 {
                     coun[j] = coun[j - v[i]] + 1;
                     f[j] = 1;
                 }
         }
         int ans = 0;
         for(int i = 1; i <= m; i++)
             if(f[i]) ans++;
         printf("%d\n", ans);
     }
     return 0;
 }