能够将四位数字分成两组，使得它们的和之差尽可能接近的算法

Question

我有一份 C++ 作业，需要我输入 4 个自然数，并将它们配对，使它们的和之间的差异尽可能地小。

例如：

I have entered 4 numbers: 4; 3; 2; 1;
The smallest between the numbers would be 0 --> 4 + 1 and 3 + 2

我已经写了一些使用if语句的代码，但检查每种组合需要编写大量的代码，所以我想知道是否有更短的方法来完成这个任务。

#include <iostream>
using namespace std;

int main()
{
    int a, b, c, d;
    int x, y, z;

    cout << "Insert 1st number" << endl;
    cin >> a;
    cout << "Insert 2nd number" << endl;
    cin >> b;
    cout << "Insert 3rd number" << endl;
    cin >> c;
    cout << "Insert 4th number" << endl;
    cin >> d;

    if ((a > b) && (b > c) && (c > d))
    {
        x = a + d;
        y = b + c;
        z = x - y;

        cout << "The smallest differnce is: " << z << endl;
        cout << endl;
    }
    else if ((a > b) && (b > c) && (c < d))
    {
        x = a + c;
        y = b + d;
        z = x - y;
        cout << "The smallest differnce is: " << z << endl;
        cout << endl;
    }
    else if ((a > b) && (b < c) && (c > d))
    {
        x = a + b;
        y = d + c;
        z = x - y;
        cout << "The smallest differnce is: " << z << endl;
        cout << endl;
    }
}

- kdzy

---

你的代码是什么样子的？另外，0 是从哪里来的？ - PhoenixBlue

https://en.wikipedia.org/wiki/Knapsack_problem#Solving - user2956272

@PhoenixBlue 我添加了代码。它还不完整，但我希望你能理解。0来自于将这4个数字成对相加：4+1=5和3+2=5，它们的差为0。 - kdzy

Answer 1

如果只涉及4个自然数，按照以下步骤处理：

• 首先，创建一个普通数组（例如int [4]或std::array<int, 4>），并将用户输入存入其中。
• 升序或降序排列数组。
• （1st + 4th）元素与（2nd + 3rd）元素的差值即为结果。

以下是示例代码：

#include <iostream>
#include <array>     // std::array
#include <algorithm> // std::sort

int main()
{
    std::array<int, 4> arr;
    for (int& element : arr) std::cin >> element;
    std::sort(arr.begin(), arr.end());
    int result = (arr[0] + arr[3]) - (arr[1] + arr[2]);
    std::cout << "The smallest difference is: " << result << "\n";
}

(点击查看在线演示)

- JeJo

---

为什么那是答案？ - David G

@0x499602D2 我认为这是不言自明的。嗯... 老实说，除了根据上面提供的示例来解释之外，我不知道该如何解释。我发现对于一个有4个数字的数组来说，这种情况是正确的。 - JeJo

是的，我也发现这是答案，但我不知道如何证明它。 - David G

有6种情况，只需证明其中5种不是最优的即可。 - Neil

但是如何证明这总是正确的答案？ @NeilEdelman - David G

Answer 2

为了证明排序后的版本|(a + d) - (b + c)|总是成立的，其中a ≤ b ≤ c ≤ d，我们需要做以下步骤：(1) 显然c和d永远不会配对，因为这会使一边的总和最大化，另一边的总和最小化，导致可能的差异最大化。既然我们知道c在一侧，d在另一侧，显然我们想要添加到更大的一侧（相同或）比我们添加到较小的一侧少。

- גלעד ברקן