python - 列表元素的公平划分

Question

给定玩家的评分列表，我需要尽可能公平地将玩家(即评分)分为两组。目标是最小化球队累积评分之间的差异。对于如何将玩家分成团队没有任何限制(一个团队可以有 2 名玩家，另一支团队可以有 10 名玩家)。

例如:[5, 6, 2, 10, 2, 3, 4] 应返回 ([6, 5, 3, 2], [10, 4, 2 ])

我想知道解决这个问题的算法。请注意，我正在学习在线编程入门类(class)，因此简单的算法将不胜感激。

我正在使用以下代码，但由于某种原因，在线代码检查器显示它不正确。

def partition(ratings):
    set1 = []
    set2 =[]
    sum_1 = 0
    sum_2 = 0
    for n in sorted(ratings, reverse=True):
        if sum_1 < sum_2:
            set1.append(n)
            sum_1 = sum_1 + n
        else:
            set2.append(n)
            sum_2 = sum_2 + n
    return(set1, set2)

更新:我联系了讲师，他们告诉我应该在函数内定义另一个“辅助”函数来检查所有不同的组合，然后我需要检查最小差异。

Answer 1

注意:进行编辑是为了更好地处理所有数字之和为奇数的情况。

回溯是解决此问题的可能性。

它允许递归地检查所有可能性，而不需要大量内存。

一旦找到最佳解决方案，它就会停止:sum = 0 ，其中sum是集合 A 的元素之和与集合 B 的元素之和之间的差。编辑:它会立即停止 sum < 2 ，处理所有数字之和为奇数的情况，即对应最小差值为1。如果这个全局和为偶数，则最小差值不能等于1。

它允许实现过早放弃的简单程序:
在给定时间，如果 sum大于所有剩余元素(即未放入 A 或 B 中的元素)加上当前获得的最小值的绝对值的总和，那么我们可以放弃检查当前路径，而不检查剩余元素。此过程经过优化:

• 按降序对输入数据进行排序
• 每一步，首先检查最可能的选择:这样可以快速找到接近最佳的解决方案

这是一个伪代码

初始化:

• 对元素进行排序 a[]
• 计算剩余元素的总和:sum_back[i] = sum_back[i+1] + a[i];
• 将最小“差异”设置为其最大值:min_diff = sum_back[0];
• 输入a[0]在 A -> 索引 i检查元素的个数设置为 1
• 设置up_down = true; :这个 bool 值表示我们当前是前进(true)还是后退(false)

While循环:

• 如果(up_down):前进

  • 在sum_back的帮助下测试过早放弃
  • 选择最可能的值，调整sum根据这个选择
  • if (i == n-1) : LEAF -> 测试最优值是否得到改进，如果新值等于 0，则返回(编辑: if (... < 2) )；向后走
  • 如果不在叶子中:继续前进

• If (!updown): 向后

  • 如果我们到达i == 0 :返回
  • 如果是该节点第二次行走:选择第二个值，向上走
  • 否则:向下
  • 在这两种情况下:重新计算新的 sum值

这是一段 C++ 代码(抱歉，我不懂 Python)

#include    <iostream>
#include    <vector>
#include    <algorithm>
#include    <tuple>

std::tuple<int, std::vector<int>> partition(std::vector<int> &a) {
    int n = a.size();
    std::vector<int> parti (n, -1);     // current partition studies
    std::vector<int> parti_opt (n, 0);  // optimal partition
    std::vector<int> sum_back (n, 0);   // sum of remaining elements
    std::vector<int> n_poss (n, 0);     // number of possibilities already examined at position i

    sum_back[n-1] = a[n-1];
    for (int i = n-2; i >= 0; --i) {
        sum_back[i] = sum_back[i+1] + a[i];
    }

    std::sort(a.begin(), a.end(), std::greater<int>());
    parti[0] = 0;       // a[0] in A always !
    int sum = a[0];     // current sum

    int i = 1;          // index of the element being examined (we force a[0] to be in A !)
    int min_diff = sum_back[0];
    bool up_down = true;

    while (true) {          // UP
        if (up_down) {
            if (std::abs(sum) > sum_back[i] + min_diff) {  //premature abandon
                i--;
                up_down = false;
                continue;
            }
            n_poss[i] = 1;
            if (sum > 0) {
                sum -= a[i];
                parti[i] = 1;
            } else {
                sum += a[i];
                parti[i] = 0;
            }

            if (i == (n-1)) {           // leaf
                if (std::abs(sum) < min_diff) {
                    min_diff = std::abs(sum);
                    parti_opt = parti;
                    if (min_diff < 2) return std::make_tuple (min_diff, parti_opt);   // EDIT: if (... < 2) instead of (... == 0)
                }
                up_down = false;
                i--;
            } else {
                i++;        
            }

        } else {            // DOWN
            if (i == 0) break;
            if (n_poss[i] == 2) {
                if (parti[i]) sum += a[i];
                else sum -= a[i];
                //parti[i] = 0;
                i--;
            } else {
                n_poss[i] = 2;
                parti[i] = 1 - parti[i];
                if (parti[i]) sum -= 2*a[i];
                else sum += 2*a[i];
                i++;
                up_down = true;
            }
        }
    }
    return std::make_tuple (min_diff, parti_opt);
}

int main () {
    std::vector<int> a = {5, 6, 2, 10, 2, 3, 4, 13, 17, 38, 42};
    int diff;
    std::vector<int> parti;
    std::tie (diff, parti) = partition (a);

    std::cout << "Difference = " << diff << "\n";

    std::cout << "set A: ";
    for (int i = 0; i < a.size(); ++i) {
        if (parti[i] == 0) std::cout << a[i] << " ";
    }
    std::cout << "\n";

    std::cout << "set B: ";
    for (int i = 0; i < a.size(); ++i) {
        if (parti[i] == 1) std::cout << a[i] << " ";
    }
    std::cout << "\n";
}