879. 盈利计划

image.png
这一题我只能想到DFS，在人数以及盈利两个约束下很难写DP，而且盈利约束还不是不大于，而是不小于，学学三叶的思路：
image.png
逻辑上说比较清楚，对于上一个状态需要的至少利润为负，那么显然等价于至少利润为0
不过，具体的还是需要看看转移图才懂

  1. /// 879. 盈利计划
  2. pub fn profitable_schemes(n: i32, min_profit: i32, group: Vec<i32>, profit: Vec<i32>) -> i32 {
  3.     let mod1 = (1e9 as i64 + 7);
  4.     let (n, m, min) = (n as usize, group.len(), min_profit as usize);
  5.     // m个任务，n个人，至少min
  6.     let mut f = vec![vec![vec![0 as i64; min + 1]; n + 1]; m + 1];
  7.     for x in 0..=n {
  8.         f[0][x][0] = 1;
  9.     }
  10.     for i in 1..=m {
  11.         let peo = group[i-1] as usize;
  12.         let pro = profit[i-1] as usize;
  13.         for j in 0..=n {
  14.             for k in 0..=min {
  15.                 f[i][j][k] = f[i-1][j][k];
  16.                 if j >= peo {
  17.                     f[i][j][k] += f[i-1][j-peo][max(k as i64 - pro as i64, 0) as usize];
  18.                     if f[i][j][k] >= mod1 { f[i][j][k] -= mod1; }
  19.                 }
  20.             }
  21.         }
  22.     }
  23.     println!("{:?}", f);
  24.     f[m][n][min] as i32
  25. }

跑案例一：

  1. 5
  2. 3
  3. [2,2]
  4. [2,3]
  6. // 输出的dp:
  7. // 第一维：物品，第二维：人数，第三维：至少利润
  8. [
  9.     0: [
  10.         // 初始化，物品0的所有人数的情况下，获取至少利润为0都有一种方案
  11.         [1, 0, 0, 0], 
  12.         [1, 0, 0, 0], 
  13.         [1, 0, 0, 0], 
  14.         [1, 0, 0, 0], 
  15.         [1, 0, 0, 0], 
  16.         [1, 0, 0, 0]
  17.     ], 
  18.     1: [
  19.         [1, 0, 0, 0], 
  20.         [1, 0, 0, 0], 
  21.         [2, 1, 1, 0],  // 人数为2的时候，利润至少为0为2种，1为1种
  22.         [2, 1, 1, 0], 
  23.         [2, 1, 1, 0], 
  24.         [2, 1, 1, 0]
  25.     ], 
  26.     2: [
  27.         [1, 0, 0, 0], 
  28.         [1, 0, 0, 0], 
  29.         [3, 2, 2, 1],  
  30.         [3, 2, 2, 1], 
  31.         [4, 3, 3, 2], 
  32.         [4, 3, 3, 2]
  33.     ]
  34. ]