07 二进制优化多重背包问题：樱花

二进制优化多重背包问题：樱花

樱花

题目背景

《爱与愁的故事第四弹·plant》第一章。

题目描述

爱与愁大神后院里种了 $n$ 棵樱花树，每棵都有美学值 $C_i(0 \le C_i \le 200)$。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看 $P_i(0 \le P_i \le 100)$ 遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 $T_i(0 \le T_i \le 100)$。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或提早）去上学。

输入格式

共 $n+1$行：

第 $1$ 行：现在时间 $T_s$（几时：几分），去上学的时间 $T_e$（几时：几分），爱与愁大神院子里有几棵樱花树 $n$。这里的 $T_s$，$T_e$ 格式为：hh:mm，其中 $0 \leq hh \leq 23$，$0 \leq mm \leq 59$，且 $hh,mm,n$ 均为正整数。

第 $2$ 行到第 $n+1$ 行，每行三个正整数：看完第 $i$ 棵树的耗费时间 $T_i$，第 $i$ 棵树的美学值 $C_i$，看第 $i$ 棵树的次数 $P_i$（$P_i=0$ 表示无数次，$P_i$ 是其他数字表示最多可看的次数 $P_i$）。

输出格式

只有一个整数，表示最大美学值。

样例 #1

样例输入 #1

6:50 7:00 3
2 1 0
3 3 1
4 5 4

样例输出 #1

11

提示

$100\%$ 数据：$T_e-T_s \leq 1000$（即开始时间距离结束时间不超过 $1000$ 分钟），$n \leq 10000$。保证 $T_e,T_s$ 为同一天内的时间。

样例解释：赏第一棵樱花树一次，赏第三棵樱花树 $2$ 次。

这是一个普通背包，多重背包，完全背包的混合

其他的背包正常做就行，但由于平时都是把多重背包一个物品最多取n件拆成n个这种的一件物品。时间会消耗得很厉害。于是就出现了二进制优化：

一个正整数n，可以被分解成1,2,4,…,2^(k-1),n-2k+1的形式。其中，k是满足n-2^k+1>0的最大整数。

例如，假设给定价值为2，数量为10的物品，依据二进制优化思想可将10分解为1+2+4+3，则原来价值为2，数量为10的物品可等效转化为价值分别为1x2，2x2，4x2，3x2，即价值分别为2，4，8，6，数量均为1的物品。

代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> t,c,p;
int dp[100000]={0};
int T,n;
int exchage(string st,string ed)
{
    if(st[1]==':')st="0"+st;
    if(ed[1]==':')ed="0"+ed;
    int hs=stoi(st.substr(0,2)),hed=stoi(ed.substr(0,2));
    int ms=stoi(st.substr(3,5)),med=stoi(ed.substr(3,5));

    if(hed<hs)hed+=24;
    int ret=(hed-hs)*60+med-ms;
    return ret;

}
signed main(void)
{
    string st,ed;
    cin>>st>>ed>>n;
    T=exchage(st,ed);
    //cout<<T<<endl;
    for(int i=0;i<n;i++)
    {
        int tempt,tempc,tempp;
        cin>>tempt>>tempc>>tempp;

        if(tempp==1 || tempp==0)
        {
            t.push_back(tempt);
            c.push_back(tempc);
            p.push_back(tempp);
        }
        else if(tempp>1)
        {
            int x=0;
            while (tempp > pow(2, x))
            {
                t.push_back(tempt * pow(2, x));
                c.push_back(tempc * pow(2, x));
                p.push_back(1);
                tempp -= pow(2, x);
                x++;
            }
                t.push_back(tempt * tempp);
                c.push_back(tempc * tempp);
//注意，数量（2个，4个...）绑定后相应的价值和重量也会发生改变
                p.push_back(1);
                
        }
    }
    
    for(int i=0;i<t.size();i++)
    {
        if(p[i]==0)//complete package
        {
            for(int j=t[i];j<=T;j++)
            {
                dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
            }
        }
        else 
        {
            for(int j=T;j>=t[i];j--)
            {
                dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
            }
        }
        
    }
    cout<<dp[T]<<endl;
    return 0;
}