【动态规划/背包问题】特殊的多维费用背包问题

输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]

输出：2

解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。

输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]

输出：7

解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

class Solution {
    int mod = (int)1e9+7;
    public int profitableSchemes(int n, int min, int[] gs, int[] ps) {
        int m = gs.length;
        // f[i][j][k] 代表考虑前 i 个任务，使用人数不超过 j，产生利益至少 k 的方案数 
        int[][][] f = new int[m+1][n+1][min+1];
        // 初始化：当没有任务时，无论有多少人，只有利益至少为 0 时的方案数为 1，其他为 0 
        for (int j = 0; j <= n; j++) {
            f[0][j][0] = 1;
        }
        for (int i = 1; i <= m; i++) {
            int g = gs[i-1], p = ps[i-1];
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= min; k++) {
                    f[i][j][k] = f[i-1][j][k];
                    if (j >= g) {
                        f[i][j][k] += f[i-1][j-g][Math.max(0, k-p)];
                        f[i][j][k] %= mod;
                    }
                }
            }
        }
        return f[m][n][min];
    }
}

import java.math.BigInteger;
class Solution {
    static int N = 105;
    static BigInteger[][] f = new BigInteger[2][N]; 
    static BigInteger[][][] g = new BigInteger[2][N][N];
    static BigInteger mod = new BigInteger("1000000007");
    
    public int profitableSchemes(int n, int min, int[] gs, int[] ps) {
        int m = gs.length;

        for (int j = 0; j <= n; j++) {
            f[0][j] = new BigInteger("1"); 
            f[1][j] = new BigInteger("0"); 
        }
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= min; k++) {
                g[0][j][k] = new BigInteger("1"); 
                g[1][j][k] = new BigInteger("0"); 
            }
        }

        for (int i = 1; i <= m; i++) {
            int a = gs[i - 1], b = ps[i - 1];
            int x = i & 1, y = (i - 1) & 1;
            for (int j = 0; j <= n; j++) {
                f[x][j] = f[y][j];
                if (j >= a) {
                    f[x][j] = f[x][j].add(f[y][j-a]);
                } 
            }
        }
        if (min == 0) return (f[m&1][n]).mod(mod).intValue();

        for (int i = 1; i <= m; i++) {
            int a = gs[i - 1], b = ps[i - 1];
            int x = i & 1, y = (i - 1) & 1;
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k < min; k++) {
                    g[x][j][k] = g[y][j][k];
                    if (j - a >= 0 && k - b >= 0) {
                        g[x][j][k] = g[x][j][k].add(g[y][j-a][k-b]);
                    } 
                }
            }
        }

        return f[m&1][n].subtract(g[m&1][n][min-1]).mod(mod).intValue();
    }
}