子集状压DP

2024-01-01 04:04:27

本来应该放到DP篇。但由于这个部分灵神单列了题单,我就按题单刷题记录单列一篇。位运算状压应该算是我入门第一个接触到的算法级别的trick。

详细的位运算trick参考灵神的详解:leetcode.cn/circle/discuss/CaOJ45/

知识图谱也列出来了:

因此本篇会略过位运算,仅将其作为工具。主要还是子集DP。

1. 周赛297 LC 2305 公平分发饼干

这题灵神标的1887。甚至不到K。但由于我压根没学过状压,这题就烂掉了。

另外DP是我的尤其弱项,基本很少有能靠自己想出来的,想出来的也基本都是板子题。一次双周赛118 T3的状态机DP,一次周赛377的floyd板子,还有一次忘了哪次双周赛出了个特别特别板的子集DP,算法导论课作业有过这题,大致就是问从一个集合中选取子集,能否组成某个目标值。这题是板中之板,刷烂了的题。只有这种很板或者很简单的DP我才能自己想出来,不然就是直接烂。

这题我一开始压根想不到DP,最小化最大值一眼二分板子,但是检查不会写,写了个贪心。然后WA。反例如下:

[15,18,19,5,6,13,15,20]
3

我是从大到小贪心选择的,过不了。感觉任何贪心都过不了,这就不是贪心题。另外二分可以用但没必要,直接可以DP求解的题没必要转判定。

现在进入正题,子集状压DP。

可以将题意理解为:将整个集合划分为k个子集,求所有划分方式中K个集合各自元素和最大值的最小值。(我在LC上做DP到现在,大几十题了,感觉DP最大的难点不是写状态转移方程,而是设计状态含义,这需要对题目有最本质的理解才能做到,很多时候我就是看不出题目的本质,DP设计不出。灵神的思路和视角一直都是直击本质的,看他做搜索题是一种享受)

令f[i][j]表示对于集合j,将其划分为i个子序列,所有划分方式中i个子序列元素和的最大值的最小值。

思路是枚举j的子集s,遍历每一种划分情况带来的代价(这个代价当然是一个最大值),然后取这些代价中的最小值。

  1. 枚举j的子集s,s 是 j 的一个子集,它有一个元素和 sum(s)
  2. 而目标的f[i][j]希望能有i个子集,现在我们单独计算了s这个子集,那么还有i-1个子集
  3. 这些子集可选的元素需要剔除掉s中的元素:j^s(^s代表异或,是位运算中的差集trick)
  4. 对于每种不同的划分{s,j^s} 都会产生一个子集元素和的最大值,那么我们的目的就是求这些最大值中的最小值
  5. 状态转移方程为:min ( max ( sum(s) , f[i-1][j^s] ) ) for s in j
  6. 由于我们想求的是将整个集合划分为k个子集的最小代价,那么答案就是f[k-1][(1<<n)-1]了。

在实现上,可以预先计算所有的子集和,这样之后要用sum(s)的时候直接查表就可以,这里就涉及到**判断子集元素**的技巧:

  1. 状压:1 << n
  2. 枚举:for i in (1 << n) for j in(1,n)
  3. 位与判断是否在该子集中:i>>j&1

另外还有枚举j的子集s,这涉及**枚举子集**的技巧:

  1. s=j
  2. s=(s-1)&j
  3. 直至s≤0

具体原理的证明就算了。例子在代码里:

import java.util.Arrays;

class Solution {
    public int distributeCookies(int[] cookies, int k) {
        // 题意:将整个集合划分为K个集合,求所有划分方式中K个集合各自元素和的最大值的最小值
        // 输入顺序随意

        // 令f[i][j]表示消耗i个子序列,这i个子序列组成集合j对应的i个集合各自元素和最大值的最小值
        int n = cookies.length;
        // 预先计算每个子集的和用来查表
        // 这里状压,比如 5D = 0101B,代表选取第1个元素和第3个元素(下标为0开始就是第0个和第2个)
        int[] sum = new int[1 << n];
        // 预计算子集和
        // 枚举
        for (int i = 1; i < 1 << n; i++) {
            // 遍历所有cookie,看谁被选中了,i本质上就是状压后的选择结果
            // 比如3个零食包,则共有8个子集,假设现在是0101B好了,说明选择了第0个和第2个零食包。
            // i = 0101B,j=0D->2D
            // i 右移0位,0101B,末尾1说明被选中,第零号零食包选中
            // i 右移1位,0010B,末尾0说明没被选中,第一号零食包没选中
            // i 右移2位,0001B,末尾1说明被选中,第二号零食包选中
            for(int j=0;j<n;j++){
                if((i>>j&1)==1){
                    sum[i]+=cookies[j];
                }
            }
        }

        // 状态转移
        int[][] f = new int[k][1 << n];
        // f[0]实际代表f[1],消耗一个子序列,f[i]对应上述的f[i+1],下标从0开始位置错开了
        // f[0]即消耗一个集合,这个集合就是枚举cookies的每一个子集,也就是sum对应的元素和数组
        f[0] = sum;
        // 最终目标f[k-1][1<<n],即将整个集合划分为k个子集的元素和的最大值的最小值
        for (int i = 1; i < k; i++) {
            for (int j = 0; j < (1 << n); j++) {
                // 这里状压,枚举j的子集
                // x & (x-1)
                // 例如求10110B的子集
                // 10110B-1B = 10101B
                // 10101B & 10110B = 10100B 确实是子集
                // 下一个子集从10100B开始
                // 10100B - 1B = 10011B
                // 10011B & 10110B = 10010B 也是子集
                // 这样枚举是不重不漏的
                // 证明就算了
                f[i][j] = (int) 1e9;
                for(int s = j; s > 0 ; s=(s-1)&j){
                    f[i][j] = Math.min(
                            f[i][j],
                            Math.max(sum[s],f[i-1][j^s]) // 差集位运算经典trick异或^
                    );
                }
            }
        }
        return f[k-1][(1<<n)-1];
    }
}

由于状态转移只和前一个f[i-1]有关,就可以滚动数组降空间了:

import java.util.Arrays;

class Solution {
    public int distributeCookies(int[] cookies, int k) {
        int n = cookies.length;
        int[] sum = new int[1 << n];
        for (int i = 1; i < 1 << n; i++) {
            for(int j=0;j<n;j++){
                if((i>>j&1)==1){
                    sum[i]+=cookies[j];
                }
            }
        }

        var f = sum.clone();
        for (var i = 1; i < k; i++) {
            for (var j = (1 << n) - 1; j > 0; j--) {
                for (var s = j; s > 0; s = (s - 1) & j) {
                    f[j] = Math.min(f[j], Math.max(f[j ^ s], sum[s]));
                }
            }
        }
        return f[(1 << n) - 1];
    }
}

文章来源:https://blog.csdn.net/lyh20021209/article/details/135310361
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。