题目描述：
为了迎接节日，商店街策划了一次”火舞之人“促销大酬宾活动。每个在活动开始当天来商店街消费的客人，都可以最多抽奖两次，根据抽到的卡片获得不同的优惠。已知卡池里面有红色的小绵羊卡、黑色的小鲨鱼卡、紫色的大尾巴狼卡以及一张看上去就很稀有的眯眯眼天使卡。你抽出了一张黑色小鲨鱼卡，还上去还有点稀有的样子，身边没多少人抽到。
对于抽到黑色小鲨鱼卡的人，本期活动中，共有N件商品参与促销，你身上带了M块钱。这N种物品每种物品有价格Ci和原价Vi，以及限购Ki件。
你想知道你最多能够买走原价总和多少的商品。特别提醒，商品论件出售，不允许拆分。
输入格式：
第一行包括两个正整数N， M，表示共有N件商品，你有M块钱。
接下来的N行，每i行包括三个自然数Ci,Vi,Ki。表示第i件商品的价格、原价和限购数量。
输出格式：
输出仅包括一个正整数，表示你能买走的最大原价总和。
输入样例:
2 8
2 100 4
4 100 2
输出样例:
400
HINT
对于60%的数据， 1<=Ki<=20
对于100%的数据，1<=N<=200,1<=M<=3000,0<=Ci<=20,1<=Vi<=200,1<=Ki<=10^6
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int max(int a, int b) {
return a > b ? a : b;
}
const int N = 200, M = 3000;
int dp[M+1], v[N * M+1], w[N * M+1];
int main()
{
int n, m, k = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int vv, ww, s;
cin >> vv >> ww >> s;
for (int i = 1; i <= s; i *= 2) //与之前代码改进的地方是我之前没有用二进制去优化，因为数量级是10的6次方，不优化也许过不了。
v[k] = vv * i, w[k++] = ww * i, s -= i;
if (s > 0)
v[k] = vv * s, w[k++] = ww * s;
}
for (int i = 0; i <k; i++)
for (int j = m; j >= v[i]; j--)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[m] << endl;
return 0;
}
这一题有两种优化的方法，一种是单调队列优化（由于过于复杂本渣没弄懂），一种是二进制优化，单调队列的优化程度更高，但是二进制就达满分标准，所以你们懂得。
二进制优化：
简单点说就是，本来你有一种物品可选，它占用的是Vi，价值是Wi，个数是N。
则你一开始是在N个数里进行0-1背包选择，例如你输入的是：
1 1 8
即当V和W都是1时，如果N是8，那你做0-1背包选择的时候其实是列8个相同的物品，如果要知道选7的价值是多少，你其实是选了前7个，第8个不选，价值是7。
但是如果是二进制优化，你就不需要8个相同的1 1的组合了 ：
8可以拆分成1+2+4+1（余数），所以你要存的不是8个1 1，而是4组数：
1 1
2 2
4 4
1 1
这有什么好处呢，同样，你想知道7的价值的时候，你不用做8个数的背包选择（选前7个1，不选最后一个1），只要选1+2+4，不选最后的余数1，做一次4个数的背包选择就行了。
这样多重背包的复杂度就降了一个规模。
for (int i = 1; i <= s; i *= 2)
v[k] = v * i, w[k++] = w * i, s -= i;
if (s > 0)
v[k] = v* s, w[k++] = w * s;
}
for (int i = 0; i <k; i++)
for (int j = m; j >= v[i]; j--)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
总结：二进制优化让时间复杂度和空间复杂度都从n降为了logn
不得不感叹，这是和大佬脑子上的差距啊
网友评论