链接：POJ - 1276

题意：给你一个最大金额m，现在有n种类型的纸票，这些纸票的个数各不相同，问能够用这些纸票再不超过m的前提下凑成最大的金额是多少？

题解：写了01背包直接暴力，结果T了，时间复杂度太高了，要跑外循环m和内循环所有的纸票的个数。这个题需要把每种纸票的的个数存的时候转化成2的次幂的形式来存，比如有8个$1，就可以存成1，2，4，1。这样就可以不存放8个1了，如果在个数大的情况下存储的也不会很多，因为转化成这样子，在1~8每一个都可以凑出来，随机搭配，另一方面，如果是8个$2，那么可以存的是2，4，8，2。是2~16之间的偶数都可以凑出来。这是转化成二进制存的好处，具体证明可以自己百度一下。

存的这个地方处理好了之后，剩下的用01背包跑一遍就可以了，我，板子当时记错了QAQ。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const ll maxn = 420000;

ll a[maxn];

ll dp[maxn];

int main()

{

    ll n,m;

    while(~scanf("%lld",&m))

    {

        memset(dp,0,sizeof(dp));

        scanf("%lld",&n);

        ll i,j, x, y, cnt,sum,temp;

        cnt = 0;

        while(n --)

        {

            scanf("%lld %lld",&x,&y);

            temp = sum = 1;

            while(sum <= x)

            {

                a[cnt ++] = temp * y;

                temp *= 2;

                sum += temp;

            }

            if(sum - temp < x)

                a[cnt ++] = (x - (sum - temp)) * y;

        }

        for(i = 0; i < cnt; i ++)

        {

            for(j = m; j >= a[i]; j --)

            {

                dp[j] = max(dp[j],dp[j - a[i]] + a[i]);

            }

        }

        printf("%lld\n",dp[m]);

    }

    return 0;

}