0-1背包问题 完全背包 多重背包

参考博客链接：https://blog.csdn.net/BestFM/article/details/79685329
https://blog.csdn.net/alidingding/article/details/104143826

动态规划之0-1背包问题

问题描述：有N件物品和一个容量为V的背包。第i件物品的价值是v[i]，重量是w[i]。求解将哪些物品装入背包可使价值总和最大。

class Main {
    public static void main(String[] args) {
        int m = 100;//钱
        int n = 5;//物品数量
        int[] w = {0,77,22,29,50,99};//价格
        int[] v = {0,92,22,36,46,90};//价值

        int[][] dp = new int[n+1][m+1];
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                if(j >= w[i]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i]] + v[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}

压缩为一维数组

class Main {
    public static void main(String[] args) {
        int m = 100;//钱
        int n = 5;//物品数量
        int[] w = {0,77,22,29,50,99};//价格
        int[] v = {0,92,22,36,46,90};//价值

        int[] dp = new int[m+1];
        for(int i = 1;i <= n;i++){
            /*0-1背包和完全背包区别在于：    
            0-1背包从 m 向 W[j] 遍历
            完全背包从 W[j] 向 m 便利
            */
            for(int j = m;j >= w[i];j--){
                dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        System.out.println(dp[m]);
    }
}

动态规划之完全背包

问题描述：有一个容积为V的背包，同时有n种物品，每种物品均有无数多个，并且每种物品的都有自己的体积和价值。求使用该背包最多能够装的物品价值总和。

class Main {
    public static void main(String[] args) {
        int m = 100;//钱
        int n = 5;//物品数量
        int[] w = {0,77,22,29,50,99};//价格
        int[] v = {0,92,22,36,46,90};//价值

        int[][] dp = new int[n+1][m+1];
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                if(j >= w[i]){
                    int max = 0;
                    for(int k = 1;k <= j/w[i];k++){
                        if(dp[i-1][j-k*w[i]]+k*v[i] > max){
                            t = dp[i-1][j-k*w[i]]+k*v[i];
                        }
                    }
                    dp[i][j] = Math.max(dp[i-1][j],max);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}

或者

class Main {
    public static void main(String[] args) {

        int m = 100;//钱
        int n = 5;//物品数量
        int[] w = {0,77,22,29,50,99};//价格
        int[] v = {0,92,22,36,46,90};//价值

        int[][] dp = new int[n+1][m+1];
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                if(j >= w[i]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}

压缩为一维数组

class Main {
    public static void main(String[] args) {
        int m = 100;//钱
        int n = 5;//物品数量
        int[] w = {0,77,22,29,50,99};//价格
        int[] v = {0,92,22,36,46,90};//价值

        int[] dp = new int[m+1];
        for(int i = 1;i <= n;i++){
            for(int j = w[i];j <= m;j++){
                dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        System.out.println(dp[m]);
    }
}

动态规划之多重背包问题

问题描述：多重背包是在完全背包的基础上，加了个条件：第 i 件物品有路面num[i]件。

class Main {
    public static void main(String[] args) {
        int m = 100;//钱
        int n = 5;//物品数量
        int[] w = {0,77,22,29,50,99};//价格
        int[] v = {0,92,22,36,46,90};//价值
        int[] num = {0,10,20,30,40,50};//每个物品最大的数量

        int[][] dp = new int[n+1][m+1];
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                if(j >= w[i]){
                    int max = 0;
                    //多重背包和完全背包只差k <= num[i]，因为这是限定取物品的数量不超过该物品总量
                    for(int k = 1;k <= j/w[i] && k <= num[i];k++){
                        if(dp[i-1][j-k*w[i]]+k*v[i] > max){
                            t = dp[i-1][j-k*w[i]]+k*v[i];
                        }
                    }
                    dp[i][j] = Math.max(dp[i-1][j],max);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}