【动态规划】POJ 1014 Dividing

这段时间要沉迷刷题一段时间了，就让CSDN陪我一起吧！

一、题目大意

这道题目的大致意思就是，两个小孩有一堆弹珠，然后想把他平分，但是不同的球有不同的价值，分为6个档次(1…6)，所以这样的话，有的情况是无法平分的，即使总价值是偶数，比如1个价值为1的弹珠，1个价值为3的弹珠，2个价值为4的弹珠，这样是没办法平分的，所以想让你编写一个程序来判断是否可以平分。输入是6个数，分别是ni，是价值为i的弹珠的个数。

二、题目思路以及AC代码

因为最近都在刷动态规划的题，所以看到这题的时候，就想到了POJ 1837那道题，类似，但不完全一样，所以我最开始想的办法是，定义一个dp[i][j]，其含义是在前i个物体中挑，使得价值等于j的挑法(也就是挑的种类数)，这样自然是可以的，你最终需要求得的结果就是dp[6][total/2]，total是给定弹珠的总价值。

但后来发现discuss中有人内存用的比我少，我在琢磨为啥呢？不都是多重背包吗？然后我就看了人家的代码，人家同样定义了dp[i][j]，但类型是bool类型，这是什么意思呢？因为这道题只要求你告诉它是否可以平分，所以你只需要定义dp[i][j]为在前i个物体中挑，如果存在使得价值等于j的挑法，那么dp[i][j]为1，否则为0，即可，这样，一下子就节省了75%的空间！哎，我还是太年轻！

上述两种做法都是可以的，都可以AC，区别我也在上边已经说过了，这里给出两种方法的递推公式：

• 第一种：dp[i][j] = dp[i-1][j] + dp[i-1][j-v[i]]
• 第二种：dp[i][j] = dp[i-1][j-v[i]]

（注意，v数组是已经用二进制优化分离完的数组）

还需要注意的是，一般的ACM考题，如果考到背包问题，最好直接用它的空间优化，可以避免debug的烦躁。(友情提示)

下面给出后一种做法的AC代码：(前一种方法其实也是一样，无非递推公式换一换)

#include <iostream>
#define MAXN 7
#define MAXC 500000
using namespace std;

int dp[MAXC];
int num[MAXN];
int n[1000];

int Max(int a, int b) {
	return a > b ? a : b;
}

void init() {
	for (int i = 0; i < MAXN; i++) {
		n[i] = 0;
	}
	for (int j = 0; j < MAXC; j++) {
		dp[j] = 0;
	}
}

int computeSum() {
	int res = 0;
	for (int i = 1; i <= 6; i++) {
		res += num[i] * i;
	}
	return res;
}

int main()
{
	int Case = 1;

	while (scanf("%d%d%d%d%d%d", &num[1], &num[2], &num[3], &num[4], &num[5], &num[6]) != EOF) {
		if (!num[1] && !num[2] && !num[3] && !num[4] && !num[5] && !num[6]) {
			break;
		}
		init();

		int total = computeSum();

		if (total & 1) {
			printf("Collection #%d:\n", Case++);
			printf("Can't be divided.\n\n");
			continue;
		}
		int halfTotal = total / 2;

		int cnt = 1;
		for (int i = 1; i <= 6; i++) {
			int k = 1;
			while (k < num[i]) {
				n[cnt++] = k * i;
				num[i] -= k;
				k *= 2;
			}
			if (num[i]) {
				n[cnt++] = num[i] * i;
			}
		}

		dp[0] = 1;
		for (int i = 1; i < cnt; i++) {
			for (int j = halfTotal; j >= n[i]; j--) {
				dp[j] = dp[j] + dp[j - n[i]];
			}
		}

		if (dp[halfTotal]) {
			printf("Collection #%d:\n", Case++);
			printf("Can be divided.\n\n");
		}
		else {
			printf("Collection #%d:\n", Case++);
			printf("Can't be divided.\n\n");
		}
	}

    return 0;
}
           

如果有问题的话，欢迎大家指正！！！