2

ここでの私の目標は、特定の合計になるすべての可能な組み合わせを見つけることです。たとえば、配列が 2 59 3 43 5 9 8 62 10 4 で、合計が 12 の場合、可能な組み合わせは次のとおりです。

2 10
3 9
8 4
5 3 4

これが私が書いた最初のコードセットです。これでできる最善の改善を考えています。

   int find_numbers_matching_sum(int *number_coll, int total)
{

    int *search_till = lower_bound(number_coll,number_coll+TOTAL_SIZE, total);
    int location = search_till - number_coll;
    if (*search_till > total && location > 0 )
    {
        --location;
    }

    while ( location >= 0 )
    {
        find_totals(number_coll,total,location);
        --location;
    }
    return 1;
}

int find_totals(int *number_coll, int total, int end_location)
{
    int left_ones = total - number_coll[end_location];
    int curloc = end_location;
    int *search_till = 0;
    int location ;
    int all_numbers[10];
    int i = 0;

    all_numbers[i] = number_coll[end_location];
    while ( left_ones && curloc >= 0 )
    {
        search_till = lower_bound(number_coll,number_coll+end_location, left_ones);
        location = search_till - number_coll;
        if (*search_till > left_ones && location > 0 )
        {
            --location;
        }
        else if ( left_ones < *search_till )
        {
            break;
        }
        curloc=location;
        left_ones = left_ones - number_coll[curloc];
        all_numbers[++i] = number_coll[curloc];
        end_location = curloc - 1;
    }

    if ( !left_ones )
    {
        while ( i>=0)
        {
            cout << all_numbers[i--] << ' ';
        }
    }
    cout << endl;
    return 1;


}
4

6 に答える 6

6

あなたが説明する問題は、 NP-completeであるサブセット合計問題としても知られています。あなたが達成できる最善の方法は、配列/セットのすべての可能なサブセットを試す指数時間アルゴリズムです。

于 2010-07-21T19:07:50.740 に答える
5

これは部分和問題 ( NP-Complete ) であり、 P ?= NP までは指数関数的な解しかありません。

からxkcd

于 2010-07-21T19:12:57.377 に答える
3 
#include <iostream>
#include <vector>

using namespace std;

struct State {
    int v;
    const State *rest;
    void dump() const {
        if(rest) {
            cout << ' ' << v;
            rest->dump();
        } else {
            cout << endl;
        }
    }
    State() : v(0), rest(0) {}
    State(int _v, const State &_rest) : v(_v), rest(&_rest) {}
};

void ss(int *ip, int *end, int target, const State &state) {
    if(target < 0) return; // assuming we don't allow any negatives
    if(ip==end && target==0) {
        state.dump();
        return;
    }
    if(ip==end)
        return;
    { // without the first one
        ss(ip+1, end, target, state);
    }
    { // with the first one
        int first = *ip;
        ss(ip+1, end, target-first, State(first, state));
    }
}

int main() {
    int a[] = { 2,59,3,43,5,9,8,62,10,4 };
    int * start = &a[0];
    int * end = start + sizeof(a) / sizeof(a[0]);
    ss(start, end, 12, State());
}
于 2010-07-21T21:13:46.067 に答える
3

これは、NP 完全 ナップザック問題(部分和問題) のバリエーションです。本格的なナップザック問題は、N を連続的に下げることによって、問題に直線的に還元できます。P != NP が成立する場合、N で指数関数的に実行されるよりも高速に実行される問題の正確なアルゴリズムは見つかりません。

ただし、多項式時間近似は知られています。

于 2010-07-21T19:06:31.413 に答える
3

値が大きくない場合、たとえば合計が M で制限されている場合、動的計画法を使用できます。N個のアイテムがあるとします。

行列があると想像してくださいDP[M][N]。セルのDP[m][n]意味: 最初の n 個の要素の組み合わせのうち、m を正確に合計するものはいくつあるか?

各項目を分析すると、いくつかの組み合わせに含める場合と含めない場合があります。次に、再発を取得します（範囲外の値を処理します）

DP[m][n] = DP[m][n-1] + DP[m - v[n]][n - 1]

rhs の最初の項は、n 番目の項目を使用しないすべての合計を考慮していることを意味し、2 番目の項は n 番目の項目を使用するすべての合計を考慮していることを意味します。空集合は合計が 0 になる有効な組み合わせであるため、 base から始めますDP[0][0] = 1。目的の値は DP[M][N] にあります。

これは疑似多項式ですが、O(MN).

于 2010-07-21T19:23:33.933 に答える
1

これは数論の分割に関係しており、動的計画法を使用して解決できます。

合計nとします。を要素partsのリストとします。それらは正の整数であると仮定します。

if parts == []
then f(n,parts) = [] 
else let parts = x::queue and f(n,parts) = union(L1, L2)

where:

L1 = f(n, queue)

if n-x>0
then let result = f(n-x, queue) and L2 = concatenation([x], result)
else if n-x==0, L2 = [x]
else L2 = []

これは典型的な宿題です。

于 2010-07-21T19:28:34.263 に答える