0

これが問題です。

足し算と引き算のみを使用して、与えられた数の合計として、与えられた数 N を書きます。

次に例を示します。

N = 20
Integers = 8, 15, 2, 9, 10

20 = 8 + 15 - 2 + 9 - 10。

これが私の考えです。

最初のアイデアは、プラスとマイナスを交互に、ブルート フォースを使用することでした。最初に、組み合わせの数とその 2^k (k は整数の数) を計算します。これは、マイナスとプラスしか交互に使用できないためです。次に、1 から 2^k までのすべての数値を実行し、それをバイナリ形式に変換します。そして、任意の 1 にはプラスを使用し、任意の 0 にはマイナスを使用します。例を使用すると簡単になります (上記の例を使用)。

The number of combinations is: 2^k = 2^5 = 32.
Now I run through all numbers from 1 to 32. 
So i get: 1=00001, that means: -8-15-2-9+10 = -24 This is false so I go on.
2 = 00010, which means: -8-15-2+9-10 = -26. Also false.

この方法はうまく機能しますが、整数の数が多すぎると時間がかかりすぎます。

C ++での私のコードは次のとおりです。

#include <iostream>
#include <cmath>
using namespace std;
int convertToBinary(int number) {
    int remainder;
    int binNumber = 0;
    int i = 1;
    while(number!=0)
    {
        remainder=number%2;
        binNumber=binNumber + (i*remainder);
        number=number/2;
        i=i*10;
    }
    return binNumber;
}
int main()
{
    int N, numberOfIntegers, Combinations, Binary, Remainder, Sum;
    cin >> N >> numberOfIntegers;
    int Integers[numberOfIntegers];
    for(int i = 0; i<numberOfIntegers; i++)
    {
        cin >>Integers[i];
    }
    Combinations = pow(2.00, numberOfIntegers);
    for(int i = Combinations-1; i>=Combinations/2; i--) // I use half of the combinations, because 10100 will compute the same sum as 01011, but in with opposite sign.
    {
        Sum = 0;
        Binary = convertToBinary(i);
        for(int j = 0; Binary!=0; j++)
        {
            Remainder = Binary%10;
            Binary = Binary/10;
            if(Remainder==1)
            {
                Sum += Integers[numberOfIntegers-1-j];
            }
            else
            {
                Sum -= Integers[numberOfIntegers-1-j];
            }
        }
        if(N == abs(Sum))
        {
            Binary = convertToBinary(i);
            for(int j = 0; Binary!=0; j++)
            {
                Remainder = Binary%10;
                Binary = Binary/10;
                if(Sum>0)
                {
                    if(Remainder==1)
                    {
                        cout << "+" << Integers[numberOfIntegers-1-j];
                    }
                    else
                    {
                        cout << "-" << Integers[numberOfIntegers-1-j];
                    }
                }
                else
                {
                    if(Remainder==1)
                    {
                        cout << "-" << Integers[numberOfIntegers-1-j];
                    }
                    else
                    {
                        cout << "+" << Integers[numberOfIntegers-1-j];
                    }
                }
            }
            break;
        }
    }
    return 0;
}
4

3 に答える 3

0

これは典型的な宿題なので、完全な答えを出すつもりはありません。しかし、これを考慮してください：

K = +a[1] - a[2] - a[3] + a[4]

として書き換えることができます

a[0] = K
a[0] + a[2] + a[3] = a[1] + a[4]

これで、両側に通常のサブセットの合計ができました。

于 2013-03-28T12:33:51.810 に答える
0

これは、あなたが提供した静的入力を受け取り、コアJavaを使用して記述しました

  public static void main(String[] args) {

    System.out.println("Enter number");

    Scanner sc = new Scanner(System.in);

    int total = 0;

    while (sc.hasNext()) {


        int[] array = new int[5] ;

        for(int m=0;m<array.length;m++){
            array[m] = sc.nextInt();
        }

         int res =array[0];
            for(int i=0;i<array.length-1;i++){

                    if((array[i]%2)==1){
                            res = res - array[i+1];
                    }
                    else{
                    res =res+array[i+1];
                    }
            }
            System.out.println(res);
    }
}
于 2013-05-09T05:38:03.310 に答える
0

あなたが心配しているのはあなたの複雑さです。

どのような最適化を行うことができるかを分析してみましょう。

a[n] に n 個の数値が指定され、ターゲット値 T;

そして、加算と減算の 1 つの組み合わせで T が得られることは確かです。

したがって、Sigma(m*a[k]) =T ここで、( m =(-1 または 1) および 0 >= k >= n-1 )

これは単に..

次のように書くことができます

(配列内のいくつかの数値の合計) = (配列内の残りの数値の合計) + T

あなたの場合のように..

8+15-2+9-10=20 は次のように書けます

8+15+9= 20+10+2

したがって、ターゲットを含むすべての数値の合計 = 64 // それを計算できます .. :)

したがって、半分は 32 です。

さらに 20+(何か)=32 と書くと、この場合は 12 (2+10) になります。

あなたの問題は、この場合、合計が 12 である配列内の数字を見つけることに減らすことができます

したがって、合計が k である数値の組み合わせを見つけることで、問題を減らすことができます (上記のように計算できます k=12 。) 複雑さは O(log (n )) n 配列のサイズとして、 O（log（n））を取得するには、配列をソートし、バイナリ検索ベースのアルゴリズムを使用する必要があることに注意してください。

したがって、並べ替えが含まれているため、複雑さを O(2^n) から O((N+1)logN) にすることができます。

于 2013-03-28T20:16:15.787 に答える