自动搬运

查看原文

来自洛谷，原作者为

	MuelsyseU 行き場のない声の淵か 赤い水が流れ落ちるのら

搬运于2025-08-24 21:36:55，当前版本为作者最后更新于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$时，不限制大小。

---

$dp$函数代码如下：

int dp(int k) {
	for(int j=1;j<=s;j++)			//初始化
		f[j]=0;
	for(int i=1;i<=n;i++){
		if(k!=-1&&a[i]>k) continue;	//大小限制的特判
		for(int j=s;j>=a[i];j--){	//注意倒序
			f[j]=max(f[j],f[j-a[i]]+b[i]);
		}
	}
	return f[s];
} 

教练说$find$函数模版尽量不要动，那就象征性写个$check$：

bool check(int s) {
	return dp(s)>=m;	//是否可行
}

不过，由上所述，可知在满足条件时移动的是上界，反之移动下界。所以，还要对$70$行之前的$find$函数模版略微调整：

int find(int low,int high) {
	int mid;
	while(low+1<high){
		mid=low+(high-low)/2;
		if(check(mid))	//检查可行性
			high=mid;	//上界下移
		else
			low=mid;	//否则下界上移
	} 
	return high;		//high表示可行最小值
}

至此，我们已理出了二分答案的大部分框架。

5. 代码实现

教练果然是万能的，这就是为什么这一段爆了第$3$个点的坑：

for(int i=1;i<=n;i++) {
	cin>>a[i]>>b[i];
	low=min(low,a[i]);
	high=max(high,a[i]);
}
if(dp(-1)<m) cout<<"No Solution!";
else cout<<find(low,high);

首先，我们发现$find$返回的是$high$，但是假设有极端情况，即只需要备份大小最小的文件即可达到要求时，返回的值本应当是传入的$low$。

可是，由于$low$和$high$不能重合，最后的结果最小只能是$low+1$。这就产生了问题。

只需改成cout<<find(low-1,high)即可$AC$。

$AC$代码如下：

#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(int k) {
	for(int j=1;j<=s;j++)			//由于重复使用，必须初始化
		f[j]=0;
	for(int i=1;i<=n;i++){
		if(k!=-1&&a[i]>k) continue;	//大小特判
		for(int j=s;j>=a[i];j--){	//注意倒序
			f[j]=max(f[j],f[j-a[i]]+b[i]);
		}
	}
	return f[s];
} 

bool check(int s) {
	return dp(s)>=m;
}

int find(int low,int high) {
	int mid;
	while(low+1<high){
		mid=low+(high-low)/2;
		if(check(mid))
			high=mid;
		else
			low=mid;
	} 
	return high;	//注意是high表示可行
}

int main() {
	int low=1e7,high=0;
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++) {
		cin>>a[i]>>b[i];
		low=min(low,a[i]);				//下界即最小值
		high=max(high,a[i]);			//上界是最大值
	}
	if(dp(-1)<m) cout<<"No Solution!";	//无解
	else cout<<find(low-1,high);		//注意传入low-1
	return 0;
}

6. 总结

二分与$DP$恰好是本蒟蒻最近大肆被虐之算法，所以一看到此题便觉神清气爽。

似乎思路中规中矩，不过有些小优化，但个人感觉讲的还是蛮清晰的。

这是第$335$行。感谢阅读到这里的诸位。

以上。