题目描述

给定有限的物品种类且每种物品数量有无限个（每种物品的容量是vi， 价值是wi），背包总容量V。使其装到背包中的物品达到最大价值。

朴素解法

动态规划 完全背包
状态表示：dp[i][j] 表示前i个物品装到容量j的价值
状态属性：max
状态计算：dp[i][j] = max(dp[i][j], dp[i-1][j-k*vi]+k*wi) 其中 k=[0, j/vi]

import java.util.*;

public class Main {
    static int N = 1010;
    static int V = 1010;
    static int[][] dp = new int[N][V];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int v = scanner.nextInt();

        for (int i=1; i<=n; i++) {
            int vi = scanner.nextInt();
            int wi = scanner.nextInt();
            for (int j=1; j<=v; j++) {
                for (int k=0; k*vi<=j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-k*vi]+k*wi);
                }
            }
        }

        System.out.println(dp[n][v]);
    }
}

二维数组优化

f[i,j] = max(f[i-1,j], f[i-1,j-vi]+wi, f[i-1,j-2*vi]+2*wi…)
f[i,j-vi] = max(f[i-1, j-vi]+wi, f[i-1,j-2*vi]+2*wi…)
对比：发现可优化到 f[i, j] = max(f[i-1,j], f[i,j-vi]+wi)
解释：前边的元素数据已经加wi, 而后再次加wi, 以达到加多次的wi

import java.util.*;

public class Main {
    static int N = 1010;
    static int V = 1010;
    static int[][] dp = new int[N][V];
    // static int[] dp = new int[V];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int v = scanner.nextInt();


        for (int i=1; i<=n; i++) {
            int vi = scanner.nextInt();
            int wi = scanner.nextInt();
            for (int j=1; j<=v; j++) {
                dp[i][j] = dp[i-1][j];
                if (j - vi >= 0) {
                    // 因为前边的元素数据已经加wi, 而后再次加wi, 以达到加多次的wi
                    dp[i][j] = Math.max(dp[i][j], dp[i][j-vi]+wi);
                }
            }
        }

        System.out.println(dp[n][v]);
    }
}

一维数组优化

与01背包循环方式相反，完全背包从小到大遍历，以达到一个物品多次累加的想法

import java.util.*;

public class Main {
    static int N = 1010;
    static int V = 1010;
    // static int[][] dp = new int[N][V];
    static int[] dp = new int[V];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int v = scanner.nextInt();

        for (int i=1; i<=n; i++) {
            int vi = scanner.nextInt();
            int wi = scanner.nextInt();
            for (int j=vi; j<=v; j++) {
                // 已经多次相加了
                dp[j] = Math.max(dp[j], dp[j-vi]+wi);
            }
        }

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