Profitable Schemes

Problem

There is a group of members, and a list of various crimes they could commit. The crime generates a and requires members to participate in it. If a member participates in one crime, that member can't participate in another crime.

Let's call a profitable scheme any subset of these crimes that generates at least profit, and the total number of members participating in that subset of crimes is at most .

Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo .

Example

Input: n = 5, p = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation: To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.

Input: n = 10, p = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation: To make a profit of at least 5, the group could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).

Constraints

Submit your solution at here

Solution

Approach

  • Let denotes number of ways to use exact men, to generate exact profit, with first crimes (we don't have to use all crimes)
  • By definition There are way to do nothing and gain nothing
  • If we commit crime , we need to use men and we gain money
  • Recursively we have

Complexity

  • Time complexity:
  • Space complexity:
  • Where is men count, is crimes count, and is average profit

Code

impl Solution {
    pub fn profitable_schemes(n: i32, min_profit: i32, group: Vec<i32>, profit: Vec<i32>) -> i32 {
        let INF = 1000_000_007;
        let n = n as usize;
        let p0 = min_profit as usize;
        let p = profit.iter().sum::<i32>() as usize;
        let c = group.len();
        let mut f = vec![vec![vec![0;c+1];p+1];n+1];
        // f(n, p, c), how many ways to use team exact n men, to generate exact p profit, using first c crimes
        f[0][0][0] = 1;
        for i in 0..=n {
            for j in 0..=p {
                for k in 0..c {
                    if(f[i][j][k] == 0) {
                        continue;
                    }
                    f[i][j][k+1] += f[i][j][k];
                    f[i][j][k+1] %= INF;
                    let men = i+group[k] as usize;
                    if men > n {
                        continue;
                    }
                    let gain = j+profit[k] as usize;
                    f[men][gain][k+1] += f[i][j][k];
                    f[men][gain][k+1] %= INF;
                }
            }
        }
        let mut ret = 0;
        for i in 0..=n {
            for j in p0..=p {
                ret += f[i][j][c];
                ret %= INF;
            }
        }
        //println!("{f:?}");
        return ret;
    }
}