uva uva 562 Dividing coins 01背包

缘起

日常水题 uva 562 Dividing coins 就是01背包, 而且因为费用=价值, 所以可以借鉴【1】中那样优化

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给你至多100枚硬币（硬币的价值在[1,500]范围内），要你找一种差距最小的平分成两堆的方式,输出最小差距.

【输入】
多样例，第一行是样例数t, 每个样例由硬币的枚数n, 然后n个数字分别是n枚硬币的价值

【输出】
输出最小差距

【样例输入】
2
3
2 3 5
4
1 2 4 6

【样例输出】
0
1

【限制】
Time limit 3000 ms

其实就是背包——首先求出所有硬币的价值之和sum, 然后sum>>1 得到分得较少的一堆最多这么多钱. 然后每枚硬币看做物品，这些物品的费用=价值，所以可以使用true或false.

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
//#include "stdafx.h"

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

int n,V,a[105],sum; // a[i]是硬币的价值
bool dp[30000]; // true 表示可以达到(因为100枚硬币，每枚硬币最多100, 所以最多5w, 除以2，小于3w)

void zo(int i)
{
	for (int j = V; j>=a[i]; j--)
	{
		dp[j] = dp[j]||dp[j-a[i]];
	}
}

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		memset(dp,0,sizeof(dp));
		dp[0]=true;
		sum = 0;
		scanf("%d",&n);
		for (int i = 1; i<=n;i++)
		{
			scanf("%d", a+i);
			sum+=a[i];
		}
		V=(sum>>1);
		for (int i = 1; i<=n;i++)
		{
			zo(i);
		}
		while(!dp[V])V--;
		printf("%d\n", sum-(V<<1));
	}
	return 0;
}

ac情况

Status Accepted
Length 686
Lang C++11 5.3.0
Submitted 2019-08-19 14:07:33
Shared
RemoteRunId 23788006

参考

【1】https://yfsyfs.github.io/2019/08/19/uva-624-CD-01%E8%83%8C%E5%8C%85-%E8%BE%93%E5%87%BA%E6%9C%80%E4%BC%98%E6%96%B9%E6%A1%88%E6%A8%A1%E6%9D%BF/