algorithm - n 个元素之间的最小差异

Question

我正在使用 C++ 开发一个项目。我有和 的n元素。intK

我需要找到一种方法来获得min{a1+a2+....+an} - K <= ε >= 0ε = 最小数字。

数字的组合可以是{a1+a2+a6}or just {a2}or {a2+an}，我的意思是它不像 find (nk) 组合。

我正在研究一个小的 n (n < 15)，所以复杂性不是问题。

Answer 1

Imagine you find a polynomial solution to your problem, i.e., you can find a subset of numbers whose sum is closest to K.

Now imagine this algorithm:

- Find the subset of numbers with sum closest to K
- If (sum(subset) - K == 0)
-     return subset
- Else
-     return DOESNT_EXIST

What is this algorithm? A polynomial solution to the subset-sum problem!

Since it's very unlikely that P=NP, then it's very unlikely that you're ever going to find any scalable solution.

In other words, you're stuck with brute force.

Answer 2

我将为此编写伪代码：

您可以使用值列表创建一个可排序的映射。并将 a1..n 元素的一个值及其值放入映射中。并且在插入 set compare 方法时 < map 看起来像：

[n] [value]

该列表将是 ASC

并且要获得最小的数字，您将从头开始遍历列表并执行 + 操作，直到 mapelement[0] + mapelement[1] > e + K

并且您将拥有地图的第一个元素的列表，以及它们的 n 值

Answer 3

您可以将位掩码用于蛮力方法。像这样：

#include <iostream>
using namespace std;

int main()
{
    int n = 15;
    int a[] = {8, 6, 14, 3, 4, 11, 100, 24, 41, 56, 18, 22, 11, 39, 91};
    int k = 16;
    int best_sum = -1;
    int best_i = -1;
    for(int i = 0; i < (1 << n); i++) {
        int sum = 0;
        for(int j = 0; j < n; j++) {
            if((i >> j) & 1) {
                sum += a[j];
            }
        }
        if(sum >= k && (best_sum == -1 || sum < best_sum)) {
            best_sum = sum;
            best_i = i;
        }
    }
    cout << best_sum << " ->";
    for(int j = 0; j < n; j++) {
        if((best_i >> j) & 1) {
            cout << " " << a[j];
        }
    }
    cout << endl;
    return 0;
}