添加/減去數字以查找是否可以創建數字的算法？

Question

我想知道是否有一個有效的預製算法來確定一組數字的和/差是否可以等於不同的數字。例如：

5，8，10，2，使用+或 - ，等於9 5 - 8 = -3 + 10 = 7 + 2 = 9

如果存在預先存在的算法，什麼它被稱爲。如果沒有，我可以弄清楚如何編程它，但它可能不是有效的。

謝謝！

Answer 1

是的，這基本上是揹包問題，但它可以使用動態規劃在假多項式時間內計算。

我做了一個月幾前，所以也許這java代碼可以幫助你，如果你想實現它：

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