题解 P2370 【yyy2015c01的U盘】

MuelsyseU · 2019-12-08 16:30:06 · 题解

1. 前言

立志作超长题解的本蒟蒻，自从上次水完书的复制300行，并发现竟排在第5页后，便再没看到打算写题解的二分题。

但这道P2370，不得不说是一道好题。

虽说据说竟无需二分（震惊！贪心时间竟仅二分的十分之一），但毕竟是为数不多的将01背包与二分结合的普及题。

在此小议百行，聊以复习罢。

2. 01背包简述

此题大致意思为：

现有U盘一个，需在其中备份N个文件。每个文件有大小W_i及价值V_i，且备份的文件总价值不得小于M。U盘有总容量限制S，同时其内部的任何文件大小不得超过一个值L（此值可变）。需求出是否能备份足够价值的文件，如果能，至少需要多大的L。

上述内容可能比较抽象，同时本题数据较多，建议还是回题目中仔细分析一下。

首先，我们可以发现，如果去除求L的要求，该题将是一个纯粹的01背包问题。只需根据01背包求出最大价值与M比较即可。

以下简述背包问题的思想，dalao可跳过

貌似众dalao均用了一维数组，这边还是先开二维，到时再压缩作一维。

设f[i][j]表示对于前i个文件在容量为j时，最终可得到的的最大价值。

如何推出f[i][j]呢？考虑对第i个文件，可取或不取。

若不取，则f[i][j]与f[i-1][j]完全相同；

若取，则至少需w[i]的空间，至多剩余j-w[i]的空间，以换取v[i]的价值。由此可知，此时价值可由f[i-1][j-w[i]]+v[i]推出。

则最终状态转移方程为：f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])

最后的最大价值即为f[n][s]。

然后我们一看数组，发现f数组分别以文件编号和可用空间大小作为下标，于是有：

int f[1000][1000000];

注：当然，此处还需预留空间，数组实际还要更大。

显然爆空间。于是乎，我们需要考虑压缩到一维数组，即f[1000000]。

由上述内容可以看出，在计算第i个文件时，仅需使用f[i-1][]的数据，其前的值可以舍弃——最终可直接舍弃f[n][]之前的所有值。

这样看来，不妨直接使用方程f[j]=max(f[j],f[j-w[i]]+v[i])。

仔细观察方程，可发现每次i循环都更新了f[]中的值，这样，在执行完第i-1层循环后，f数组就保存了第i-1层的所有数据。

其后第i层循环，实际上也就等同于使用max(f[i-1][j],f[i-1][j-w[i]]+v[i]))来更新f[i][j]。

这种办法的妙处在于，每次更新完f数组，f数组所表示的层数就不同了，但仍能保证状态转移的正确（其实比二维更正确，因为少了一个状态转移的判断）。

最终，就能求出总共n个文件的最大价值。可能稍有些难理解，但认真思考就能明白其中的道理了。

关于DP部分代码的实现，其实到此已没什么难点。

但要注意，为了防止一个物品被重复选用，内层j必须倒序遍历，这样使用的是之前的数据，而不会使用到新的数据（如果是完全背包本就可以无限使用则直接改为正序即可）。

于是我们现在已经可以求出是否有解的部分分：

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

int n,m,s;
int a[1005],b[1005];
int f[1000010];

int dp() {
    for(int j=1;j<=s;j++)           //初始化 
        f[j]=0;
    for(int i=1;i<=n;i++){
        for(int j=s;j>=a[i];j--){   //注意倒序 
            f[j]=max(f[j],f[j-a[i]]+b[i]);
            //状态转移 
        }
    }
    return f[s];                    //最终结果即f[s] 
} 

int main() {
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++) {
        cin>>a[i]>>b[i];
    }
    if(dp()<m) cout<<"No Solution!";//无解 
    return 0;
}

3. 二分基本思想

然而，题目中还有一个至关重要的因素：L值的确定。

由于L值是文件体积的最大值，我们要让它尽量小。“最大值最小”，嗯，典型的二分答案思想。

简述二分答案的基本思想， dalao也可跳过

二分答案的理解疑似是来自二分查找 （并不），二分查找的理解疑似是来自“猜数游戏”。

1 2 4 10 29 30 31 65

假设预选一个数作为答案，让玩家每次对其中一个数进行询问。

每个询问可能回答：该数比答案大、比答案小或猜中答案。

如果该数即是答案则游戏结束。

那么，希望用最少的询问次数猜出答案，就可以用二分查找法。

由于数列单调上升，试想先取一中间数如10，如果回答“太小”，则“嫌疑”范围肯定是10-65（方便起见这里把10考虑进去）这一段4个数；如果“太大”则嫌疑范围会取到1-10。

可以再在新的嫌疑范围中取该范围的中间数来询问，比如询问10-65中的30；之后再在新的范围中取中间数……可以预见，最多询问3次（从实际编码角度可能理解为4次）就能确定这个答案。

简单讲讲代码实现。二分，顾名思义要将数据分成两类，比如小于等于X和大于X两类。分类要求不重不漏且满足单调。

定义low和high表示“嫌疑范围”的上下界，由于可知当“嫌疑范围”确定到一点时即结束，所以循环条件为low+1<high。（技巧：初始化low=0,high=n+1）

结束时，可发现数据已被分成了[a[0],a[low]]和[a[high],a[n]]两类。这时就可据low,high找到“最接近X的、次接近X的、大于X且最接近X的”值等。

其实做这道题应该对二分查找有较深理解的，所以这里只是简述一下，接下来不再讲。

二分答案基于二分原理，即用二分的思想快速“猜出”最合适的答案。当且仅当：

1. 题目难以用直接数学方法解出；
2. 题目用逐步验证的方法相对容易解出，但暴力枚举又容易超时；
3. 答案有明显的范围，且范围时间上允许二分答案（时间复杂度一般近似O[log_2(right-left+1)]）；
4. 问题的答案是单调的（反复强调的重点），即当验证答案X满足条件，则[n,right]或[left,n]也一定满足；不满足时，也可表明[left,n]或[n,right]也一定不满足。

满足以上条件时，二分答案就可以使用且可能显著优化时间复杂度。

注意一点，二分答案实际上仍然属于穷举的优化，其基本思路也是需要一个个查找验证，所以check验证函数的编写是二分答案的核心。比较容易地是采用贪心法或动规验证。

由于仍然是需要分界，因此分成可行与不可行两类。比以下模板是最后找到的low就是可行的最大值。

接下来有个无需ans的蒟蒻模版，也就是将一般low=mid+1,high=mid-1改成直接赋值为mid。

实际上可发现mid本身是不需再确定的，所以此模板把时间复杂度略微抬高但较容易理解。

int find(int low,int high) {
    int mid;
    while(low+1<high){          //找到可行与不可行的分界
        mid=low+(high-low)/2;   //此处是(low+high)/2的防爆优化
        if(check(mid))          //check函数检查可行性
            low=mid;            //当可行时[left,mid]也可行
        else
            high=mid;           //当不可行时[mid,right]也不可行
    } 
    return low;                 //由于low表示可行，返回low
}

关于二分答案，最适合练手的个人认为是木材加工。

4. 二分解题思路

以上已唠叨近两百行，现在总算开始讲解题思路 （鼓掌！）。

首先明确我们要二分查找什么？顾名思义，要二分的一般是“答案”。

所以，我们应当枚举这个L值，也就是接口的大小。

现在倒回去看二分答案的四个要素。这个值肯定很难用数学方式或暴力枚举来解(1,2-2)，并且这个最小值也存在范围(3)：从所有文件大小的最小值到所有文件大小的最大值。

这个范围也容易理解。首先根据数据，所需价值至少为1，接口大小至少为“所有文件大小的最小值”才能通过至少一个文件；

而由于接口大小越小越好，所以只要达到“所有文件大小的最大值”，即可保证可通过所有文件，自然不需要更大。

粗略计算可发现这个范围用二分答案是完全允许的。（大约只需不到十次验证）

现在只剩两个要素(4,2-1)，也就是单调性和如何逐步验证。

先考虑单调性。设想我们已经验证，接口大小的最小值小于等于30，那么是不是肯定小于等于31？

再假设已知这个最小值肯定大于11页，那么是不是肯定也会大于10页？

换言之，当某个答案可行时，比它大的答案也肯定可行，无需再验证，上界就可以减小；同理，当某个答案不可行，比它小的答案也肯定不可行，下界就要上移。

所以单调性是完全满足的。

最后考虑，我们如何验证答案是否可行？如前所述，由于我们假想已知这个“接口大小的最小值”，只需要求出对应所需的最大价值，然后判断是否足够。

发现了什么？刚才的DP恰好可以用于求出这个最大价值。

只需在进行内层j循环前，增加一个判定，看第i个文件大小是否超过接口大小，如果超过即跳过这个文件。

此处有一个小细节。由于判断之前是否有解时，是没有接口大小的限制的，所以增加判定，当传入的这个mid是-1时，不限制大小。