woj 67 Weight ida

缘起

QQ群里面一道题目, 觉得有点意思, 就做了. woj 67 Weight

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
N个砝码, 你需要去称重M千克. 注意,每个砝码至多使用一次.

【输入】
多样例. 每个样例首先是N和M, 然后N个正整数, 分别是砝码的重量. 
1<=N<=30,1<=M<=2^31,1<=砝码的重量<=2^30

【输出】
对每个样例,输出最少砝码的数量

【样例输入】
3 10
5 9 1

【样例输出】
2

【限制】
1s

一开始以为是01背包的DP做法, 但是注意到M和物品的质量都太大了. 无法使用基于【1】的优化. 所以想到了dfs（确切讲是ida*, 因为n的范围仅仅是30, 比较小）. 首先预处理出k个砝码(1<=k<=n)的最小质量和最大质量. 然后对于M, M必须要在这个范围内, 所以就知道了k的搜索范围. 然后对每个k开始搜索即可.

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

typedef long long LL;

bool cmp(LL &x, LL &y){
	return x > y;
}

LL n,m, a[35], p[35], s[35], lo,hi, ans; // p是前缀和, s是后缀和, p[i]=a[1,...,i]之和, s[i]=a[n-i+1,...,n]之和

bool dfs(LL cur, LL sum, LL num) // 当前决定a[cur]的存取,sum是迄今为止的砝码重量总和(不包含cur),num是迄今为止用的砝码总数(不包含cur)
{
	if (num>ans) // ida*剪枝,注意, 不能和下面的return true交换顺序,会wa的,因为必须在num<=ans的情况下达到m才行
	{
		return false;
	}
	if (sum==m) // 如果达到
	{
		return true;
	}
	if (sum>m) // 如果当前选择的砝码重量已经超过了m,剪枝
	{
		return false;
	}
	if (sum+s[n-cur+1]<m) // 如果就算加上后面所有的也都<m, 剪枝
	{
		return false;
	}
	if (num+n-cur+1<ans) // 如果就算后面全选上, 也不能达到ans个砝码, 剪枝
	{
		return false;
	}
	if (dfs(cur+1, sum+a[cur], num+1)) // 选择砝码 a[cur]
	{
		return true;
	}
	return dfs(cur+1, sum, num); // 不选择砝码 a[cur]
}

LL ida()
{
	for (ans = lo; ans<=hi; ans++)
	{
		if (dfs(1,0,0)) // 如果ans是答案的话
		{
			return ans;
		}
	}
	return -1;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%lld%lld", &n, &m))
	{
		for (int i = 1;i<=n; i++)
		{
			scanf("%lld", a+i);
		}
		sort(a+1, a+n+1, cmp); // 降序排序
		for (int i = 1;i<=n; i++)
		{
			p[i] = p[i-1]+a[i];
		}
		for (int i = 1; i<=n; i++)
		{
			s[i] = s[i-1]+ a[n+1-i];
		}
		for (lo = 1; lo<=n; lo++)
		{
			if (p[lo]>=m && s[lo]<=m)
			{
				break;
			}
		}
		for (hi = n; hi; hi--)
		{
			if (p[hi]>=m && s[hi]<=m)
			{
				break;
			}
		} // 至此, 得到最少使用k个砝码称重m,k的搜索的范围为[lo,hi]
		printf("%lld\n", ida());
	}
	return 0;
}

ac情况

1
2
3
4
5
6
7
Accepted
#9070 code C++11
av_timer 451 ms
memory 340 KiB
access_time 2019-10-05 16:54:11
face yfsyfs
assignment 67 - Weight

参考

【1】https://yfsyfs.github.io/2019/08/19/fzu-2214-Knapsack-problem-%E8%B6%85%E5%A4%A7%E5%AE%B9%E9%87%8F01%E8%83%8C%E5%8C%85/