题目网址：http://poj.org/problem?id=1276
思路：
很明显是多重背包，把总金额看作是背包的容量。
刚开始是想把单个金额当做一个物品，用三层循环来 转换成01背包来做。T了……
后面学习了 用二进制来处理数据。
简单地介绍一下二进制优化：✧(≖ ◡ ≖✿)
假设数量是8，则可以把它看成是1，2，4，1的组合，即这4个数的组合包括了1-8的所有取值情况。这是为什么呢？将它们转换成二进制再观察一下：
1：1
2：10
4：100
1：1
二进制都只有0，1。所以1，2，4已经能够组成1-7的所有情况，但是这样还不够 还要再加一个1 才能凑成8
或许有人会问 为什么不取到8，即1，2，4，8。注意！！所有的数加起来不可以超过数量。
我们主要是用到这些数的排列组合，取到8的话 上限就被我们扩大了，会取到原本不能取到的值。
将数量分解成之后，把number[i]*value当做一个物品，就可以转换成01背包啦~ 详情看代码！
代码：
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int dp[];
int a[];
vector<int>v;
int main(){
int cash;
int n,m,x;
while(scanf("%d%d",&cash,&n)!=EOF){
memset(dp,, sizeof(dp));
v.clear();
dp[]=;
for (int i = ; i < n; ++i) {
scanf("%d%d",&m,&x);
for (int j = ; j <= m; j<<=) {//二进制优化
v.push_back(j*x);
m-=j;
}
if(m>) v.push_back(m*x);//别忘了剩余的数
}
for (int i = ; i < v.size(); ++i) {
for (int j = cash; j >=v[i] ; --j) {
dp[j]=max(dp[j-v[i]],dp[j]);
}
}
for (int i = cash; i >= ; --i) {
if(dp[i]){
printf("%d\n",i);
break;
}
}
}
return ;
}