二进制分组优化
题目
题目描述
爱与愁大神后院里种了 n 棵樱花树，每棵都有美学值 C₁（0 ≤ Cᵢ ≤ 200）。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：
- 一种樱花树看一遍过，
- 一种樱花树最多看 Pᵢ（0 ≤ Pᵢ ≤ 100）遍，
- 一种樱花树可以看无数遍。
但是看每棵樱花树都有一定的时间 Tᵢ（0 ≤ Tᵢ ≤ 100）。
爱与愁大神离去上学的时间只剩下一小会儿了。
求解：看哪几棵樱花树能使美学值最高，且他能准时（或提早）去上学。
输入格式
共 n+1 行。
第 1 行：现在时间 Tₛ（格式：hh:mm），去上学的时间 Tₑ（格式：hh:mm），樱花树数量 n。
其中 0 ≤ hh ≤ 23，0 ≤ mm ≤ 59，hh、mm、n 为正整数。
第 2 行到第 n+1 行，每行三个正整数：Tᵢ Cᵢ Pᵢ
- Tᵢ：看完第 i 棵树的耗时
- Cᵢ：第 i 棵树的美学值
- Pᵢ：最多可看的次数（0 表示可无限次）
输出格式
只有一个整数，表示最大美学值。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
100% 数据满足：Te - Ts ≤ 1000（即开始时间距离结束时间不超过 1000 分钟），n ≤ 10000。保证 Te、Ts 为同一天内的时间。
样例解释
爱与愁大神有 10 分钟时间赏花。
他选择赏第一棵樱花树 1 次，赏第三棵樱花树 2 次，总花费时间：2 + 4 × 2 = 10 分钟。
获得的美学值为：1 + 5 × 2 = 11。
思路
本题为标准混合背包模板，包括01背包（选/不选）、多重背包（每个物品有限次数选择）和完全背包（每个物品不限次数选择），其通用思路为：
- 将多重背包转换为复数个使用二进制分组优化的01背包
- 单开状态数组记录每个物品为01背包（包括多重背包转换为的01背包）和完全背包
- 进入正常背包问题的
dp[i]外层循环 - 根据状态数组决定进入的内层循环是01背包的倒序还是完全背包的顺序
- 输出
dp[t](t为最大时间)
注意：01背包和完全背包的内层for遍历顺序不同，如果采用01背包的两个dp数组回滚会导致完全背包的部分在计算时出错，因此对于这类问题应该只用一个dp数组，所有操作都在原来的数组上修改。
二进制分组：原理是任意一个整数 P，都可以表示成若干个 2 的幂次之和 ，而使用这种拆分能在保证dp结果相同时降低时间复杂度。
内层循环的顺序：完全背包和01背包的模板上唯一的区别是内层循环的顺序和倒序，其中，01背包倒序是为了防止同一物品被重复选取。
for循环嵌套：01背包中两层for循环判断的本质是是否将第i个物品放入最大容量为j的背包中。
dp[j-w[i]]+w[i]：状态转移方程中的这一部分是选择当前物品时的最大价值。
如果要在容量为j的背包中装下当前物品，那么可以剩下的能装物品的最大容积就是j-w[i]，用这时的最大价值加上当前物品的价值，结果就是如果取当前物品，背包中能装下的最大价值。
因为当前物品是有体积的，而背包已经装了一部分东西，如果要装下当前物品，就必须舍弃部分物品，留出可以装下当前物品的容积。
Code
#include<iostream>
#include<cstring>
using namespace std;
const int N = 70005;
int h1=0, m1=0, h2=0, m2 = 0;
char _a; //滤掉时间输入时的字符
int t; //时间
int tree; //树的数目
int n=1; //分堆用的计数器；
int cost, value, num; //耗费时间，美学价值，可看次数
int c[N] = { 0 }, v[N] = { 0 }; // 二进制分堆后的耗费时间和美学价值；
bool state[70005] = { false }; //ture：01背包；false：完全背包
int dp[1005] = { 0 }; //dp
int main(){
cin >> h1 >> _a >> m1;
cin >> h2 >> _a >> m2;
cin >> tree;
t = 60 * (h2 - h1) + (m2 - m1); //最大时间
for (int x = 1;x <= tree ; x++) {
cin >> cost >> value >> num;
if (num == 0) {
c[n] = cost;
v[n] = value;
state[n] = false;
n++;
}
else {
for (int i = 1;i <= num;i<<=1) {
c[n] = cost * i;
v[n] = value * i;
state[n] = true; // 01背包
num -= i;
n++;
}
if (num!=0) {
c[n] = cost * num;
v[n] = value * num;
state[n] = true;
n++;
}
}
}
for (int i = 1;i < n;i++) {
//01背包
if (state[i]) {
for (int j = t;j >= 1;j--) {
if (c[i] > j)continue;
dp[j] = max(dp[j], dp[j - c[i]] + v[i]);
}
}
//完全背包
else {
for (int j = 1;j <=t;j++) {
if (c[i] > j)continue;
dp[j] = max(dp[j], dp[j - c[i]] + v[i]);
}
}
}
cout<<dp[t];
return 0;
}