经过本人验证，这并非什么0-1背包问题、只是一个扩展后的找零问题。
分析：

平分marbles的问题等价于在marbles中，寻找一个组合，达到价值的1/2即可（剩下部分的价值自然是1/2）。因此，问题转化为如何寻找一个组合，使得价值 = 1/2 * value。
明显是一个用面值为1~6，凑出 1/2 * value 的找零问题。

代码如下：

// POJ 1014  dividing

#include <iostream>

using namespace std;

bool match(int (&marbles)[6], int value)
{
	if ( value == 0 ) {
		return true;
	}

	for ( int i = 6; i >= 1; --i ) {
		int n = value / i;
		n = min(n, marbles[i-1]);
		if ( n > 0 ) {
			marbles[i-1] -= n;
			if ( match(marbles, value - n * i) ) {
				return true;
			}
			marbles[i-1] += n;
		}
	}

	return false;
}


bool dividing(int (&marbles)[6])
{
	int value = 0;
	for ( int i = 0; i < 6; ++i ) {
		value += (i + 1) * marbles[i];
	}

	if ( value % 2 != 0 ) {
		return false;
	}

	return match(marbles, value / 2);
}


int main(int argc, char* argv[])
{
	int marbles[6] = {0};
	int count = 1;

	while ( true ) {
		for ( int i = 0; i < 6; ++i ) {
			cin >> marbles[i];
		}

		bool stop = true;
		for ( int j = 0; j < 6; ++j ) {
			if ( marbles[j] ) {
				stop = false;
			}
		}
		if ( stop ) {
			break;
		}

		cout << "Collection #" << count++ << ":" << endl;
		if ( dividing(marbles) ) {
			cout << "Can be divided." << endl << endl;
		} else {
			cout << "Can't be divided." << endl << endl;
		}
	}

	return 0;
}

• 这是0-2背包问题。 (1505) yygy 2015-01-16 09:29:28
  • Re:这是0-2背包问题。 (2) smfwuxiao 2015-01-16 16:05:59