我在网上练习算法时发现了一个拔河问题：
声明：
给定一个由n个整数组成的集合，将该集合划分为两个子集，每个子集的大小为n/2，使得两个子集之和的差尽可能小。如果n是偶数，则两个子集的大小必须严格为n/2，如果n是奇数，则一个子集的尺寸必须为（n-1）/2，而另一个子集必须为（n+1）/2。
例如，设给定集合为
{3, 4, 5, -3, 100, 1, 89, 54, 23, 20}
套装的尺寸是10。此集合的输出应为
{4, 100, 1, 23, 20}
和
{3, 5, -3, 89, 54}
两个输出子集的大小都是5，并且两个子集中的元素之和是相同的（148和148）。
让我们考虑另一个例子，其中n是奇数。设给定集合为
{23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}
输出子集应为
{45, -34, 12, 98, -1}
和
{23, 0, -99, 4, 189, 4}
两个子集中元素的和分别为120和121。
我在网上找到了一种背包式的方法，同时在这里寻找解决方案：
我没有得到解决方案的这一部分：
for (int i = 1; i <= N; ++i)
for (int j = sum; j >= 0; --j)
if (dp[j])
dp[j + W[i]] |= dp[j] << 1;
我知道我们正在试图找到占I和的对象的数量。但做dp[i] << 1是我没有得到正确的东西：
此外，为什么我们要向后迭代j变量，从sum到0？为什么不用0求和呢？
有人能用更简单、更概括的方式告诉我底层逻辑吗？
感谢
实际上，我认为注释非常清楚。
// If (dp[i] << j) & 1 is 1, that means it is possible
// to select j out of the N people so that the sum of
// their weight is i.
从初始条件dp[0]＝1<lt；0，意思是"可以选择0个人，使他们的体重总和为0"。
然后，对于dp中的每个非零条目（即if (dp[j])部分），更新列表中当前人员的dp。
现在，你特别问"为什么dp[j] << 1"？假设前三个元素是1,2,3。
那么dp[3]将是二进制的110，意思是"你可以用一个人（3）或两个人（1和2）求3的和
如果下一个数字是10，那么当我们谈到dp[3]时，我们做dp[3+10] |= dp[3] << 1，使dp[13]1100。意思是"由于我们可以用两个人或一个人制作3个，再加上10个，我们可以用3个人（1、2、10）或2个人（3、10）制作13个"
最后，你所需要做的就是在dp中寻找最接近总和一半的条目。当然，另一个团队的总和将是总和减去这个值。
注意，这个算法不会告诉你需要选择哪些数字才能得到那个和；该信息丢失。它只会告诉你最好的两个和是什么。尽管稍微修改算法并使用一些数据结构来保留信息并不困难（例如dp中的每个条目都说"我可以从3个数字中求和，，这些数字是…"）
哦，关于向后迭代：这是为了防止我们对同一个数字计数两次。如果第一个条目是1，我们会说"我可以从0个数字中得出0；现在我可以从1个数字中得到1"。然后紧接着，"我可以从1个数字中得出1；现在我可以从2个数字中得到2"。等等。
编辑：既然你问了，这里有一种方法（注意，如果你输入非正数，它会坏掉，我让你来解决这个问题）：
int N;
int W[100 + 5];
std::map<int, std::vector<int>> dp[450 * 100 + 5];
void solve()
{
int sum = accumulate(W + 1, W + N + 1, 0);
// If (dp[i][j]) contains a nonempty vector, that means it is possible
// to select j out of the N people so that the sum of
// their weight is i, with those people's indices being the values of said vector
dp[W[1]][1].push_back(1);
for (int i = 2; i <= N; ++i)
{
for (int j = sum; j >= 0; --j)
{
for (std::map<int, std::vector<int>>::iterator it = dp[j].begin(); it != dp[j].end(); ++it)
{
dp[j + W[i]][it->first+1] = it->second;
dp[j + W[i]][it->first+1].push_back(i);
}
}
}
std::vector<int> selected;
int minDiff = 450 * 100;
int teamOneWeight = 0, teamTwoWeight = 0;
for (int i = 0; i <= sum; ++i)
{
if (!dp[i].empty())
{
int diff = abs(i - (sum - i));
if (diff < minDiff)
{
minDiff = diff;
teamOneWeight = i;
teamTwoWeight = sum-i;
selected = dp[i].begin()->second;
}
}
}
cout << "Team 1, sum of " << teamOneWeight << ": ";
for (int i = 1; i <= N; ++i)
{
if (std::find(selected.begin(), selected.end(), i) != selected.end())
cout << W[i] << ' ';
}
cout << endl << "Team 1, sum of " << teamTwoWeight << ": ";
for (int i = 1; i <= N; ++i)
{
if (std::find(selected.begin(), selected.end(), i) == selected.end())
cout << W[i] << ' ';
}
cout << endl;
}
基本方法
这种方法可以被认为是使用动态编程来计算三维阵列f的内容。
f定义为：
f[i][sum][j] = 1，如果可以使用1..i范围内的权重中的j来产生总和的总权重。
现在假设我们知道f[i][sum][j]对于i，sum，j的一些值是1。如果我们决定包括权重i，那么我们推断f[i+1][sum+W[i]][j+1]也必须是真的。
f[i+1][sum+W[i]][j+1] |= f[i][sum][j]
如果我们不包括权重i，那么我们推断f[i+1][sum][j]也一定是真的。
优化1
第一个优化是将第三维存储在单个64位整数中，而不是64个1位整数中。这使得代码运行得更快。
假设f[i][sum]=二进制1001，这意味着对于等于0或3的j，f[i][sum][j]是1。我们现在得出结论，对于j等于1或4，我们需要将f[i][sum+w[i]][j]设置为等于1，因此我们需要与二进制10010=1001<lt；1，这解释了<lt；1次操作。
优化2
第二个优化是发现我们可以对i的所有值重用相同的数组，但是要做到这一点，我们需要向后迭代，否则我们会认为我们可以多次使用第i个元素。