poj 3172 Scales 01背包 深搜+剪枝

缘起

【1】中我们介绍了01背包的动态规划解法. 其实01背包问题有三种解法

分析

  1. dp （【1】中已介绍）
  2. dfs+剪枝（不剪枝是不行的，复杂度太高）
  3. bfs（即所谓的分支限界），一般使用FIFO队列或者优先队列, 即所谓的普通队列之分支限界以及优先队列之分支限界.

本文介绍第二种，至于第三种复杂度太高，用于oj肯定被T掉. 注意，01背包的贪心是错误的（但是贪心的结果作为近似最优解可以拿来做剪枝）.

题意

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
约翰有一架用来称牛的体重的天平．与之配套的是N(1≤N≤1000)个已知质量的砝码（所有砝码质量的数值都在31位二
进制内）．每次称牛时，他都把某头奶牛安置在天平的某一边，然后往天平另一边加砝码，直到天平平衡，于是此时砝
码的总质量就是牛的质量（约翰不能把砝码放到奶牛的那边，因为奶牛不喜欢称体重，每当约翰把砝码放到她的蹄子底
下，她就会尝试把砝码踢到约翰脸上）．天平能承受的物体的质量不是无限的，当天平某一边物体的质量大于
C(1≤C<230)时，天平就会被损坏．    砝码按照它们质量的大小被排成一行．并且，这一行中从第3个砝码开始，每
个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和．    约翰想知道，
用他所拥有的这些砝码以及这架天平，能称出的质量最大是多少．由于天平的最大承重能力为C．他不能把所有砝码都
放到天平上．
    现在约翰告诉你每个砝码的质量，以及天平能承受的最大质量．你的任务是选出一些砝码，
使它们的质量和在不压坏天平的前提下是所有组合中最大的．

【输入】
第1行：两个用空格隔开的正整数N和C. 1 <= N <= 1000，1 <= C < 2^30
第2到N+1行：每一行仅包含一个正整数，即某个砝码的质量．保证这些砝码的质量是一个不下降序列

【输出】
一个正整数，表示用所给的砝码能称出的不压坏天平的最大质量．

【样例输入】
3 15
1
10
20

【样例输出】
11

【限制】
Time Limit: 1000MS
Memory Limit: 65536K

题目大意，给你n个砝码，你需要挑出一些砝码来使重量总和最大但不超过C

本题显然是一个01背包问题，背包容量是C. 每个物品的价值和耗费相等都是其重量

因为背包容量太大了，所以本题使用DP来解决01背包是不行的. 要使用深搜+剪枝解决（不剪枝也是不行的，因为2^N 太大）

首先展示我被T掉的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include "stdafx.h"

#include <stdio.h>
#define LOCAL

typedef long long LL;

LL V,N,ans=-1,c[1005], w[1005];

void dfs(LL i,LL v, LL worth, LL tot) // 现在决定(ci,wi)是否选取, 当前还剩余v的背包容量, worth是当前背包中的物品价值,tot是[1,..,i]这i件物品的总价值
{
	if (!i) // 说明已经得到了一种背包组合了
	{
		if (worth>ans)
		{
			ans = worth;
		}
		return;
	}
	if (worth+tot<=ans) // 剪枝——如果当前境况就算后面的物品全选也无法超越当前的最大值ans的话, 就剪枝
	{
		return;
	}
	dfs(i-1, v, worth,tot-w[i]); // 不放(ci,wi)
	if (v>=c[i]) // 如果放得下(ci,wi)
	{
		dfs(i-1, v-c[i], worth+w[i], tot-w[i]);
	}
}

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%lld%lld", &N, &V);
	LL tot = 0;
	for (LL i = 1; i<=N; i++)
	{
		scanf("%lld",c+i);
		w[i] = c[i];
		tot+=w[i];
	}
	dfs(N,V,0,tot);
	printf("%lld\n", ans);
	return 0;
}

再来看一种被T掉的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

typedef long long LL;

LL V,N,ans=-1,c[1005], w[1005];

void dfs(LL i,LL v, LL worth, LL tot) // 现在决定(ci,wi)是否选取, 当前还剩余v的背包容量, worth是当前背包中的物品价值,tot是[i,..,N]这N-i+1件物品的总价值
{
	if (i==N+1) // 说明已经得到了一种背包组合了
	{
		if (worth>ans)
		{
			ans = worth;
		}
		return;
	}
	if (worth+tot<=ans) // 剪枝——如果当前境况就算后面的物品全选也无法超越当前的最大值ans的话, 就剪枝
	{
		return;
	}
	if (v>=c[i]) // 如果放得下(ci,wi)
	{
		dfs(i+1, v-c[i], worth+w[i], tot-w[i]);
	}
	dfs(i+1, v, worth,tot-w[i]); // 不放(ci,wi)
}

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%lld%lld", &N, &V);
	LL tot = 0;
	for (LL i = 1; i<=N; i++)
	{
		scanf("%lld",c+i);
		w[i] = c[i];
		tot+=w[i];
	}
	dfs(1,V,0,tot);
	printf("%lld\n", ans);
	return 0;
}

然后是ac的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

typedef long long LL;

LL V,N,ans=-1,c[1005], w[1005];
LL count; // dfs次数

void dfs(LL i,LL v, LL worth, LL tot) // 现在决定(ci,wi)是否选取, 当前还剩余v的背包容量, worth是当前背包中的物品价值,tot是[1,..,i]这i件物品的总价值
{
	//count++; // 记录递归次数
	if (!i) // 说明已经得到了一种背包组合了
	{
		if (worth>ans)
		{
			ans = worth;
		}
		return;
	}
	if (worth+tot<=ans) // 剪枝——如果当前境况就算后面的物品全选也无法超越当前的最大值ans的话, 就剪枝
	{
		return;
	}
	if (v>=c[i]) // 如果放得下(ci,wi)
	{
		dfs(i-1, v-c[i], worth+w[i], tot-w[i]);
	}
	dfs(i-1, v, worth,tot-w[i]); // 不放(ci,wi)
}

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%lld%lld", &N, &V);
	LL tot = 0;
	for (LL i = 1; i<=N; i++)
	{
		scanf("%lld",c+i);
		w[i] = c[i];
		tot+=w[i];
	}
	dfs(N,V,0,tot);
	printf("%lld\n", ans);
	//printf("%lld\n", count);
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 104kB
Length 841
Lang C++
Submitted 2019-08-18 20:24:42
Shared
RemoteRunId 20763602

注意，其实被T掉的2份代码和ac的代码其实长得很像，只是顺序变了而已. 为什么顺序变了就T了?

其中第一份被T掉的代码顺序坏在先考虑不放再考虑放，第二份被T掉的代码顺序坏在从价值小的开始深搜. 而ac代码从价值大的开始深搜，而且先考虑放，再考虑不放. 就可以ac而不会超时. 这是为什么呢?

其实我们知道唯一的剪枝手段就是如果当前价值+剩下物品的价值之和<当前ans的话, 就剪枝. 所以想要快速剪枝最好的办法就是快速增大ans. 而快速增大ans的手段就是ac代码做的——从价值最大的开始（注意，因为本题特殊性，每个物品的价值=耗费）深搜. 而且先考虑放，后考虑不放. 就能实现快速增大ans进而提高剪枝效率， 从而ac.

注意，其实本题提供了一种非常普适的剪枝手段哦~ 而且可以使用一个全局变量count像ac代码那样打印深搜次数你会有一个惊人的发现N=50的时候——仅仅递归了15588次!!! 在不加任何剪枝情况下, dfs理论上要进行 2^50, 这是一个什么概念? 达到了惊人的1e15数量级. 但是剪枝之后——仅仅需要递归1e4!!! 可见ac代码的剪枝是多么的强力!!!

ps: 其实本题的价值按照斐波那契数列增长起到的作用就是能快速剪枝，如果对于价值增长无规律，例如【1】中的题目，则即便使用本题的剪枝手法依旧是会被T掉的——只能使用dp

参考

【1】https://yfsyfs.github.io/2019/08/18/%E7%99%BE%E7%BB%83oj-2773-%E9%87%87%E8%8D%AF-01%E8%83%8C%E5%8C%85/