P1833 混合背包转化成 01 背包详解

lzyqwq · 2022-02-09 23:26:48 · 题解

题目分析

首先这是个混合背包，很烦，所以，我们要把他转化成不烦的。

于是，我的 OI 导师 FJ 教我了直接由混合背包转化成 01 背包的方法。转化主要分为四步走，接下来我们一起康康。

First Things First。

为了方便讲解，我把定义的变量、数组以及结构体先放上来。

const int M=1005,N=10005,K=70005;//偷个小懒，可以用#define完成
struct lim
{
    int w,c;//w表示耗费时间，c表示美学值
}f2[N];//一开始筛选物品用的完全背包樱花树的数组
int f[M],w1[N],c1[N],s1[N],wf[K],cf[K];
//f是dp的数组，w1、c1、s1非完全背包樱花树的时间、美学
//值、棵数，wf、cf存放二进制拆分后转化成01背包的樱花
//树。由于棵树最多10000，而二进制拆分会拆出来新的、更
//多的，所以wf和cf适当开大一点（由于要二进制拆分是log，而最多看pi遍不超过100，所以是log100×10000，70000就够了）

第一步：完整输入数据，并筛选出属于完全背包的物品。

这个没什么好说的，就是普通的读入加上特判 P_i 是否为 0。

int h1,m1,h2,m2;
scanf("%d:%d%d:%d",&h1,&m1,&h2,&m2);//这边scanf读入可以把字符的位置占用（预处理）掉，使我们读出整数
int n,m;
m=(h2*60+m2)-(h1*60+m1);//结束时间减起始时间为总时间，通过观察样例可知欣赏所用时间单位为分钟，所以把总时间用分钟的单位计算
scanf("%d",&n);
int k=0,l=0;//k为非完全背包物品个数，l为完全背包物品个数，都当下标使用
for(int i=1;i<=n;i++)
{
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    if(z)//如果不是完全背包
    {
        k++;//存入非完全背包
        w1[k]=x;
        c1[k]=y;
        s1[k]=z;
    }
    else//否则存入完全背包
    {
        l++;
        f2[l].w=x;
        f2[l].c=y;
    }
}

第二步：将完全背包中的樱花按照美学值从小到大排序，删除掉“残次品”，然后对于剩下的每一棵樱花树，用总时间除以这棵樱花树的欣赏时间，得出理论最大欣赏次数，转化成为多重背包，放入非完全背包（01 背包物品也可以看作物品个数为 1 的多重背包物品，所以非完全背包其实就是多重背包）。

这里对“残次品”的定义是：如果一棵樱花树的欣赏时间比别的樱花树长，但是美学值却比别的樱花树低，那肯定是去欣赏别的樱花树，而不是这棵。所以可以直接不要。

由于总共只有 m 分钟，而这棵樱花树需要 T_i 分钟，所以最多只能欣赏这颗樱花树 \left\lfloor\dfrac{x}{T_i}\right\rfloor 分钟(向下取整因为分钟是整数，而没有可以欣赏半次这种说法。所以要取整。因为向上取整的话会超出总时间，所以要向下。比如说 \dfrac{52}{8}=6.5，向上取整是 7，但是在 52 分钟中只有 6.5 个 8，不能到达 7 个 8，所以不能向上，而要向下。而没有欣赏 0.5 次的说法，肯定是一次一次欣赏，所以要取整）。

因为是结构体，所以我们排序要先写排序函数。

//排序函数
bool com(lim a,lim b)
{
    return a.c<b.c;
}

//第二步具体操作
if(l==1)//这边特判一下，如果只有一个完全背包樱花树就不存在比别的多花时间这种情况，所以直接转化成
{
    k++;
    w1[k]=f2[l].w;
    c1[k]=f2[l].c;
    s1[k]=m/w1[k];
}
else
{
    sort(f2+1,f2+1+l,com);//从小到大排序，注意范围
    for(int i=1;i<=l-1;i++)
    {
        bool q=0;//是否为残次品，=1为是，=0为否
        for(int j=i+1;j<=l;j++)//从小到大排序，i前面的美学值肯定小于等于i，i美学值更大，所以在前i个中肯定不算残次品，所以从i的下一个，即i+1，开始找
        {
            if(f2[i].w>f2[j].w&&f2[i].c<f2[j].c)//如果当前樱花树花的时间更长美学值反而少，说明是残次品，直接不要
            {
                q=1;//是残次品
                break;//不要
            }
        }
        if(!q)//不是残次品
        {
            k++;//处理后放入非完全背包，当作多重背包处理
            w1[k]=f2[i].w;
            c1[k]=f2[i].c;
            s1[k]=m/w1[k];
        }
    }
    k++;//最后那个是美学值最大的，肯定不是残次品，所以处理后直接放入非完全背包
    w1[k]=f2[l].w;
    c1[k]=f2[l].c;
    s1[k]=m/w1[k];
}

第三步：对非完全背包内的樱花树进行二进制拆分，将非完全背包转化为 01 背包。

对于二进制拆分，我将做出证明，即：为什么一个数 n 二进制拆分后，可以表示出 1...n 的所有数。

首先，我们要明白，二进制拆分指的是把一个自然数 n 拆分成 1+2+4+...+2^k+[n-(2^{k+1}-1)] 的形式。

解释一下中括号中的内容，前面我们已经拆出了 2^0+2^1+...+2^k 的部分，但是不一定能正好拆完，所以肯定会有剩余不能被拆分的部分，不能拆的就是 n 减去拆的部分。

我们令 S=2^0+2^1+...+2^k，即二进制拆的部分。

则 2S=2 \times (2^0+2^1+...+2^k)=2×2^0+2 \times 2^1+...+2 \times 2^k。

然后 2 就相当于 2^1，我们把以 2 为底的幂的指数相加，最后得出 2S=2^1+2^2+...+2^{k+1}。

所以 S=2S-S=(2^1+2^2+...+2^{k+1})-(2^0+2^1+...+2^k)，把同底（为 2）的幂消掉，得出 S=2^{k+1}-2^0=2^{k+1}-1。

原来是 n，二进制拆了 S，所以剩余不能被拆分的部分为 n-S=n-(2^{k+1}-1)。为了体现“整体”，所以加了中括号。

解释完之后，我们举例说明二进制拆分。以 12 为例，12=1+2+4+5，写成二进制之后为：

通过观察我们发现，每一位二进制上都有 1（最高位可以通过 4+5 进位得到），这说明我们可以通过对这些 1 进行排列组合，组成 1...n 中所有的数。

证明了二进制拆分的正确性，对于每一棵樱花树，我们对其欣赏次数进行二进制拆分，就可以凑出欣赏 1...n 次樱花中所有的次数了。

我们接下来来看代码：

int p=0;//转化成01背包后物品个数，做下标
for(int i=1;i<=k;i++)//一个一个物品拆过去，到k是因为无论之前是非完全背包还是完全背包都放在了非完全背包里
{
    for(int j=1;s1[i]>0;j<<=1)//只要还有没拆完的就继续拆，保证s1[i]>0，>=0也没关系，下面有解释，j<<=1就是说j的二进制左移一位，相当于j*=2
    {
        int d=min(j,s1[i]);
        /*s1一直在拆，如果够拆，则s1[i]中包含j的部
        分，s1[i]>=j，所以最小值返回j，是二进制拆
        分新拆出来的部分；如果不够拆，说明j超过
        s1[i]，j>s1[i]，最小值返回s1[i]，此时s1[i]
        是不够拆的剩余部分，也要把它算上。上面如果
        是s1[i]>=0的话，则会存在s1[i]=0的情况，而j
        是从1开始一直乘2，所以>0，因此这种情况下
        j>s1[i]，最小值返回s1[i]，即0，而0×d还是
        0，所以会放入时间、美学值都为0的樱花树，都
        为0既不加时间，也不加美学值，所以对dp没影
        响，也没关系*/
        p++;//放入二进制拆分的樱花树，物品个数+1
        wf[p]=d*w1[i];//时间和美学值拆成d份
        cf[p]=d*c1[i];
        s1[i]-=j;//拆的就没了
    }
}

第四步：01 背包。

模板了，不用多说，用 f[j] 表示看 j 分钟获得的最大美学值。状态转移方程为 f[j]=\max(f[j],f[j-wf[i]]+cf[i])，直接上代码。

for(int i=1;i<=p;i++)//p棵树
{
    for(int j=m;j>=wf[i];j--)
    {
        f[j]=max(f[j],f[j-wf[i]]+cf[i]);
        /*考虑看不看这颗樱花树，不看则是f[j]，看时由于
        这棵树需要wf[i]的时间，所以看这棵树必须至
        少有wf[i]的时间，而最多有m的时间，所以j的范围
        是m...wf[i]。看这棵树要wf[i]的时间，能获得
        cf[i]的美学值，所以之前要j-wf[i]的时间，看这棵
        树的美学值f[j-wf[i]]+cf[i]由于是01背包，所以要
        倒着往前扫，因为如果从前往后扫前面的用了一次，
        后面的转移时要用到前面的于是又用了一次，就不是
        01背包了，虽然对多重没什么影响，但是之前是01背
        包的樱花树就被重复看了。而从后往前，后面先看
        掉，此时前面还没看，所以没有重复，而前面的不会
        用到后面的，也不会重复后面。这样后面不重复前
        面，前面不重复后面，就是正宗、土生土长的01背包*/
    }
}

最后我们输出的答案就是 f[m]。

AC 代码

讲解中都写过注释了，所以这里不再重复写（码字不易，互相体谅，码风保证不毒瘤）。

#include<bits/stdc++.h>
using namespace std;
const int M=1005,N=10005,K=70005;
struct lim
{
    int w,c;
}f2[N];
int f[M],w1[N],c1[N],s1[N],wf[K],cf[K];
bool com(lim a,lim b)
{
    return a.c<b.c;
}
int main()
{
    //第一步
    int h1,m1,h2,m2;
    scanf("%d:%d%d:%d",&h1,&m1,&h2,&m2);
    int n,m;
    m=(h2*60+m2)-(h1*60+m1);
    scanf("%d",&n);
    int k=0,l=0;
    for(int i=1;i<=n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(z)
        {
            k++;
            w1[k]=x;
            c1[k]=y;
            s1[k]=z;
        }
        else
        {
            l++;
            f2[l].w=x;
            f2[l].c=y;
        }
    }
    //第二步
    if(l==1)
    {
        k++;
        w1[k]=f2[l].w;
        c1[k]=f2[l].c;
        s1[k]=m/w1[k];
    }
    else
    {
        sort(f2+1,f2+1+l,com);
        for(int i=1;i<=l-1;i++)
        {
            bool q=0;
            for(int j=i+1;j<=l;j++)
            {
                if(f2[i].w>f2[j].w&&f2[i].c<f2[j].c)
                {
                    q=1;
                    break;
                }
            }
            if(!q)
            {
                k++;
                w1[k]=f2[i].w;
                c1[k]=f2[i].c;
                s1[k]=m/w1[k];
            }
        }
        k++;
        w1[k]=f2[l].w;
        c1[k]=f2[l].c;
        s1[k]=m/w1[k];
    }
    //第三步
    int p=0;
    for(int i=1;i<=k;i++)
    {
        for(int j=1;s1[i]>0;j<<=1)
        {
            int d=min(j,s1[i]);
            p++;
            wf[p]=d*w1[i];
            cf[p]=d*c1[i];
            s1[i]-=j;
        }
    }
    //第四步
    for(int i=1;i<=p;i++)
    {
        for(int j=m;j>=wf[i];j--)
        {
            f[j]=max(f[j],f[j-wf[i]]+cf[i]);
        }
    }
    printf("%d\n",f[m]);
    return 0;//完结撒花，此时0:13
}

跪求过审 orz，虽然今晚麻烦了兔队很多，但还是要表示感谢！！！