숫자를 더하거나 뺄 때 사용할 수있는 알고리즘을 찾으려면?

Question

숫자 그룹의 합/차이가 다른 숫자와 같을 수 있는지 결정하기위한 효율적인 미리 준비 알고리즘이 있는지 궁금합니다. 예 :

5, 8, 10, 또는 +를 사용하여 2 - 동일 9. 5 - 8 = -3 + 10 = + 7 = 9

이미 존재하는 알고리즘이 있다면 2 어떤 그것은 부름이다. 그렇지 않은 경우 효율적이지 않을 수도 있지만 프로그래밍하는 방법을 알아낼 수 있습니다.

감사합니다.

Answer 1

그래, 이것은 기본적으로 배낭 문제이지만 동적 프로그래밍을 사용하여 의사 다항식 시간으로 계산할 수 있습니다.

나는 당신이 그것을 구현하려는 경우 몇 달 전에, 그래서 어쩌면이 자바 코드는, 당신을 도울 수있는 한 :

public void solve() { 
    while (this.isEnd() == false) { 
     int priceSum = this.getItemsInstance().getTotalPrice()/divide; 
     int numOfItems = this.getItemsInstance().itemCount(); 
     int maxWeight = this.getItemsInstance().getMaxWeight(); 

     int[][] array = new int[numOfItems + 1][priceSum + 1]; 
     boolean[][] arrayCounted = new boolean[numOfItems + 1][priceSum + 1]; 

     for (int i = 0; i < numOfItems + 1; i++) { 
      array[i][0] = 0; 
      arrayCounted[i][0] = true; 
     } 

     int max = 0; 
     int price = 0; 
     for (int j = 1; j < priceSum + 1; j++) { 
      for (int i = 1; i < numOfItems + 1; i++) { 
       int temp = W(i, j, array, arrayCounted); 
       if (temp <= maxWeight) { 
        max = temp; 
        price = j; 
       } 
      } 
     } 
    } 
} 

private int W(int i, int c, int[][] array, boolean[][] arrayCounted) { 
    if (c < 0) { 
     return MAX_PRICE/divide; 
    } 
    if (i == 0) { 
     if (c == 0) { 
      return 0; 
     } else { 
      return MAX_PRICE/divide; 
     } 
    } 

    if (arrayCounted[i][c]) { 
     return array[i][c]; 
    } 

    arrayCounted[i][c] = true; 
    array[i][c] = Math.min(W(i - 1, c, array, arrayCounted), W(i - 1, c - this.items[i - 1].price/divide, array, arrayCounted) + this.items[i - 1].weight); 
    return array[i][c]; 
}