package com.harrison.class12;

public class Code06_Knapsack {
    // 不变参数 w[] v[] bag
    // alreadyW 0~index位置的货物已经做过决定了，现在形成的重量
    // 返回index及其往后位置货物的最大价值
    // 返回 -1 认为方案无效，
    // 返回不是-1，返回值就是真实的价值
    public static int process1(int[] w,int[] v,int index,int alreadyW,int bag) {
        if(alreadyW>bag) {// 超过了载重，方案无效
            return -1;
        }
        // 重量没吵 && 没有货物了，所以此时的最大价值就是0
        if(index==w.length) {
            return 0;
        }
        // 没有要当前货物
        int p1=process1(w, v, index+1, alreadyW, bag);
        // 要了当前的货物
        int p2next=process1(w, v, index+1, alreadyW+w[index], bag);
        int p2=-1;
        // 如果要了当前位置的货物 && 重量没有超过bag
        // 那么这种情况下的最大价值就要加上当前这个货物的价值
        if(p2next!=-1) {
            p2=p2next+v[index];
        }
        // 返回要当前货物和不要当前货物两种情况下的最大价值
        return Math.max(p1, p2);
    }
    
    public static int maxValue1(int[] w,int[] v,int bag) {
        if(w==null || v==null || w.length!=v.length || w.length==0) {
            return 0;
        }
        return process1(w, v, 0, 0, bag);
    }
    
    // rest 当前剩余的重量，其余参数跟你上面方法一样
    public static int process2(int[] w,int[] v,int index,int rest) {
        // 如果没有剩余重量了，方案无效
        if(rest<0) {
            return -1;
        }
        // 如果有剩余空间但是没有货物了
        // 那么index及其往后位置的货物的最大价值就是0
        if(index==w.length) {
            return 0;
        }
        // 不要当前位置的货物，所以rest没变
        int p1=process2(w, v, index+1, rest);
        // 要了当前位置的货物，所以剩余空间要减去当前货物的重量
        int p2next=process2(w, v, index+1, rest-w[index]);
        int p2=-1;// 要当前位置货物的话，可能会导致方案无效，也就是剩余重量可能会<0
        // 如果要了当前货物 && 还有剩余重量（方案有效）
        if(p2next!=-1) {
            p2=p2next+v[index];
        }
        // 返回要跟不要当前货物两种情况下的最大值
        return Math.max(p1, p2);
    }
    
    public static int maxValue2(int[] w,int[] v,int bag) {
        if(w==null || v==null || w.length!=v.length || w.length==0) {
            return 0;
        }
        return process2(w, v, 0, bag);
    }
    
    public static void main(String[] args) {
        int[] w = { 3, 2, 4, 7, 3, 1, 7 };
        int[] v = { 5, 6, 3, 19, 12, 4, 2 };
        int bag=15;
        System.out.println(maxValue1(w, v, bag));
        System.out.println(maxValue2(w, v, bag));
    }
}