背包九讲学习笔记

落日映苍穹つ 2021-09-10 16:18 302阅读 0赞

从上到下顺序遍历 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\]\]获得的。我们只要这样存储就可以。

![5057999-e4c252a1166064ef.png][]

背包九讲原文截取

完全背包问题

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。表述不太清楚，可以看此处

![5057999-0443e3e3aa36ebfc.png][]

背包九讲原文截取

[5057999-e4c252a1166064ef.png]: /images/20210811/c6ce12b010f8491d9824f580eb60438e.png
[5057999-0443e3e3aa36ebfc.png]: /images/20210811/e4c809efcff947ffb988d0984236a97e.png