0-1 背包[二维]

import java.util.*;

public class Main{

    static final int N = 1010;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    // v[i]代表第i件物品的体积。
    static int[] v = new int[N];
    // w[i]代表第i件物品的价值。
    static int[] w = new int[N];
    // dp[N][N]代表动态规划数组。
    static int[][] dp = new int[N][N];

    public static void main(String... args){
        var sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        // 读入每件物品的体积和价值，并分别存入v和w中。
        for (int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

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

0-1 背包[一维]

import java.util.*;

public class Main{

    static final int N = 1010;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    // v[i]代表第i件物品的体积。
    static int[]  v = new int[N];
    // w[i]代表第i件物品的价值。
    static int[]  w = new int[N];
    // dp[N]代表动态规划数组。
    static int[] dp = new int[N];

    public static void main(String... args){
        var sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        // 读入每件物品的体积和价值，并分别存入v和w中。
        for (int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

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

完全 背包[二维]

import java.util.*;

public class Main{

    static final int N = 1010;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    // v[i]  代表第i件物品的体积。
    static int[] v = new int[N];
    // w[i]  代表第i件物品的价值。
    static int[] w = new int[N];
    // dp[][] 代表动态规划数组
    static int[][] dp = new int[N][N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();

        // 读入每件物品的体积和价值，并分别存入v和w中。
        for (int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

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

完全 背包[一维]

import java.util.*;

public class Main{

    static final int N = 1010;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    // v[i]  代表第i件物品的体积。
    static int[]  v = new int[N];
    // w[i]  代表第i件物品的价值。
    static int[]  w = new int[N];
    // dp[][] 代表动态规划数组
    static int[] dp = new int[N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();

        // 读入每件物品的体积和价值，并分别存入v和w中。
        for (int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

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

多重 背包[二维]

import java.util.*;

public class Main{

    static int N = 110;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    // v[i]  代表第i件物品的体积。
    static int[] v = new int[N];
    // w[i]  代表第i件物品的价值。
    static int[] w = new int[N];
    // s[i]  代表第i件物品的可选数量。
    static int[] s = new int[N];
    // dp[][] 代表动态规划数组
    static int[][] dp = new int[N][N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
            s[i] = sc.nextInt();
        }

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

多重 背包[一维]

import java.util.*;

public class Main{

    static int N = 110;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    // v[i]  代表第i件物品的体积。
    static int[]  v = new int[N];
    // w[i]  代表第i件物品的价值。
    static int[]  w = new int[N];
    // s[i]  代表第i件物品的可选数量。
    static int[]  s = new int[N];
    // dp[][] 代表动态规划数组
    static int[] dp = new int[N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
            s[i] = sc.nextInt();
        }

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

多重 背包[一维、二进制优化]

import java.util.*;

public class Main{

    static final int N = 12000;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    static int[]  v = new int[N];
    static int[]  w = new int[N];
    static int[]  s = new int[N];
    static int[] dp = new int[N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        // Binary optimization
        // 20: 1 2 4 8 + 5
        int cnt = 0;
        for (int i = 1; i <= n; i++){
            // vv 代表第i件物品的体积。
            int vv = sc.nextInt();
            // ww 代表第i件物品的价值。
            int ww = sc.nextInt();
            // ss 代表第i件物品可以使用的最大次数。
            int ss = sc.nextInt();
            int k = 1;
            while (k <= ss){
                cnt++;
                v[cnt] = vv * k;
                w[cnt] = ww * k;
                ss -= k;
                k <<= 1;
            }
            if (ss > 0){
                cnt++;
                v[cnt] = vv * ss;
                w[cnt] = ww * ss;
            }
        }
        n = cnt;

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

分组 背包[一维]

import java.util.*;

public class Main{

    static final int N = 110;
    static int n = 0;
    static int m = 0;
    static int[][] v = new int[N][N];
    static int[][] w = new int[N][N];
    static int[]   s = new int[N];
    static int[]  dp = new int[N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 1; i <= n; i++){
            s[i] = sc.nextInt();
            for (int j = 1; j <= s[i]; j++){
                v[i][j] = sc.nextInt();
                w[i][j] = sc.nextInt();
            }
        }

        for (int i = 1; i <= n; i++){
            for (int j = m; j >= 0; j--){
                for (int k = 1; k <= s[i]; k++){
                    if (j - v[i][k] >= 0){
                        dp[j] = Math.max(dp[j], dp[j - v[i][k]] + w[i][k]);    
                    }
                }
            }
        }

        System.out.println(dp[m]);
    }
}