python - 列表元素的公平划分

Question

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

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

我想知道解决这个问题的算法。请注意，我正在参加在线编程入门课程，因此将不胜感激简单的算法。

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

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)

更新：我联系了导师，被告知我应该在函数内部定义另一个“帮助”函数来检查所有不同的组合，然后我需要检查最小差异。

标签： pythonalgorithmlist

Answer 1

注意：编辑以更好地处理所有数字的总和为奇数的情况。

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

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

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

它允许实现一个简单的提前放弃过程：
在给定时间，如果sum大于所有剩余元素的总和（即未放置在 A 或 B 中）加上当前获得的最小值的绝对值，那么我们可以放弃检查当前路径，而不检查其余元素。此过程通过以下方式进行了优化：

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

这是一个伪代码

初始化：

• 排序元素a[]
• 计算剩余元素的总和：sum_back[i] = sum_back[i+1] + a[i];
• 将最小“差异”设置为其最大值：min_diff = sum_back[0];
• 放入a[0]A -> 检查元素的索引i设置为 1
• Set up_down = true;: 这个布尔值表示我们当前是前进 (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";
}