HDU 1059 Dividing dp 백팩 문제 해결

배낭 문제, 이런 종류의 문제는 응용이 매우 넓다.
이 문제는 특례에 따라 최적화할 수 있다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAX_N = 20001;
const int ARR_SIZE = 6;
int N, arr[ARR_SIZE], tbl[MAX_N * ARR_SIZE];

bool dividable(int sum)
{
	if (sum & 1) return false;
	int half = sum >> 1;

	memset(tbl, 0, sizeof(int) * (half+1));
	tbl[0] = 1;
	for (int i = 0; i < ARR_SIZE; i++)
	{
		if (arr[i] == 0) continue;
		int v = i+1;
		for (int j = 0; j <= half; j++)
		{
			if (tbl[j]) tbl[j] = arr[i]+1;
			else if (j >= v && tbl[j-v] > 1)
			{
				tbl[j] = tbl[j-v] - 1;
			}
		}
	}
	return tbl[half] > 0;
}

int main()
{
	int minNum, sum, t = 1;

	while (true)
	{		
		minNum = INT_MAX;
		sum = 0;
		for (int i = 0; i < ARR_SIZE; i++)
		{
			scanf("%d", arr+i);
			minNum = min(minNum, arr[i]);
			sum += arr[i] * (i+1);
		}
		if (0 == sum) break;//    

		if (t > 1) putchar('
');
		printf("Collection #%d:
", t++);
		if (sum & 1)//  
		{
			puts("Can't be divided.");
			continue;
		}

		if (minNum)//  
		{
			for (int i = 0; i < ARR_SIZE; i++)
			{
				arr[i] -= minNum;
				sum -= (i+1) * minNum;
			}
			if (minNum & 1)
			{
				arr[2] += 1, arr[3] += 1;
				sum += 3 + 4;
			}
		}

		if (dividable(sum)) puts("Can be divided.");
		else puts("Can't be divided.");
	}
	return 0;
}

HDU 1059 Dividing dp 백팩 문제 해결

좋은 웹페이지 즐겨찾기