【刷题篇】背包问题

• 一、题目
• 二、题解
• • 2.1方法一：递归
  • 2.2 方法二：动态规划

int[] w 代表每个物品的重量 int[] v 代表每个物品的价值，和w数组中的物品一一对应

bag 是背包的最大容量

要求返回最大价值

从左往右的依次尝试， 例如：有0，1，2号三个货物，分别有其对应的价值
从0开始往右尝试

尝试函数
index 表示当前考虑到了index号货物
rest表示背包所剩余的容量

终止条件：当index=w.length ，表示所有货物都已经考虑完了
rest<0 说明背包没有容量了 ，rest==0的时候不是终止，因为有可能有的货物的重量就是0而且他还有价值

当还有货物时：，对于当前的货有两种选择
1.不要当前的货，背包容量没有发生变化，考虑下一个货物
2.要当前的货，rest要减掉当前货物的重量.但是在选择要当前的货物之前，要判断背包剩余的容量，在能装下该货物的前提下，返回两种情况的较大值。

源码：
⭐️

public static int process1(int[] w,int[] v,int index,int rest){
    if(rest<0){
        return -1;
    }
    if(index==w.length){
        return 0;
    }
     int p1=process1(w,v,index+1,rest);
    int p2=0;
    int next=process1(w,v,index+1,rest-w[index]);
    if(next!=-1){
        p2=v[index]+next;
    }

    return Math.max(p1,p2);

}
    public static  int maxValue1(int[] w,int[] v,int bag){
        if(w==null||v==null||w.length==0||v.length==0||w.length!=v.length){
            return 0;
        }
        return process1(w,v,0,bag);
    }

填表
分析依赖关系
递归函数中有两个变量时在变的：
1.index 变化范围时0~N N 代表货物总数
2.rest 变化范围是 负数~bag 但当rest<0时值都为-1
根据这两个变量的变化范围来确定缓存表的大小

源码：
:

    public static  int maxValue2(int[] w,int[] v,int bag){
        int N=w.length;
        int[][] dp=new int[N+1][bag+1];
        for(int index=N-1;index>=0;index--){
            for (int rest=0;rest<=bag;rest++){
                int p1=dp[index+1][rest];
                int p2=0;
                int next=rest-w[index]<0?-1:dp[index+1][rest-w[index]];
                if(next!=-1){
                    p2=v[index]+next;
                }
                dp[index][rest]=Math.max(p1,p2);
            }
        }
     return dp[0][bag];
    }