添加/减去数字以查找是否可以生成数字的算法？

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