背包问题—暴力递归 -》记忆化搜索 -》动态规划(待补充)

public class KnapsackProblem{

    //暴力递归
    public int process(int[] w, int[] v, int index, int freeSize){
        //base case
        if (freeSize <= 0 || index == w.length){
            return 0;
        }
        int p1 = Integer.MIN_VALUE;
        if (freeSize >= w[index]){
            p1 = v[index] + process(w,v,index + 1, freeSize - w[index]);
        }
        int p2 = process(w,v,index + 1,freeSize);
        return Math.max(p1,p2);
    }
    
    //记忆化搜索
    public int process2(int[] w, int[] v, int index, int freeSize, int[][] nc){
        if (nc[index][freeSize] != -1){
            return nc[index][freeSize];
        }
        //base case
        if (freeSize <= 0 || index == w.length){
            nc[index][freeSize] = 0;
            return nc[index][freeSize];
        }
        int p1 = Integer.MIN_VALUE;
        if (freeSize >= w[index]){
            p1 = v[index] + process2(w,v,index + 1, freeSize - w[index],nc);
        }
        int p2 = process2(w,v,index + 1,freeSize,nc);
        nc[index][freeSize] = Math.max(p1,p2);
        return nc[index][freeSize];
    }
    
    //动态规划
    
    public static void main(String[] args) {
        int[] w = {2,4,6,8,4,5,6,8,7,7,3};
        int[] v = {10,50,20,100,900,5,722,145,600,100,500};
        int bag = 20;
        int[][] nc = new int[w.length + 1][bag + 1];
        for (int i = 0; i < w.length + 1; i++) {
            for (int j = 0; j < bag + 1; j++) {
                nc[i][j] = -1;
            }
        }
        final KnapsackProblem knapsackProblem = new KnapsackProblem();
        System.out.println(knapsackProblem.process(w,v,0,bag));
         System.out.println(knapsackProblem.process2(w,v,0,bag,nc));
    }
}