879. 盈利计划

发表于 分类于 阅读次数： Waline： 本文字数： 486 阅读时长 ≈ 2 分钟

考点

  • 01背包
  • “至少”的判定

思路

01背包的精髓题，会了之后可以触类旁通

设如下状态转移方程

1
2
3
4
5
6
7
8
9
f[i][j][k]: 前i个数组成的序列, 背包容量达到j, 盈利大于等于k的个数
考虑Push方向, 已知f[i], 转移到f[i+1]
不考虑第i+1个数, f[i+1][j][k] += f[i][j][k]
考虑第i+1个数, 
if (j + group[i] <= 背包大小) {
	// >= 7的数肯定也>= 5, 所以就算大于minProfit, 也可以累加到minProfit上
    int x = min(minProfit, k + profit[i]);
    f[i + 1][j + group[i]][x] += f[i][j][k];
}

得到如下第一版AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  static const int maxn = 1e2 + 50, mod = 1e9 + 7;
  // f[i][j][k]: 前i个数，容量达到j时，盈利大于等于k的个数
  int n;
  long long f[maxn][maxn][maxn];
  int profitableSchemes(int m, int minProfit, vector<int>& group,
                        vector<int>& profit) {
    n = group.size();
    memset(f, 0, sizeof(f));
    f[0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j <= m; ++j) {
        for (int k = 0; k <= minProfit; ++k) {
          f[i + 1][j][k] = (f[i + 1][j][k] + f[i][j][k]) % mod;
          if (j + group[i] <= m) {
            int x = min(minProfit, k + profit[i]);
            f[i + 1][j + group[i]][x] =
                (f[i + 1][j + group[i]][x] + f[i][j][k]) % mod;
          }
        }
      }
    }
    long long sum = 0;
    for (int i = 0; i <= m; ++i) sum = (sum + f[n][i][minProfit]) % mod;
    return sum;
  }
};

当然，可以原地滚掉第一维减少常数

这里要注意，j必须逆向，但是k不必要，因为每次是用第j层的k去更新其他层，不会覆盖旧数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  static const int maxn = 1e2 + 50, mod = 1e9 + 7;
  int n;
  long long f[maxn][maxn];
  int profitableSchemes(int m, int minProfit, vector<int>& group,
                        vector<int>& profit) {
    n = group.size();
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = m; j >= 0; --j) {
        for (int k = 0; k <= minProfit; ++k) {
          if (j + group[i] <= m) {
            int x = min(minProfit, k + profit[i]);
            f[j + group[i]][x] = (f[j + group[i]][x] + f[j][k]) % mod;
          }
        }
      }
    }
    long long sum = 0;
    for (int i = 0; i <= m; ++i) sum = (sum + f[i][minProfit]) % mod;
    return sum;
  }
};