背包但物品数量均匀

Question

因此，它基本上与 0/1 背包问题相同：n 件物品，每件物品的重量 w_i 和价值 v_i，最大化所有物品的价值，但保持总重量小于 W。但是，它们略有不同：背包中的物品数量需要均匀。结果应该是背包中所有物品的总价值。

我尝试了以下方法：我使用两个大小为 (n+1) x (W+1)、DP_odd 和 DP_even 的 DP 表。我是按照：

填写的

DP_even[i][j] = max( DP_even[i-1][j] || DP_odd[i-1][j - weights[i]] + values[i] )
DP_odd[i][j] = max( DP_odd[i-1][j] || DP_even[i-1][j - weights[i]] + values[i] )

结果（总值）应该在 DP_even[n][W] 中。但是，结果不正确。我刚得到两个相等的 DP 表。

实现如下：

public class KnapSackEven {
public static void main(String[] args) {
    int[] weights = new int[] {4, 3, 3, 5, 1, 2, 7, 12};
    int[] values = new int[] {2, 1, 3, 15, 3, 5, 9, 4}};

    int n = weights.length;
    int W = 10;

    int[][] DP_odd = new int[n+1][W+1];
    int[][] DP_even = new int[n+1][W+1];

    for(int i = 0; i < n+1; i++) {
        for(int j = 0; j < W+1; j++) {
            if(i == 0 || j == 0) {
                DP_odd[i][j] = 0;
                DP_even[i][j] = 0;
            } else if(j - weights[i-1] >= 0) {
                DP_even[i][j] = Math.max(DP_even[i-1][j], DP_odd[i-1][j - weights[i-1]] + values[i-1]);
                DP_odd[i][j] = Math.max(DP_odd[i-1][j], DP_even[i-1][j - weights[i-1]] + values[i-1]);
            } else {
                DP_even[i][j] = DP_even[i-1][j];
                DP_odd[i][j] = DP_odd[i-1][j];
            }
        }
    }

    System.out.println("Result: " + DP_even[n][W]);

}

}

Result: 23

但是，结果应该是20。因为总值23不可能由偶数项组成。它占用了 weigths[2]、weights[3] 和 weights[5] 项，但这不是一个偶数...它应该占用 weights[3] 和 weights[5]。

各位想看的，这里是DP表：（第一列是values[i]，第二列是weights[i]:

DP_even:
0   0   0   0   0   0   0   0   0   0   0   0   0
2   4   0   0   0   0   2   2   2   2   2   2   2   
1   3   0   0   0   1   2   2   2   3   3   3   3   
3   3   0   0   0   3   3   3   4   5   5   5   6   
15  5   0   0   0   3   3   15  15  15  18  18  18  
3   1   0   3   3   3   6   15  18  18  18  21  21  
5   2   0   3   5   8   8   15  18  20  23  23  23  
9   7   0   3   5   8   8   15  18  20  23  23  23  
4   12  0   3   5   8   8   15  18  20  23  23  23  

DP_odd:
0   0   0   0   0   0   0   0   0   0   0   0   0
2   4   0   0   0   0   2   2   2   2   2   2   2   
1   3   0   0   0   1   2   2   2   3   3   3   3   
3   3   0   0   0   3   3   3   4   5   5   5   6   
15  5   0   0   0   3   3   15  15  15  18  18  18  
3   1   0   3   3   3   6   15  18  18  18  21  21  
5   2   0   3   5   8   8   15  18  20  23  23  23  
9   7   0   3   5   8   8   15  18  20  23  23  23  
4   12  0   3   5   8   8   15  18  20  23  23  23

回溯给出解决方案：weights[2]、weights[3] 和 weights[5] => 总值 23。

尽管该方法看起来可行，但仍然行不通。

还有其他方法可以解决这个问题吗？

Answer 1

15加5可以得到20的值，所以结果应该是20。

DP_odd[i][j] = 0 不对，因为 0 项不是奇数。现在的方式与DP_even对称，所以结果是一样的。

相反，将 DP_odd[0][0] 设置为负数并检查其他总和中的这些负数，不允许使用它们。

所以像这样：

public class KnapSackEven {
    public static void main(String[] args) {
        int[] weights = new int[] {4, 3, 3, 5, 1, 2, 7, 12};
        int[] values =  new int[] {2, 1, 3, 15, 3, 5, 9, 4};

        int n = weights.length;
        int W = 10;

        int[][] DP_odd = new int[n+1][W+1];
        int[][] DP_even = new int[n+1][W+1];

        for(int i = 0; i < n+1; i++) {
            for(int j = 0; j < W+1; j++) {
                DP_even[i][j] = -1;
                DP_odd[i][j] = -1;

                if(i == 0 || j == 0) {
                    DP_odd[i][j] = -1;
                    DP_even[i][j] = 0;
                } else if(j - weights[i-1] >= 0) {
                    if(DP_odd[i-1][j - weights[i-1]] >= 0) {
                        DP_even[i][j] = Math.max(DP_even[i-1][j], DP_odd[i-1][j - weights[i-1]] + values[i-1]);
                    }
                    if(DP_even[i-1][j - weights[i-1]] >= 0) {
                        DP_odd[i][j] = Math.max(DP_odd[i-1][j], DP_even[i-1][j - weights[i-1]] + values[i-1]);
                    }
                }

                if(i > 0) {
                    DP_odd[i][j] = Math.max(DP_odd[i][j], DP_odd[i-1][j]);
                    DP_even[i][j] = Math.max(DP_even[i][j], DP_even[i-1][j]);
                }
            }
        }

        System.out.println("Result: " + DP_even[n][W]);
    }
}

背包但物品数量均匀

Knapsack but even amount of items

java

algorithm

knapsack-problem

dynamic-programming