题意：给你一个最大金额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
",dp[m]);
}
return 0;
}