题目类型 DP
题目意思
给出一个凑钱的目标 x (0 <= x <= 100 000) 和 n (0 <= n <= 10) 种硬币的面值(1-1000) 和数量(1-1000) 问能凑出的最大的不超过 x 的钱数是多少
解题方法
多重背包
用二进制优化即可AC
二进制优化:
最终某种硬币出的数量是确定的 所以只要枚举完所有可能的数量即可 暴力枚举就是从小到大枚举数量 但是这样效率太低
因此可以把某种硬币的数量 N 分割成 c 个数 然后用这 c 个数对应的一个 "物品" 去更新其他值
那么应该分割成哪几个值呢 如果 N 等于 2^0 + 2^1 + 2^2 + 2^3 = 15 的话只要把 15 分割成 4 个整数 1 2 4 8, 那么1,2,4,8中某几个数的和
就可以表示出 1 - 15了, 即用 1, 2, 4, 8对应的物品用01背包的方式更新一次即可
但是如果硬币的数量不是 2^x-1的话 可以把 N 分成最大的 2^x-1和 (N- (2^x-1)), 2^x-1再分割成 2^0 + 2^1 + ... + 2^(x-1)
其中 (N-(2^x-1)) < 2^x 否则 x 可以更大 这样的话 2^0,2^1,...,2^(x-1)的某几个数的和可以组合出 1->(2^x-1) 而 2^x->N可以由 (N-(2^x-1)) + (2^0,2^1,...2^(x-1))中的某几个数组成 因为(N-(2^x-1)) 是小于等于 2^x-1即要组合的某个数-(N-(2^x-1)) <= 2^x-1 所以 2^x->N自然可以组合出来
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
bool dp[100010];
int main() {
// freopen("in", "r", stdin);
int cash, n;
while(scanf("%d%d", &cash, &n) != EOF) {
memset(dp, 0, sizeof(dp));
dp[0] = true;
for( int i=0; i<n; i++ ) {
int a, b;
scanf("%d%d", &a, &b);
int k = 1; // k 表示不断增大的2的幂
while(k <= a) {
for( int j=cash; j>=b*k; j-- ) {
if(dp[j-b*k]) dp[j] = true;
}
a -= k; // a 不断减去2的幂
k *= 2; // 且2的幂不断增大
}
if(a) { // 如果还有部分剩下的话单独进行一次更新
for( int j=cash; j>=b*a; j-- ) {
if(dp[j-b*a]) dp[j] = true;
}
}
}
while(cash) {
if(dp[cash]) break;
cash--;
}
printf("%d\n", cash);
}
return 0;
}