algorithm - n 要素間の最小差

Question

私はC++でプロジェクトに取り組んでいます。とのn要素がintありKます。

min{a1+a2+....+an} - K <= ε >= 0ε = 最小数でを取得する方法を見つける必要があります。

数字の組み合わせは、{a1+a2+a6}または単に{a2}またはのみ{a2+an}にすることができます。つまり、検索 (nk) の組み合わせとは異なります。

私は小さな n (n < 15) に取り組んでいるので、複雑さは問題になりません。

Answer 1

問題の多項式解を見つけたとします。つまり、合計が に最も近い数のサブセットを見つけることができますK。

次のアルゴリズムを想像してください。

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

このアルゴリズムは何ですか？部分和問題の多項式解！

P=NP である可能性は非常に低いため、スケーラブルなソリューションが見つかる可能性はほとんどありません。

言い換えれば、あなたは力ずくで立ち往生しています。

Answer 2

このための擬似コードを作成します。

値のリストを使用して、並べ替え可能なマップを作成できます。そして、マップにa1..n要素の1つの値とその値を配置します。<mapとしてsetcompareメソッドを挿入すると、次のようになります。

[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;
}