java - dp 的背包问题让我的答案错误

Question

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [] val = new int[n];
        int [] weight = new int[n];
        for(int i =0;i<n;i++){
            val[i] = sc.nextInt();
        }
        
         for(int i =0;i<n;i++){
            weight[i] = sc.nextInt();
        }
        
        int cap = sc.nextInt();
        int [][]dp = new int[n+1][cap+1];
        System.out.println(getMaxVal(val, weight, cap, 0, 0, dp));
      
        
    }
    
    public static int getMaxVal(int []val, int []wt, int cap, int index, int valStored, int [][]dp){
        
        if(cap == 0 || index >= val.length){
            return valStored;
        } 
        if(dp[index][cap] != 0) {
            return dp[index][cap];
        }
        
        int n = val.length;
        int withCurrentItem = 0;
        int inittalMaxValue = 0;
        if(cap - wt[index] >=0){
            withCurrentItem = getMaxVal(val, wt, cap - wt[index], index+1, valStored+val[index], dp);
        }
        int withoutCurrentItem = getMaxVal(val, wt, cap, index+1, valStored, dp);
      

        dp[index][cap] = Math.max(withoutCurrentItem, withCurrentItem);
        
        return  Math.max(withoutCurrentItem, withCurrentItem);
        
        
        
        
        
        
    }
}

在这个 0 / 1 背包问题中，如果我在没有 dp 的情况下使用相同的代码，那么它可以完美运行，并且我的所有测试用例都通过了。但如果我喜欢这种方式，我的一些测试用例就会失败。我在这里做错了什么，请帮助我。

标签： javaalgorithmdata-structuresknapsack-problem

Answer 1

的想法Dynamic Programming如下：你有一个接受一些参数的函数，但它的输出只取决于特定的参数（如果这些参数相同，则输出总是相同的）所以我们不会多次计算答案因为这些参数是相同的，我们知道输出。

您的动态规划的问题是您假设 的输出getMaxVal仅取决于capand index，但实际上它也取决于valStored。但是您检查cap并index假设输出相同，这是错误的。

一种可能的解决方案是您可以扩展您的备忘录并包括在内valStored，但这会增加复杂性。

另一种可能的解决方案（我推荐）是您可以更改函数，使其不依赖于valStored.

以后如何发现此类错误

我如何解决您的问题如下：我实现了两个函数withDP，withoutDP创建了随机输入并一遍又一遍地测试了这两个，并比较了它们的输出。当出现问题时，我打印了输入并继续进一步调查。我这样说是因为您始终可以按照这些步骤尝试自己调试代码。

这是代码（请注意，一些输入，cap和index是相同的，但输出是不同的）

import java.util.*;

public class Main {

    static ArrayList<String> parameters;

    public static void main(String[] args) {

        parameters = new ArrayList<>();
        Random r = new Random(0);
        int[] val;
        int[] weight;
        int n;
        int[][] dp;

        for (int counter = 0; counter < 1000; counter++) {
            System.out.println("Test Case: " + counter);
            parameters.clear();
            n = r.nextInt(5) + 5;
            val = new int[n];
            weight = new int[n];
            for (int i = 0; i < n; i++) {
                val[i] = r.nextInt(9) + 1;
            }

            for (int i = 0; i < n; i++) {
                weight[i] = r.nextInt(9) + 1;
            }

            int cap = r.nextInt(90) + 10;
            dp = new int[n + 1][cap + 1];
            int withDP = getMaxValDP(val, weight, cap, 0, 0, dp);
            int withoutDP = getMaxVal(val, weight, cap, 0, 0);
            if (withDP != withoutDP) {
                System.out.println("With DP: " + withDP);
                System.out.println("Without DP: " + withoutDP);
                System.out.println("input:");
                System.out.println("n = " + n);
                System.out.println("cap = " + cap);

                System.out.print("val:    ");
                for (int i: val) {
                    System.out.print(i + ", ");
                }
                System.out.println();

                System.out.print("weight: ");
                for (int i: weight) {
                    System.out.print(i + ", ");
                }
                System.out.println();

                Collections.sort(parameters);
                for (String s: parameters){
                    System.out.println(s);
                }

                break;
            }
        }

    }

    public static int getMaxVal(int []val, int []wt, int cap, int index, int valStored){

        if(cap == 0 || index >= val.length){
            parameters.add("cap:  " + cap + ",\tindex: " + index + ",\tvalStored: " + valStored + ",\treturn value: " + valStored);
            return valStored;
        }

        int withCurrentItem = 0;
        if(cap - wt[index] >=0){
            withCurrentItem = getMaxVal(val, wt, cap - wt[index], index+1, valStored+val[index]);
        }
        int withoutCurrentItem = getMaxVal(val, wt, cap, index+1, valStored);

        parameters.add("cap:  " + cap + ",\tindex: " + index + ",\tvalStored: " + valStored + ",\treturn value: " + Math.max(withoutCurrentItem, withCurrentItem));
        return Math.max(withoutCurrentItem, withCurrentItem);

    }

    public static int getMaxValDP(int []val, int []wt, int cap, int index, int valStored, int [][]dp){

        if(cap == 0 || index >= val.length){
            return valStored;
        }
        if(dp[index][cap] != 0) {
            return dp[index][cap];
        }

        int withCurrentItem = 0;
        if(cap - wt[index] >=0){
            withCurrentItem = getMaxValDP(val, wt, cap - wt[index], index+1, valStored+val[index], dp);
        }
        int withoutCurrentItem = getMaxValDP(val, wt, cap, index+1, valStored, dp);

        dp[index][cap] = Math.max(withoutCurrentItem, withCurrentItem);

        return  Math.max(withoutCurrentItem, withCurrentItem);

    }
}