拔河：将n个对象的集合int划分为子集

Question

声明：

给定一个n个整数的集合，将集合分成两个大小为n/2的子集，使两个子集之和的差值尽可能小。若n为偶数，则两个子集的大小必须严格为n/2，若n为奇数，则一个子集的大小必须为(n-1)/2，另一个子集的大小必须为(n+1)/2。

例如，设给定集为

{3, 4, 5, -3, 100, 1, 89, 54, 23, 20}

{4, 100, 1, 23, 20} 

{3, 5, -3, 89, 54}

{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;

Answer 1

我觉得这句话说得很清楚。

 // 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<<0开始，意思是“可以选择0个人，使他们的权重之和为0”。

然后，对于dp中非零的每个条目（即if(dp[j])部分），更新列表中当前人员的dp。

请注意,这个算法不会告诉您需要选择哪些数字才能得到这个和；信息丢失了。它只会告诉你最好的两个和是什么。尽管稍微修改算法并使用某种数据结构来保留这些信息并不难（例如dp中的每个条目都说“我可以从3个数字中求出这个和，这些数字是……”）。

哦，还有关于向后迭代的问题：这是为了防止我们对同一个数字进行两次计数。如果第一个条目是1，我们会说“I can make 0 from 0 numbers；now I can make 1 from 1 numbers”。紧接着，“我可以从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;
}