DP - 类背包问题 - 《学习笔记》

956. 最高的广告牌

难度困难
你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。
你有一堆可以焊接在一起的钢筋 rods。举个例子，如果钢筋的长度为 1、2 和 3，则可以将它们焊接在一起形成长度为 6 的支架。
返回 广告牌的最大可能安装高度 。如果没法安装广告牌，请返回 0 。

示例 1：
输入：[1,2,3,6] 输出：6 解释：我们有两个不相交的子集 {1,2,3} 和 {6}，它们具有相同的和 sum = 6。
示例 2：
输入：[1,2,3,4,5,6] 输出：10 解释：我们有两个不相交的子集 {2,3,5} 和 {4,6}，它们具有相同的和 sum = 10。
示例 3：
输入：[1,2] 输出：0 解释：没法安装广告牌，所以返回 0。

提示：

0 <= rods.length <= 20
1 <= rods[i] <= 1000
sum(rods[i]) <= 5000

思路：
受限制的选择最优化问题
f[i][j]表示从前i个物品中选，且左右高度差为j的所有方案
属性：左柱的最大高度
状态转移：
不用第i件物品
f[i][j] = f[i - 1][j]
用第i件物品，放左边
f[i][j] = f[i - 1][j - rods[i-1]] + rods[i-1]
用第i件物品，放右边
f[i][j] = f[i - 1][j + rods[i - 1]]
初始化：f[i][j] = -0x3f3f3f3f, f[0][m] = 0
这里需要做一个映射，因为左边高度如果小于右边, j为负值，而数组下标不能为负数，故整体右移m

class Solution {
    public int tallestBillboard(int[] rods) {
        int n = rods.length, m = Arrays.stream(rods).sum();
        int[][] f = new int[n + 1][2 * m + 1];
        for (int i = 0; i <= n; i++)
            Arrays.fill(f[i], (int)(-1e8));
        f[0][m] = 0;
        for (int i = 1; i <= n; i++) {
            int x = rods[i - 1];
            for (int j = 0; j <= 2 * m; j++) {
                f[i][j] = f[i - 1][j];
                if (j - x >= 0)
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - x] + x);
                if (j + x <= 2 * m)
                    f[i][j] = Math.max(f[i][j], f[i - 1][j + x]);
            }
        }
        return f[n][m];
    }
}

1751. 最多可以参加的会议数目 II

物品之间有选择限制的01背包问题

二进制枚举的背包问题

1434. 每个人戴不同帽子的方案数

总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 。
给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表。
请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。
由于答案可能很大，请返回它对 10^9 + 7 取余后的结果。

示例 1：
输入：hats = [[3,4],[4,5],[5]] 输出：1 解释：给定条件下只有一种方法选择帽子。第一个人选择帽子 3，第二个人选择帽子 4，最后一个人选择帽子 5。
示例 2：
输入：hats = [[3,5,1],[3,5]] 输出：4 解释：总共有 4 种安排帽子的方法： (3,5)，(5,3)，(1,3) 和 (1,5)
示例 3：
输入：hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]] 输出：24 解释：每个人都可以从编号为 1 到 4 的帽子中选。 (1,2,3,4) 4 个帽子的排列方案数为 24 。
示例 4：
输入：hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]] 输出：111

提示：

n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i] 包含一个数字互不相同的整数列表。

思路：
f[i][j]表示考虑前i个帽子分配给状态为j的人的总分配方案。其中j是二进制表示，每一位为1表示这一位的人被分配帽子，否则没被分配

class Solution {
    public int numberWays(List<List<Integer>> hats) {
        int mod = (int)(1e9 + 7);
        int n = hats.size();
        int[] f = new int[1 << n];
        long[] like = new long[n];
        boolean[] st = new boolean[41];
        int idx = 0;
        for (var list : hats) {
            long x = 0;
            for (int v : list) {
                x |= 1L << v;
                st[v] = true;
            }
            like[idx++] = x;
        }
        // System.out.println(Arrays.toString(like));
        f[0] = 1;
        for (int i = 1; i <= 40; i++) {
            if (!st[i]) continue;
            for (int j = (1 << n) - 1; j >= 0; j--) {
                for (int k = 0; k < n; k++) {
                    if ((j >> k & 1) == 0 && (like[k] >> i & 1) == 1) {
                        // System.out.println(i + " " + j + " " + k + " " + f[i - 1][j]);
                        f[j | (1 << k)] = (f[j | (1 << k)] + f[j]) % mod;
                    }
                }
            }
        }
        return f[(1 << n) - 1];
    }
}

1125. 最小的必要团队

作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。
所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：

例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。

请你返回任一规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。

示例 1：
输入：req_skills = [“java”,”nodejs”,”reactjs”], people = [[“java”],[“nodejs”],[“nodejs”,”reactjs”]] 输出：[0,2]
示例 2：
输入：req_skills = [“algorithms”,”math”,”java”,”reactjs”,”csharp”,”aws”], people = [[“algorithms”,”math”,”java”],[“algorithms”,”math”,”reactjs”],[“java”,”csharp”,”aws”],[“reactjs”,”csharp”],[“csharp”,”math”],[“aws”,”java”]] 输出：[1,2]

提示：

1 <= req_skills.length <= 16
1 <= req_skills[i].length <= 16
req_skills[i] 由小写英文字母组成
req_skills 中的所有字符串 互不相同
1 <= people.length <= 60
0 <= people[i].length <= 16
1 <= people[i][j].length <= 16
people[i][j] 由小写英文字母组成
people[i] 中的所有字符串 互不相同
people[i] 中的每个技能是 req_skills 中的技能
题目数据保证「必要团队」一定存在

思路：
背包问题
枚举每个成员
枚举技能状态

初始化问题：f[i][j] = 0x3f3f3f3f, f[0][0] = 0

class Solution {
    public int[] smallestSufficientTeam(String[] r, List<List<String>> people) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < r.length; i++)
            map.put(r[i], i);
        int n = people.size(), m = r.length;
        int[] st = new int[n];
        for (int i = 0; i < n; i++) {
            List<String> list = people.get(i);
            int x = 0;
            for (String s : list) {
                x |= 1 << (map.get(s));
            }
            st[i] = x;
        }
        int[] f = new int[1 << m];
        long[] g = new long[1 << m];
        Arrays.fill(f, 0x3f3f3f3f);
        f[0] = 0;
        for (int i = 0; i < n; i++) {
            int x = st[i];
            for (int j = (1 << m) - 1; j >= 0; j--) {
                if (f[j] == 0x3f3f3f3f) continue;
                if (f[x | j] > f[j] + 1) {
                    f[x | j] = f[j] + 1;
                    g[x | j] = g[j] | (1L << i);
                }
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((g[(1 << m) - 1] >> i & 1) == 1)
                res.add(i);
        }
        int[] ans = new int[res.size()];
        for (int j = 0; j < res.size(); j++)
            ans[j] = res.get(j);
        return ans; 
    }
}