주어진 정수의 합으로 숫자 쓰기

Question

여기에 문제가 있습니다.

주어진 숫자 N을 덧셈과 뺄셈을 사용하여 합계로 씁니다. 여기

은 예입니다 :

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

(20) = 8 + 15 - 2 + 9 - 10

여기

내 생각;

첫 번째 아이디어는 +와 -를 번갈아 가며 사용하는 것이 었습니다. 먼저 마이너스 (+)와 플러스 (+)를 번갈아 사용할 수 있기 때문에 조합의 수와 그 2^k (k는 정수 중 nubmer)를 계산합니다. 그런 다음 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. 

이 방법은 정상적으로 작동하지만 정수 값이 너무 클 경우 시간이 오래 걸립니다. 이 전형적인 숙제이기 때문에, 나는 완전한 대답을하지 않을거야

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

Answer 1

:

여기 ++ C에 내 코드입니다. 그러나이 생각 : 이제 양측의 정상 부분 집합의 합계가

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

로

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

를 다시 작성할 수 있습니다.

Answer 2

그래서 당신이 걱정하는 것은 당신이 복잡하다는 것입니다.

어떤 최적화가 수행되는지 분석합니다.

[n]과 목표 값 T에 n 개의 숫자가 주어지면;

그리고 덧셈과 뺄셈의 한 조합으로 T가 주어집니다.

그래서 시그마 (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를 포함한 모든 숫자의 합계 // 우리는 그 ..:)

그래서 그 반 더 20+ (뭔가해야만)로 기록하는 경우이 경우에는 12 (10 + 2) 32 = 32

로

이다.

귀하의 문제는 누구의 합이 12이 경우 배열의 숫자를 찾기로 줄일 수있다

그래서 문제는 이제 누구의 합이로 계산할 수 K (인 숫자의 조합을 찾기로 줄일 수있다 배열의 크기로 O (log (n)) n을 복잡하게하는 경우 배열을 정렬하고 O (log (n))를 얻기 위해 algo를 기반으로하는 이진 탐색을 사용해야한다는 것을 명심하십시오.

따라서 정렬이 포함되어 있으므로 O (2^n)에서 O ((N + 1) logN)까지 복잡성이 발생할 수 있습니다.

Answer 3

이것은 당신이 제공 한 정적 입력을 받아, 나는 내가 전에이 문제를 여러 번 본 기억이 있기 때문에

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