有利可图的计划-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
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的量级里面？

代码：

```java
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;
    }
}
```

该分类下的相关小册推荐：

业务开发实用算法精讲

数据结构与算法(上)

编程之道-算法面试(下)

算法面试通关 50 讲

编程之道-算法面试(上)

数据结构与算法(下)

数据结构与算法之美