Skip to content

879. Profitable Schemes

879. Profitable Schemes

题目: https://leetcode.com/problems/profitable-schemes/

难度: Hard

题意：

  1. 给定一个集合，每个集合都有一个group和profile，给定两个数G和P
  2. 求在集合所有的子集合中，group和不大于G，并且profile和不小于P的子集合个数

思路：

  • 这是一个01背包模型的变种
  • 大家思考一下，01背包是说，给定一个集合，每个集合有一个成本和一个收益，求成本和不大于总成本的最大收益
  • 这个题有两个条件，因此有两个规划方向。这两个方向还不一样，group是约束条件，规划长度是1-G，而profile是下限，规划长度也是1-P（因为超过P再记录P的具体的值已经没有意义了，所以一切>=P都可用P代替）
  • 最后的结果就是总group在1-G中，并且总profile>=p的子集合个数
  • 复杂度是o(NGP)，看数据范围，是不是正好在10^6的量级里面？

代码：

class Solution {
    private static int MOD = 1000000007;

    public int profitableSchemes(int G, int P, int[] group, int[] profit) {
        int[][] dp = new int[G + 1][P + 1];
        for(int i = 0;i <= G;i++) {
            for (int j = 0;j <= P;j++) {
                dp[i][j] = 0;
            }
        }
        dp[0][0] = 1;
        for (int k = 0;k < group.length;k++) {
            for (int i = G;i >= 0;i--) {
                if (i + group[k] > G) {
                    continue;
                }
                for (int j = 0;j <= P;j++) {
                    int p = j + profit[k];
                    if (p > P) {
                        p = P;
                    }
                    dp[i + group[k]][p] += dp[i][j];
                    if (dp[i + group[k]][p] >= MOD) {
                        dp[i + group[k]][p] -= MOD;
                    }
                }
            }
        }
        int ret = 0;
        for (int i = 1;i <= G;i++) {
            ret += dp[i][P];
            if (ret >= MOD) {
                ret -= MOD;
            }
        }
        return ret;
    }
}
回到顶部