盈利计划 Profitable Schemes

[Shellbye]

这次的这个动态规划题目，我打算先自己来，把自己的思考过程记录下来。

题目

帮派里有 G 名成员，他们可能犯下各种各样的罪行。 第 i 种犯罪会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。 让我们把这些犯罪的任何子集称为盈利计划，该计划至少产生 P 的利润。 有多少种方案可以选择？因为答案很大，所以返回它模 10^9 + 7 的值。

示例 1：

输入：G = 5, P = 3, group = [2,2], profit = [2,3] 输出：2 解释： 至少产生 3 的利润，该帮派可以犯下罪 0 和罪 1 ，或仅犯下罪 1 。 总的来说，有两种方案。

示例 2:

输入：G = 10, P = 5, group = [2,3,5], profit = [6,7,8] 输出：7 解释： 至少产生 5 的利润，只要他们犯其中一种罪就行，所以该帮派可以犯下任何罪行 。 有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

提示：

1 <= G <= 100 0 <= P <= 100 1 <= group[i] <= 100 0 <= profit[i] <= 100 1 <= group.length = profit.length <= 100

初始思路与超级暴力解法

题目的条件翻译成数学语言应该是

groug(1)+groug(2)+groug(i)+...+groug(n) <= G

profit(1)+profit(2)+profit(i)+...+profit(n) >= P

因为这个题目是关于动态规划的，那么就考虑用动态规划的套路来解，首先就是考虑怎么把问题拆分成子问题，首先想到的就是这个分组的方法，把group里面的数划分成两部分（其中一部分为X个），那么其盈利方式sep(G)就可以表示成两个子问题的和

sep(G) = sep(G-X)+sep(X)

这样看起来似乎没问题，但是这里有一个问题，就是拆分的这两部分单独都无法满足条件，但是他们加起来是可以的，所以这样的划分方法是不对的。既然想不到一些优雅的方法，那就看看有没有暴力解法，这个题目里的暴力解法还是比较明显，就是求group的所有组合（参考求组合的方法 #44 ），然后分别计算这些组合的盈利能力。

class Solution {
    public int profitableSchemes(int G, int P, int[] group, int[] profit) {
        int count = 0;
        List<List<Integer>> allCom = this.combine(group.length, 1);
        for (int i = 2; i <= group.length; i++) {
            List<List<Integer>> t = this.combine(group.length, i);
            allCom.addAll(t);
        }
        for (List list : allCom) {
            int total_g = 0, total_p = 0;
            for (Object i : list) {
                int idx = (Integer)i - 1;
                // check profit
                total_g += group[idx];
                total_p += profit[idx];
            }
            if (total_g <= G && total_p >= P)
                count++;
        }
        return count;
    }
    
    public List<List<Integer>> combine(int n, int k) {
        if (n == k) {
            List<Integer> row = new ArrayList<>();
            for (int i = 1; i <= n; i++) {
                row.add(i); // select all
            }
            List<List<Integer>> ret = new LinkedList<>();
            ret.add(row);
            return ret;
        }
        if (k == 0) {
            List<Integer> row = new ArrayList<>();
            List<List<Integer>> ret = new LinkedList<>();
            ret.add(row);
            return ret;
        }

        List<List<Integer>> ret = this.combine(n - 1, k - 1);
        for (List<Integer> list : ret) {
            list.add(n);
        }
        ret.addAll(this.combine(n - 1, k));
        return ret;
    }
}

很显然，这是一个开销太大的方法，它不分青红皂白的检查了所有的组合（关键是还计算了所有组合），其中其实很有大一部分是可以省略的。

动态规划的解法

在探索动态规划的解法过程中，看到这篇文章的一个代码量特别小的解法，但是我还没搞懂其中

        if(G >= group[k]) 
        {
            int tp = P - profit[k];
            if(tp < 0) tp = 0;
            ans = profitableSchemes(flag, G-group[k], tp, group, profit, k+1);
        }
        ans = (ans + profitableSchemes(flag, G, P, group, profit, k+1))%1000000007;

其中的两个profitableSchemes，难道不是都考虑了包含k的情况？第一种是显然包含k的，所以需要再考虑除了k之外剩下有多少中方法；第二种，讨论k + 1，难道不是也相当于把k考虑进去了？ 🤔

在看了两边这个Youtube的视频讲解之后，我终于搞懂了上面的代码的含义，然后我用了一个相对简单的代码实现了一遍，因为没有存储中间的计算结果，所以超时了，但是逻辑起码是对的

class Solution {
    public int profitableSchemes(int G, int P, int[] group, int[] profit) {
        return profitableSchemesV1(G, P, group, profit, 0);
    }
    
    public int profitableSchemesV1(int G, int P, int[] group, int[] profit, int k) {
        // 退出条件，类似斐波那契数列里面的Fib(0)和Fib(1)
        if (k >= group.length && P <= 0 && G >= 0)
            return 1;
        if (G < 0)
            return 0;
        if (k >= group.length)
            return 0;
        
        int count = 0;
        if (G >= group[k]) {
            // 做第k个任务的情况下，后面的情况就是G和P都减少了
            int tp = P - profit[k];
            if (tp < 0)
                tp = 0;
            count += this.profitableSchemesV1(G - group[k], tp, group, profit, k + 1); 
        }
        // 第k个任务不错，所有的G和P都留给后面消耗
        count += this.profitableSchemesV1(G, P, group, profit, k + 1);
        return count;
    }
}

注释里已经写了我最新的理解，这次应该是没有问题了，之前的问题在于我在“反向理解”，总把profitableSchemesV1(G, P, group, profit, k + 1)理解成“前”k次的结果，但其实应该按照注释里理解的那样，而是后k + 1的结果。那么我们最初的公式就需要修改一下了

sep(G) = sep(G - K)+sep(G + K)

这里公式的物理意义就是：G这么多人，要实现P这么多的利润，有两种方法，即做K这个方案和不做K这个方案。 上面的解法虽然逻辑上是对的，但是因为大量的重复计算导致效率非常低，我没仔细算，但是我估计应该是和递归版本的斐波那契数列是一样的，即O(2^N)。

带记忆的动态规划的解法

为了避免重复计算，这次我们用一个数组把中间结果都记录下来

class Solution {
    public int profitableSchemes(int G, int P, int[] group, int[] profit) {
        int n = 101;
        int[][][] flag = new int[n][n][n];

        return profitableSchemesV2(flag, G, P, group, profit, 0);
    }
    
    public int profitableSchemesV2(int[][][] flag, int G, int P, int[] group, int[] profit, int k) {
        if (k >= group.length && P <= 0 && G >= 0)
            return 1;
        if (G < 0)
            return 0;
        if (k >= group.length)
            return 0;

        if (flag[G][P][k] != 0)
            return flag[G][P][k];

        int count = 0;
        if (G >= group[k]) {
            // 做第k个任务的情况下
            int tp = P - profit[k];
            if (tp < 0)
                tp = 0;
            count += profitableSchemesV2(flag, G - group[k], tp, group, profit, k + 1);  // 前k个任务，不能使用后面的任务
        }

        count = (count + profitableSchemesV2(flag, G, P, group, profit, k + 1)) % 1000000007;
        flag[G][P][k] = count;
        return count;
    }
}

参考资料

https://blog.csdn.net/yanglingwell/article/details/81302278 https://www.youtube.com/watch?v=MjOIR61txFc