26

まず、これは宿題ではありません（私はAレベルの学生です、これは私たちが問題を解決することに近いものではありません（これははるかに難しいです））が、私が話しかけようとしている問題の多くはプログラミングロジックを改善します。

ランダムな整数の配列があるシナリオを考えました。たとえば、10個の整数です。ユーザーはカウントしたい数値を入力し、アルゴリズムはその合計を計算するために必要な数値を計算しようとします。たとえば、この整数の配列から合計44を作成したい場合は、次のようにします。

myIntegers = array(1, 5, 9, 3, 7, 12, 36, 22, 19, 63);

出力は次のようになります。

36 + 3 + 5 = 44

またはそれらの線に沿った何か。私は自分自身を明確にしたいと思います。追加のボーナスとして、必要な合計を作成するためにアルゴリズムができるだけ少ない数を選択するようにするか、指定された数で合計が作成できない場合はエラーを出します。

再帰を使用して配列を反復処理し、合計が満たされるか過ぎてしまうまで数値を何度も追加することを考えました。しかし、私が頭を悩ませることができないのは、アルゴリズムが合計を超えて、配列から選択する数値を選択する必要がある場合にどうするかです。

私は完全なコードや完全なアルゴリズムを探しているのではありません。これをどのように進めるべきかについてあなたの意見を求め、おそらくいくつかのヒントなどを共有します。私はおそらく今夜これに取り組み始めるでしょう。：P

私が言ったように、宿題ではありません。もう少し進んだことをしたいだけです。

あなたが提供することができるどんな助けにも感謝します。:)

4

10 に答える 10

31

あなたはナップザック問題を見ています

ナップザック問題またはリュックサック問題は、組み合わせ最適化の問題です。それぞれに重みと値を持つアイテムのセットが与えられた場合、コレクションに含める各アイテムの数を決定して、合計重量が指定された制限よりも小さくなるようにします。合計値はできるだけ大きくします。その名前は、固定サイズのナップザックに制約され、最も便利なアイテムでいっぱいにしなければならない人が直面する問題に由来しています.

編集：あなたの特別なケースはサブセット合計問題です

于 2010-02-23T17:15:20.743 に答える
10

サブセットの合計はうまくいきますか? ;]

于 2010-02-23T17:14:33.527 に答える
4

これは、大学レベルのアルゴリズムのコースで見られる古典的なナップサックの問題です (少なくとも私はその時見ました)。これを紙の上で解決するのが最善であり、コードでの解決策は比較的簡単に解決できるはずです。

編集: 考慮すべきことの 1 つは、動的プログラミングです。

于 2010-02-23T17:16:27.540 に答える
2

ここにショートカットはありません。他の人が言ったことに加えて、これが具体的にどのような問題であるかなどについて、出発点を提供するための実用的なアドバイスを次に示します。

配列をソートし、入力 sum を指定するとm、配列内の より小さい最初の数値を見つけ、mそれを呼び出しn(これが合計の最初の可能な数値です)、最大の可能な補数 ( m-n) から始めて、下に向かって作業します。 .

正確に一致する番号が見つからない場合は、利用可能な最高の番号を選択して と呼びo(これが 2 番目の番号です)、( ) から始まる 3 番目の番号を探して、m-n-oもう一度下に進みます。

正確に一致するものが見つからない場合は、次の番号 n (元の n の index-1 のインデックス) から始めて、同じことを行います。2 つの数値の正確な一致が見つかるまで、これを続けることができます。2 つの数値の合計に一致するものが見つからない場合は、プロセスをもう一度開始しますが、3 番目の数値を含めるように拡張します。等々。

それは再帰的に行うことができます。少なくとも、このアプローチにより、一致が見つかったときに、入力の合計を形成するセット内の可能な数が最も少ないものになることが保証されます。

ただし、最悪の場合、多くのことを経験することになる可能性があります。

編集：Venrが正しく指摘しているように、私の最初のアプローチは間違っていました。これを反映するために編集されたアプローチ。

于 2010-02-23T17:32:34.977 に答える
2

あなたの問題は部分集合問題に関連しています。最悪の場合、考えられるすべての組み合わせを試す必要があります。

于 2010-02-23T17:18:50.490 に答える
2

この問題には、非常に効率的なランダム化アルゴリズムがあります。あなたがすでに回答を受け入れていることは知っていますが、とにかく喜んで共有します。人々がまだこの質問をチェックしてくれることを願っています:)。

Let Used = list of numbers that you sum.
Let Unused = list of numbers that you DON'T sum.
Let tmpsum = 0.
Let S = desired sum you want to reach.

for ( each number x you read )
  toss a coin:
    if it's heads and tmpsum < S
      add x to Used
    else
      add x to Unused

while ( tmpsum != S )
  if tmpsum < S 
    MOVE one random number from Unused to Used
  else
    MOVE one random number from Used to Unused

print the Used list, containing the numbers you need to add to get S

これは、特にランダム入力の場合、動的計画法のソリューションよりもはるかに高速です。唯一の問題は、解決策がない場合に確実に検出できないこと (アルゴリズムを数秒間実行し、終了しない場合は解決策がないと見なすことができます) と、解決策が確実に得られるかどうかを確認できないことです。最小数の要素が選択されています。繰り返しますが、特定の停止条件が満たされるまで、アルゴリズムを継続させ、より少ない要素でソリューションを見つけようとするロジックを追加することもできますが、これにより遅くなります。ただし、機能するソリューションにのみ関心があり、多数の数値があり、目的の合計が非常に大きくなる可能性がある場合、これはおそらく DP アルゴリズムよりも優れています。

このアプローチのもう 1 つの利点は、DP ソリューションでは部分和を配列インデックスとして使用し、インデックスは自然数のみであるため、DP ソリューションには当てはまらない、修正なしの負の数と有理数でも機能することです。もちろん、たとえばハッシュテーブルを使用することもできますが、DP ソリューションはさらに遅くなります。

于 2010-02-23T19:42:00.687 に答える
1

他の人の答えを繰り返します: それは部分和の問題です。動的計画法の手法で効率的に解決できます。

次のことはまだ言及されていません: 問題は Pseudo-P (または弱い意味での NP-Complete) です。

S (S は和) と n (要素の数) におけるアルゴリズム (動的計画法に基づく) 多項式の存在は、この主張を証明します。

よろしく。

于 2010-02-23T21:50:39.997 に答える
1

このタスクが何と呼ばれているのか正確にはわかりませんが、 http://en.wikipedia.org/wiki/Knapsack_problemのようなもののようです。

于 2010-02-23T17:15:42.133 に答える
1

へー、私は「不完全な仕様」カードをプレイし (数字は 2 回しか現れないとは誰も言っていない!)、これを「変化させる」問題に減らします。数字を降順に並べ替え、目的の合計よりも小さい最初の数字を見つけて、それを合計から引きます (除算と剰余を使用すると、これが速くなる可能性があります)。sum = 0 になるまで、または合計より小さい数が見つからなくなるまで繰り返します。

完全を期すために、各合計の加数の数を追跡する必要があります。もちろん、使用する最初の数を追跡し、それをスキップして、追加の数でプロセスを繰り返すことにより、追加のシーケンスを生成する必要があります。これにより、(7 + 2 + 1) オーバー (6 + 4) の問題が解決されます。

于 2010-02-23T18:12:14.093 に答える
0

わかりました、上記の問題を解決するために C++ プログラムを書きました。アルゴリズムは単純です:-)

まず、配列を降順で並べます (配列を降順でハードコードしましたが、任意の並べ替えアルゴリズムを適用できます)。

次に、n、pos、および sum の 3 つのスタックを取りました。最初のものは可能な合計の組み合わせが見つかる数を格納し、2 つ目は検索を開始する位置から配列のインデックスを保持し、3 つ目は要素を格納し、その加算によって入力した数が得られます。

この関数は、配列内で入力された数値以下の最大数値を探します。等しい場合は、単純にその数値を合計スタックにプッシュします。そうでない場合は、見つかった配列要素を (一時的に) 合計スタックにプッシュし、検索する数と見つかった数の差を見つけてから、再帰を実行します。

例を示しましょう:- {63,36,22,19,12,9,7,5,3,1} で 44 を検索するには

最初の 36 が sum にプッシュされます (44 未満の最大の数) 44-36=8 が n にプッシュされます (次に検索する数) 7 が合計にプッシュされます 8-7=1 が n にプッシュされます 1 がプッシュされます合計でプッシュ

したがって、44=36+7+1 :-)

#include <iostream>
#include<conio.h>
using namespace std;

int found=0;
void func(int n[],int pos[],int sum[],int arr[],int &topN,int &topP,int &topS)
{
int i=pos[topP],temp;
while(i<=9)
{
    if(arr[i]<=n[topN])
    {
        pos[topP]=i;
        topS++;
        sum[topS]=arr[i];
        temp=n[topN]-arr[i];
        if(temp==0)
            {
                found=1;
                break;
        }
topN++;
        n[topN]=temp;
        temp=pos[topP]+1;
        topP++;
        pos[topP]=temp;
        break;
    }
    i++;
}
if(i==10)
{
    topP=topP-1;
    topN=topN-1;
    pos[topP]+=1;
    topS=topS-1;
    if(topP!=-1)
    func(n,pos,sum,arr,topN,topP,topS);
}
else if(found!=1)
func(n,pos,sum,arr,topN,topP,topS);
}

main()
{
int x,n[100],pos[100],sum[100],arr[10]={63,36,22,19,12,9,7,5,3,1},topN=-1,topP=-1,topS=-1;
cout<<"Enter a number: ";
cin>>x;
topN=topN+1;
n[topN]=x;
topP=topP+1;
pos[topP]=0;
func(n,pos,sum,arr,topN,topP,topS);
if(found==0)
    cout<<"Not found any combination";
else{
cout<<"\n"<<sum[0];
for(int i=1;i<=topS;i++)
    cout<<" + "<<sum[i];
}
getch();
}

コードをコピーして IDE に貼り付けることができます。正常に動作します :-)

于 2014-10-23T10:50:41.393 に答える