小编zut*_*tru的帖子

是否有一种算法可以确定具有精确重量 W 的背包？即它就像普通的 0/1 背包问题，其中 n 个物品的重量为 w_i，价值为 v_i。最大化所有物品的价值，但是背包中物品的总重量需要正好有重量 W！

我知道“正常”的 0/1 背包算法，但这也可以返回重量更轻但价值更高的背包。我想找到最高值但精确的 W 重量。

这是我的 0/1 背包实现：

public class KnapSackTest {
    public static void main(String[] args) {
        int[] w = new int[] {4, 1, 5, 8, 3, 9, 2};  //weights
        int[] v = new int[] {2, 12, 8, 9, 3, 4, 3}; //values

        int n = w.length;
        int W = 15; // W (max weight)

        int[][] DP = new int[n+1][W+1];

        for(int i = 1; i …