0-1背包问题

    /**
     * 0-1背包问题
     * @param w w[index] 当前货物的总重量
     * @param v v[index] 当前货物的总价值
     * @param index 当前的货物号
     * @param alreadyW 0--index 已做出决定,所形成的目前重量
     * @param bag 可装的总重量
     * @return 返回最大价值
     */

    public static int process(int[] w,int[] v,int index,int alreadyW,int bag){
       //base case 背高超重了,不能再放物品了
        if(alreadyW>bag){
            return -1;
        }
        //没有物品了
        if(index==w.length){
            return 0;
        }
        //当前物品不放所获得的最大价值
        int p1=process(w,v,index+1,alreadyW,bag);
        //当前物品放入背包所获得的最大价值
        int p2=process(w,v,index+1,alreadyW+w[index],bag);
        int pNext=-1;
        if(p2!=-1){
            pNext=v[index]+p2;
        }
        return Math.max(p1,pNext);
    }

  

  /**
     * 0-1背包问题
     * @param w 当前货物的总重量
     * @param v  当前货物的总价值
     * @param index 当前的货物号
     * @param rest 剩余可装入的重量
     * @return 返回最大价值
     */

    public static int process(int[] w,int[] v,int index,int rest) {
        //没有容量了
        if (rest == 0) {
            return 0;
        }
        //没有物品了
        if (index == w.length) {
            return 0;
        }
        int p1 = process(w, v, index + 1, rest);
        int p2 = 0;
        //放入当前物品的话,要判段容量是否够
        if (rest >= w[index]) {
            p2 = v[index] + process(w, v, index + 1, rest - w[index]);
        }

        return Math.max(p1, p2);
    }

  

上一篇:ES6学习---rest参数获取实参 / (...args)


下一篇:(三)、Rest微服务支付模块构建