Profitable Schemes


Problem

There is a group of nn members, and a list of various crimes they could commit. The ithi^{th} crime generates a profitiprofit_i and requires groupigroup_i 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 pp profit, and the total number of members participating in that subset of crimes is at most nn.

Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo 109+710^9 + 7.

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

  • 1n1001 \leq n \leq 100
  • 0m1000 \leq m \leq 100
  • 1group.length1001 \leq group.length \leq 100
  • 1groupi1001 \leq group_i \leq 100
  • 1profiti1001 \leq profit_i \leq 100
  • profit.length=group.lengthprofit.length = group.length

Submit your solution at here

Solution

Approach

  • Let f(n,p,c)f(n,p,c) denotes number of ways to use exact nn men, to generate exact pp profit, with first cc crimes (we don’t have to use all cc crimes)
  • By definition f(0,0,0)=1f(0,0,0) = 1 There are 11 way to do nothing and gain nothing
  • If we commit crime cc, we need to use group(c)group(c) men and we gain profit(c)profit(c) money
  • Recursively we have f(n,p,c)=f(n,p,c1)+f(ngroup(c),pprofit(c),c1)f(n,p,c) = f(n,p,c-1) + f(n-group(c),p-profit(c),c-1)

Complexity

  • Time complexity: O(n×m2×k)O(n \times m^2 \times k)
  • Space complexity: O(n×m2×k)O(n \times m^2 \times k)
  • Where nn is men count, mm is crimes count, and kk 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;
    }
}