背包 DP

• OI Wiki: https://oi-wiki.org/dp/knapsack/

题目	难度
洛谷 P2871 [USACO07DEC]Charm Bracelet S		0-1 背包
416. 分割等和子集	中等	0-1 背包
494. 目标和	中等	0-1 背包 求方案数
879. 盈利计划	困难	0-1 背包 求方案数
顺丰 02. 小哥派件装载问题	中等	0-1 背包

题目	难度
洛谷 P1616 疯狂的采药		完全背包
322. 零钱兑换	中等	完全背包 求最小
377. 组合总和 Ⅳ	中等	完全背包 求方案数
面试题 08.11. 硬币	中等	完全背包

题目	难度
2585. 获得分数的方法数	困难	多重背包 求方案数

题目	难度
474. 一和零	中等	二维费用背包

题目	难度
洛谷 P1757 通天之分组背包		分组背包
2218. 从栈中取出 K 个硬币的最大面值和	困难	分组背包

0-1 背包

每个物体只有两种可能的状态（取与不取），对应二进制中的 和 ，这类问题便被称为「0-1 背包问题」。

洛谷 P2871 [USACO07DEC]Charm Bracelet S

import java.io.IOException;
import java.util.Scanner;

public class LuoguP2871 {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        // 有 N 件物品和一个容量为 M 的背包。
        int N = scanner.nextInt();
        int M = scanner.nextInt();

        // 第 i 件物品的重量是 wi，价值是 vi
        int[] W = new int[N];
        int[] D = new int[N];
        for (int i = 0; i < N; i++) {
            W[i] = scanner.nextInt();
            D[i] = scanner.nextInt();
        }

        // 0-1 背包
        // f[j] 代表容量为 j 的背包能达到的最大价值
        int[] f = new int[M + 1];
        for (int i = 0; i < N; i++) {
            int wi = W[i];
            int vi = D[i];
            for (int j = M; j >= wi; j--) {
                f[j] = Math.max(f[j], f[j - wi] + vi);
            }
        }
        System.out.println(f[M]);
    }
}

416. 分割等和子集

import java.util.Arrays;

public class Solution416 {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();

        if (sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;

        // 0-1 背包
        // f[j] 代表选择数字总和不超过 j 的最大和。
        int[] f = new int[target + 1];
        for (int wi : nums) {
            for (int j = target; j >= wi; j--) {
                f[j] = Math.max(f[j], f[j - wi] + wi);
            }
        }
        return f[target] == target;
    }
}

494. 目标和

import java.util.Arrays;

public class Solution494 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();

        // 负数和 neg，正数和 sum-neg，sum - 2 * neg = target
        if ((sum - target < 0) || (sum - target) % 2 == 1) {
            return 0;
        }
        int neg = (sum - target) / 2;

        // 0-1 背包
        // f[j] 表示元素之和等于 j 的方案数。
        int[] f = new int[neg + 1];
        f[0] = 1;
        for (int wi : nums) {
            for (int j = neg; j >= wi; j--) {
                f[j] += f[j - wi];
            }
        }
        return f[neg];
    }
}

879. 盈利计划

public class Solution879 {
    private static final int MOD = (int) (1e9 + 7);

    // https://leetcode.cn/problems/profitable-schemes/solution/leetcode-01bei-bao-zong-jie-by-pedantic-einstein/
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length;

        // 0-1 背包
        // f[j][k] 表示第 i 种工作，在 j 名成员参与下，获取 k 的利润的方案数
        int[][] f = new int[n + 1][minProfit + 1];
        // 如果不需要获取利润，成员人数符合条件都可以满足
        for (int j = 0; j < n + 1; j++) {
            f[j][0] = 1;
        }
        for (int i = 1; i <= len; i++) {
            int g = group[i - 1];
            int p = profit[i - 1];
            for (int j = n; j >= g; j--) {
                // 注意是 k >= 0 而不是 k >= p
                for (int k = minProfit; k >= 0; k--) {
                    // 在 k < p （剩余的所需利润 < 当前工作获取的利润）时，情况依然满足条件
                    f[j][k] = (f[j][k] + f[j - g][Math.max(0, k - p)]) % MOD;
                }
            }
        }
        return f[n][minProfit];
    }
}

顺丰 02. 小哥派件装载问题

public class SfTech220619T2 {
    public int minRemainingSpace(int[] N, int V) {
        // 0-1 背包
        int[] f = new int[V + 1];
        for (int wi : N) {
            for (int j = V; j >= wi; j--) {
                f[j] = Math.max(f[j], f[j - wi] + wi);
            }
        }
        return V - f[V];
    }
}

完全背包

完全背包模型与 0-1 背包类似，与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

洛谷 P1616 疯狂的采药

import java.io.IOException;
import java.util.Scanner;

public class LuoguP1616 {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        // 采药时间 t 和山洞草药数目 m
        int t = scanner.nextInt();
        int m = scanner.nextInt();

        // ai 采药时间，bi 草药价值
        int[] a = new int[m];
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            a[i] = scanner.nextInt();
            b[i] = scanner.nextInt();
        }

        // 完全背包
        // f[j] 代表容量为 j 的背包能达到的最大价值
        long[] f = new long[t + 1];
        for (int i = 0; i < m; i++) {
            int wi = a[i];
            int vi = b[i];
            for (int j = wi; j <= t; j++) {
                f[j] = Math.max(f[j], f[j - wi] + vi);
            }
        }
        System.out.println(f[t]);
    }
}

322. 零钱兑换

public class Solution322 {
    public int coinChange(int[] coins, int amount) {
        // 完全背包
        // f[i] 表示凑出总额为 i 的硬币需要的最少的数目
        int[] f = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            f[i] = amount + 1;
            for (int coin : coins) {
                if (i >= coin) {
                    f[i] = Math.min(f[i], f[i - coin] + 1);
                }
            }
        }
        return (f[amount] > amount) ? -1 : f[amount];
    }
}

377. 组合总和 Ⅳ

public class Solution377 {
    public int combinationSum4(int[] nums, int target) {
        // 完全背包
        // f[j] 表示和为 i 的排列的数目
        int[] f = new int[target + 1];
        f[0] = 1;
        for (int j = 1; j <= target; j++) {
            for (int wi : nums) {
                if (j >= wi) {
                    f[j] += f[j - wi];
                }
            }
        }
        return f[target];
    }
}

面试题 08.11. 硬币

public class SolutionI0811 {
    public int waysToChange(int n) {
        int[] coins = {25, 10, 5, 1};
        // 完全背包
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int wi : coins) {
            for (int i = wi; i <= n; i++) {
                f[i] += f[i - wi];
                f[i] %= 1000000007;
            }
        }
        return f[n];
    }
}

多重背包

2585. 获得分数的方法数

public class Solution2585 {
    private static final int MOD = (int) (1e9 + 7);

    public int waysToReachTarget(int target, int[][] types) {
        // 多重背包 求方案数
        long[] f = new long[target + 1];
        f[0] = 1L;

        for (int[] type : types) {
            for (int j = target; j >= type[1]; j--) {
                for (int k = 1; k <= type[0] && k * type[1] <= j; k++) {
                    f[j] = (f[j] + f[j - k * type[1]]) % MOD;
                }
            }
        }
        return (int) f[target];
    }
}

二维费用背包

474. 一和零

public class Solution474 {
    public int findMaxForm(String[] strs, int m, int n) {
        // 二维费用背包
        // f[j][k] 表示最多有 m 个 0 和 n 个 1 的最大子集的长度
        int[][] f = new int[m + 1][n + 1];
        for (String s : strs) {
            // 0 的个数，1 的个数
            int cnt0 = 0;
            for (char ch : s.toCharArray()) {
                if (ch == '0') {
                    cnt0++;
                }
            }
            int cnt1 = s.length() - cnt0;

            for (int j = m; j >= cnt0; j--) {
                for (int k = n; k >= cnt1; k--) {
                    f[j][k] = Math.max(f[j][k], f[j - cnt0][k - cnt1] + 1);
                }
            }
        }
        return f[m][n];
    }
}

分组背包

从「在所有物品中选择一件」变成了「从当前组中选择一件」，于是就对每一组进行一次 0-1 背包就可以了。

洛谷 P1757 通天之分组背包

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

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

        // 物品的重量，利用价值，所属组数
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
            b[i] = scanner.nextInt();
            c[i] = scanner.nextInt();
        }
        System.out.println(solve(m, n, a, b, c));
    }

    private static String solve(int m, int n, int[] a, int[] b, int[] c) {
        // 分组
        Map<Integer, List<Integer>> idListMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            idListMap.computeIfAbsent(c[i], key -> new ArrayList<>()).add(i);
        }

        // 分组背包
        // f[j] 代表容量为 j 的背包能达到的最大价值
        int[] f = new int[m + 1];

        // 循环每一组
        for (Map.Entry<Integer, List<Integer>> entry : idListMap.entrySet()) {
            List<Integer> idList = entry.getValue();
            // 循环背包容量
            for (int i = m; i >= 0; i--) {
                for (int id : idList) {
                    if (i >= a[id]) {
                        f[i] = Math.max(f[i], f[i - a[id]] + b[id]);
                    }
                }
            }
        }
        return String.valueOf(f[m]);
    }
}

2218. 从栈中取出 K 个硬币的最大面值和

import java.util.List;

public class Solution2218 {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int[] f = new int[k + 1];

        // 循环每一组
        for (List<Integer> pile : piles) {
            int m = pile.size();
            for (int i = 1; i < m; i++) {
                // 价值为 pile.get(i), 重量为 i+1
                pile.set(i, pile.get(i) + pile.get(i - 1));
            }

            // 循环背包容量
            for (int i = k; i >= 0; i--) {
                for (int j = 0; j < m; j++) {
                    if (i >= j + 1) {
                        f[i] = Math.max(f[i], f[i - (j + 1)] + pile.get(j));
                    }
                }
            }
        }
        return f[k];
    }
}

参考链接

• 背包问题九讲 - 崔添翼
• dd 大牛的《背包九讲》

（全文完）