背包问题基础

墨蓝 2023-03-04 08:14 13阅读 0赞

# 0-1 背包问题 #

import java.util.Scanner;
    public class ZeroOne { 
    /** * 0 1 背包问题 * V[]表示物品的体积，W[]表示物体的价值。 * 采用动态规划来做 * 使用dp[i][j] 表示前 i 件物品恰放入一个容量为 j 的背包可以获得的最大价值。。dp[0-n][0-m] * 主要分为两种情况： * 1. 如果不装入第i个物品的时候,那么问题就转化为“前 i − 1 件物品放入容量为 j 的背包中”：dp[i][j] = dp[i-1][j]; * 2. 如果放第 i 件物品，那么问题就转化为“前 i − 1 件物品放入剩下的容量为 v − wi 的背包中”：dp[i][j] = dp[i-1][j-wi] * 状态转移方程是：dp[i][j] = max(dp[i-1][j],dp[i-1][j-wi]) * 初始化：dp[0][0] = 0; * * * */
        public static void main1(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            int numOfThing = scanner.nextInt();
            int vlumPackage = scanner.nextInt();
    
            int[] vlumOfThing= new int[numOfThing+1];
            int[] valueOfThing = new int[numOfThing+1];
    
            for(int i=1;i<=numOfThing;i++){ 
                vlumOfThing[i] = scanner.nextInt();
                valueOfThing[i] = scanner.nextInt();
            }
            int [][] dp = new int[numOfThing+1][vlumPackage+1];
            dp[0][0] = 0;
    
            for(int i=1;i<=numOfThing;i++){ 
                for(int j=0;j<=vlumPackage;j++){ 
                    dp[i][j] = dp[i-1][j];
                    if(j>=vlumOfThing[i]){ 
                        dp[i][j] = Math.max(dp[i][j],dp[i-1][j-vlumOfThing[i]]+valueOfThing[i]);
                    }
                }
            }
    
            int res =0;
            for(int i=0;i<=vlumPackage;i++){ 
                res = Math.max(dp[numOfThing][i],res);
            }
    
            System.out.println(res);
        }
    
    
        /** * 空间上的优化 * @param args */
        public static void main2(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            int numOfThing = scanner.nextInt();
            int vlumPackage = scanner.nextInt();
    
            int[] vlumOfThing= new int[numOfThing];
            int[] valueOfThing = new int[numOfThing];
    
            for(int i=0;i<numOfThing;i++){ 
                vlumOfThing[i] = scanner.nextInt();
                valueOfThing[i] = scanner.nextInt();
            }
            int []dp = new int[vlumPackage+1];
            dp[0] = 0;
            for(int i=0;i<numOfThing;i++){ 
                for(int j=vlumPackage;j>=vlumOfThing[i];j--){ 
                    dp[j] = Math.max(dp[j],dp[j-vlumOfThing[i]]+valueOfThing[i]);
                }
            }
            System.out.println(dp[vlumPackage]);
        }
    }

# 完全背包问题 #

import java.util.Scanner;
    public class AllPackage { 
        /** * 完全背包问题 * * * @param args */
        public static void main(String[] args) { 
            Scanner scanner  = new Scanner(System.in);
            int numThins = scanner.nextInt();
            int vlumPackage = scanner.nextInt();
    
            int[]dp = new int[vlumPackage+1];
            for(int i=0;i<numThins;i++){ 
                int cost,value;
                cost = scanner.nextInt();
                value =scanner.nextInt();
                for(int j=cost;j<vlumPackage;j++){ 
                    dp[j] = Math.max(dp[j],dp[j-cost]+value);
                }
            }
    
            System.out.println(dp[vlumPackage]);
        }
    }

# 多重背包的暴力解法 #

import java.util.Scanner;
    
    public class SomeThingPackage {
        /**
         * 多重背包问题？
         *
         * @param args
         */
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int numTing = scanner.nextInt();
            int vlumTing = scanner.nextInt();
            int[] dp = new int[vlumTing+1];
            for(int i=0;i<numTing;i++){
                int cost,value,num;
                cost =scanner.nextInt();
                value=scanner.nextInt();
                num =scanner.nextInt();
    
                for(int j=vlumTing;j>=cost;j--){
                    for(int k=1;k<=num && k*cost<=j;k++){
                        dp[j] = Math.max(dp[j],dp[j-cost*k]+k*value);
                    }
                }
            }
    
            System.out.println(dp[vlumTing]);
        }
    }