> 经过本人验证，这并非什么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;
> }

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