背包九讲学习笔记

从上到下顺序遍历 01背包问题 使用二维数组

public class test1930 {
    public static void main(String[] args){
        int[] cost={0,2,2,6,5,4};//费用
        int[] value={0,6,3,5,4,6};//价值
        int N=5;//物品个数
        int V=10;//容量
        solvePackage(cost,value,N,V);
    }
    
    public static void solvePackage(int[] cost,int[] value,int N,int V){
        int[][] dp=new int[N+1][V+1];
        for(int i=1;i<=N;i++){
            for(int j=1;j<=V;j++){
                if(cost[i]<=j){
                    dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-cost[i]]+value[i]);
                }
                else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        System.out.println(dp[N][V]);
    }   
}

01背包问题 空间复杂度优化 使用一维数组

public class test1930 {
    public static void main(String[] args){
        int[] cost={0,2,2,6,5,4};//费用
        int[] value={0,6,3,5,4,6};//价值
        int N=5;//物品个数
        int V=10;//容量
        solvePackage(cost,value,N,V);
    }
    
    public static void solvePackage(int[] cost,int[] value,int N,int V){
        int[] dp=new int[V+1];
        for(int i=1;i<=N;i++)
            for(int j=V;j>=1;j--){
                if(cost[i]<=j){
                    dp[j]=Math.max(dp[j], dp[j-cost[i]]+value[i]);
                }
            }
        System.out.println(dp[V]);
    }
    
}

重点：此处必须从后往前遍历！！！不然数组的值会动态更改。
我们的dp[i][j]是通过dp[i-1][j]与dp[i-1][j-cost[i]]+value[i]两者的Max值获得的
化成一维数组。dp[j]是通过对应(i-1)的dp[j]与dp[j-cost[i]]获得的。我们只要这样存储就可以。

背包九讲原文截取

完全背包问题

public class test1930 {
    public static void main(String[] args){
        int[] cost={0,2,2,6,5,4};//费用
        int[] value={0,6,3,5,4,6};//价值
        int N=5;//物品个数
        int V=10;//容量
        allPackage(cost,value,N,V);
    }
    
    public static void allPackage(int[] cost,int[] value,int N,int V){
        int[] dp=new int[V+1];
        for(int i=1;i<=N;i++)
            for(int j=1;j<=V;j++){
                if(cost[i]<=j){
                    dp[j]=Math.max(dp[j], dp[j-cost[i]]+value[i]);
                }
            }
        System.out.println(dp[V]);
    }
}

完全背包问题就是在一维数组解决01背包问题的基础上进行更改。01背包需要倒序执行因为是往i-1范围内增加第i个，而完全背包问题则是向i范围内考虑是否增加i。表述不太清楚，可以看此处

背包九讲原文截取