题目大概意思是酱紫的 先给你两个数字 第一个代表目标金钱 第二个代表钞票的种类 （我这么理解的） 然后在给你n组数据 分别代表 某种面值的钞票有多少多少张
由于之前做过类似的题目 就没有用直接暴力怼 先加了一个二进制优化 简单讲一下二进制优化是什么意思 ：
二进制优化：
假设面值为1的钞票你有100张 普通做法是在数组中记录两百个1 就会很复杂 二进制优化的思想是把这一百张钞票分成 1 ， 2， 4， 8， 16， 32， 37； 这七张 他们是二的n次方来的值 这些值刚好可以组成1 ~ 100中的任意面值 是不是很神奇 我第一次学的时候也觉得 还tm有这种操作？？？ 后来发现这种操作和二进制原理有关系 大概就这样
代码中用了快速幂 + 打表 你问我为什么这么写？ 废话 当然是炫技了！！！
二进制储存的地方写的很繁琐 读者可以自己优化~~
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;
int p[10000];
int rec[15];
int dp[maxn];
int pow(int a,int b)
{
if(rec[b])return rec[b];
int base = a, res = 1;
while (b) {
if(b&1)
res *= base;
base *= base;
b >>= 1;
}
return rec[b] = res;
}
int main()
{
int sum, n;
memset(rec , 0, sizeof(rec));
while (cin >> sum >> n) {
int cnt = 0, temp, value;
for (int i = 0; i < n; i ++) {
cin >> temp >> value;
if(!temp)continue;
if(temp > 1) {
temp -= 1;
p[cnt ++] = value;
int po = 1;
while (temp) {
int k = pow(2 , po);
//cout << "k == " << k << endl;
if(k < temp) {
temp -= k;
p[cnt ++] = k * value;
} else {
p[cnt ++] = temp * value;
temp = 0;
}
po ++;
}
} else {
p[cnt ++] = value;
}
}
memset(dp , 0, sizeof(dp));
for (int i = 0; i < cnt ; i ++)
for (int j = sum; j >= p[i]; j --)
dp[j] = max(dp[j] , dp[j - p[i]] + p[i]);
cout << dp[sum] << endl;
}
}
