POJ 1014 Dividing

題意：
    每次有n1,n2,n3,n4,n5,n6六個數字代表價值1的大理石有n1個，價值2的大理石有n2個，....，價值6的大理石有n6個，現在要將這些大理石分成兩堆，問能否使得這兩堆價值一樣？

想法：
    背包問題，一開始單純把價值i的大理石做了ni次，例如價值5有70個，for迴圈就跑70次，結果就TLE了。
    後來學到其實可以將70 = 1+2+4+8+16+32+7，也就是ni=1+2+4+8+....+2^x+left，這樣可以大大減少for的次數，ni如果是70只要做6+7=13次。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int dp[6*20001];
	int main()
	{
	int n[7], Case = 1;
	while (1) {
	// Input
	int sum = 0;
	for (int i = 1; i <= 6; ++i) {
	scanf("%d", &n[i]);
	sum += (i*n[i]);
	}
	if (!sum) break;
	printf("Collection #%d:\n", Case++);
	// Knapsack
	if (sum & 1) puts("Can't be divided.\n");
	else {
	sum /= 2;
	fill(dp, dp+sum+1, 0);
	for (int i = 1; i <= 6; ++i) {
	int left = n[i];
	for (int j = 1; j <= left; left -= j, j *= 2)
	for (int k = sum; k - i*j >= 0; --k)
	dp[k] = max(dp[k], dp[k-i*j] + i*j);
	for (int j = 0; j < left; ++j)
	for (int k = sum; k - i >= 0; --k)
	dp[k] = max(dp[k], dp[k-i] + i);
	}
	if (dp[sum] == sum) puts("Can be divided.\n");
	else puts("Can't be divided.\n");
	}
	}
	}

view raw [POJ] 1014 Dividing.cpp hosted with ❤ by GitHub