洛谷P1537题：用多重背包解决弹珠平分问题
一、问题分析
洛谷P1537题要求我们判断给定数量的不同价值弹珠能否被分成两组，使得两组的总价值相等。这实际上是一个典型的多重背包问题，我们需要判断是否能够选择一些弹珠，使它们的总价值恰好为所有弹珠总价值的一半。
二、算法选择
这个问题可以使用动态规划来解决，具体来说是多重背包问题的变种。我们需要考虑每种价值的弹珠有多个，而不是传统的01背包问题中每个物品只有一个。
三、动态规划思路
状态定义：定义DP[j]表示达到价值j时，还能使用当前种类弹珠的数量。
初始化：dp[0] = 0，表示价值0不需要任何弹珠。
状态转移：
如果dp[j] ≥ 0，说明价值j可以达到，且还能使用marbles[i]个当前种类的弹珠
如果j ≥ i且dp[j-i] > 0，说明可以通过使用一个价值i的弹珠达到价值j
结果判断：检查dp[half]是否≥0，其中half是总价值的一半
四、代码逻辑
1.输入处理：读取每种价值弹珠的数量，并计算总价值
2.初步判断：如果总价值为奇数，直接输出不可能
3.动态规划实现：使用双重循环实现多重背包的状态转移
4.输出结果：根据dp数组判断是否能平分并输出结果
五、完整代码：
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_SUM = 60000; // 最大可能的总价值(20000*6)/2
int dp[MAX_SUM]; // dp数组
int marbles[7]; // 存储每种价值弹珠的数量
int main() {
int caseNum = 1;
while (true) {
int total = 0; // 总价值
bool end = true;
// 读取输入
for (int i = 1; i <= 6; i++) {
cin >> marbles[i];
total += marbles[i] * i;
if (marbles[i] != 0) end = false;
}
// 结束条件
if (end) break;
cout << "Collection #" << caseNum++ << ":" << endl;
// 总价值为奇数，直接不可能平分
if (total % 2 != 0) {
cout << "Can't be divided." << endl << endl;
continue;
}
int half = total / 2; // 每人应得的价值
memset(dp, -1, sizeof(dp)); // 初始化dp数组
dp[0] = 0; // 基础情况：价值0不需要任何弹珠
// 多重背包动态规划
for (int i = 1; i <= 6; i++) {
if (marbles[i] == 0) continue;
for (int j = 0; j <= half; j++) {
if (dp[j] >= 0) {
dp[j] = marbles[i]; // 可以完全使用这种弹珠
} else if (j >= i && dp[j - i] > 0) {
dp[j] = dp[j - i] - 1; // 使用一个i价值的弹珠
}
}
}
// 判断是否能达到half价值
if (dp[half] >= 0) {
cout << "Can be divided." << endl;
} else {
cout << "Can't be divided." << endl;
}
cout << endl; // 每组数据后空一行
}
return 0;
}原创内容 转载请注明出处
