java - 0-1 背包实现产生错误答案

Question

我已经添加了我对背包问题的递归和 DP 的实现。我找不到其中的错误。请帮忙。

import java.util.Scanner;


public class Knapsac {

    static int[][] dp;

    static int knapsack(int[] size,int[] value, int i, int weight){
        if(i <= 0)
            return 0;
        if(weight < 0)
            return Integer.MIN_VALUE;
        if(dp[weight][i] != -1)
            return dp[weight][i];

        dp[weight][i] = Math.max(knapsack(size, value, i-1, weight - size[i]) + value[i], knapsack(size, value, i-1, weight));
        return dp[weight][i];
    }

    static int knapsackWithoutDP(int[] size, int[] value, int i, int weight){
        if(i <= 0)
            return 0;
        if(weight < 0)
            return Integer.MIN_VALUE;
        return Math.max(knapsackWithoutDP(size, value, i-1, weight - size[i]) + value[i], knapsackWithoutDP(size, value, i-1, weight));
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int W, n;
        Scanner in = new Scanner(System.in);
        W = in.nextInt(); n = in.nextInt();
        dp = new int[W+1][n];

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


        int[] size = new int[n], value = new int[n];
        for(int i = 0; i < n; i++){
            size[i] = in.nextInt();
            value[i] = in.nextInt();
        }

        System.out.println(knapsackWithoutDP(size, value, size.length-1,  W));
        System.out.println(knapsack(size, value, size.length-1,  W));
    }

}

我正在处理测试用例

4 5
1 8
2 4
3 0
2 5
2 3

我应该得到 13 分，但我得到了 12 分。

谁能帮助我理解我实现过程中的错误？

Answer 1

问题似乎是您无法选择子集的第一个元素:

if(i <= 0)
     return 0;

但这意味着如果要包含或排除索引为0 的项，则无法到达您选择的位置，这是您可以选择的第一个元素。 (value[0],weight[0] 是添加到背包中的有效选择)

快速修复是简单地将此停止子句更改为

if(i < 0) //strictly smaller than
     return 0;