【動态規劃】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;
}
           

如果有問題的話，歡迎大家指正！！！