01背包问题
最简单经典的背包问题, 来看一下这个这个问题的一个具体背景:
题目描述:
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i i i件物品的体积是 v i v_i vi，价值是 w i w_i wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
思路分析
考虑用几维来表示解, 从第一维考虑, 够吗? 好像不是很够, 那用二维呢, 那f[i][j]好像能表示我们要解决的问题了, 即
我们可以表示为从1 ~ i个物品中选, 且所有物品体积之和不超过j的情况下的物品最大价值, 而我们要求解的答案即为从
N个物品中选, 且所选的物品体积之和不超过V的最大价值, 即f[i][j]
这里Dp问题的分析采用Y总的闫氏Dp分析法, 即从集合的角度来分析问题
| 集合 ： 从1 ~ i 种物品中选取，且所选物品体积之和小于 j 的一类集合
|------------状态表示 -----|
| | 属性 : 集合中所有可行方案价值最大的值 max
|
|
|
f[i][j]
|
|
|
|
|------------状态计算 : 根据集合划分，将一个大集合划分为若干个子集,
设我们要求解f(i,j), 然后来尝试将其分为更小的集合
Dp问题分析出状态表示之后, 最重要的就是推出状态计算,即状态转移方程. 这里如果直接来求f[i][j]的话,显然没什么思路
但它一定是这些可行方案中的一种, 故我们需要进行划分子集的操作, 即来将这堆方案进行分类, 也叫划分子集，那么我们划分的
标准是什么呢? 由于我们的此时的集合的方案都是从 1 ~ i 种物品种选, 故我们将集合分为两个子集, (1)不选择第i个物品, (2)
选择第i个物品. 划分子集的原则是不重不漏, 划分依据为第i个物品是否被选取, 显然是一种不重不漏的方案。
|----------------(1) 不选择第 i 种物品, 由于我们是要求最大价值, 此时所容纳的体积为j, 但不选第i个物品
| 问题转变为了从1 ~ (i - 1)个物品中选, 且所选总体积不超过j的方案的最大价值,这不就
| 是f[i - 1][j], 故f[i][j]的一个子集可以由 f[i - 1][j] 转移过来
f(i,j)
|
|----------------(2) 选择第 i 种物品, 此时由于选择了第i个物品, 故此时背包的体积为 j - v[i], 即减去
这件物品的体积, 要想得到最大的价值, 由于选择了第i件物品, 故只剩下的物品只能在
1 ~ (i - 1)中选, 且此时背包的体积为 j - v[i]. 那么问题就变为了在 1 ~ (i - 1)
件物品中选, 且体积不超过 j - v[i]的方案的最大价值, 这个就是f[i - 1][j - v[i]]
故f[i][j]的另一个子集表示为 f[i - 1][j - v[i]] + w[i],由于选择了第i个物品,故
总价值加上 w[i].
故f[i][j]的值为(1)和(2)两个子集中取一个最大值,但要注意的是(2)子集存在是有条件的,即此时的背包体积j >= v[i]，但(1)这
个子集必定是存在的。故f[i][j] 最后的状态计算表示为
f[i][j] = f[i - 1][j];
if(j >= v[i])
f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i])
可以看到两种情况下, f[i][j] 都是可以由之前计算过的状态转移得到, 故这种递推方式下可以一步一步地利用上一步计算的状态
将我们这一步要计算的状态计算出来。
具体模板题目链接: Acwing_01背包问题
代码实现
C++版本
#include<iostream>
using namespace std;
int v[1010], w[1010];
int f[1010][1010];
auto main() -> int
{
ios::sync_with_stdio(false);
int N, V; cin >> N >> V; // N件物品, 背包最大容量为V
for(int i = 1; i <= N; ++i) cin >> v[i] >> w[i]; // 输入第 i 件物品的体积 和 价值 (体积为整数 > 0)
for(int i = 1; i <= N; ++i) // 先枚举物品
for(int j = 0; j <= V; ++j) // 再枚举体积 体积从0 开始，然后 ++, 最大不超过V
{
f[i][j] = f[i - 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[N][V] << endl; // 最后输出我们的方案, 即从1 ~ N种物品种选, 所选物品体积不超过V的最大价值
return 0;
}
Python3版本
v, w = [0] * 1010, [0] * 1010
f = [[0] * 1010 for i in range(1010)]
N, V = map(int, input().split())
for i in range(1, N + 1):
v[i], w[i] = map(int, input().split())
for i in range(1, N + 1):
for j in range(1, V + 1):
f[i][j] = f[i - 1][j]
if(j >= v[i]): f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])
print(f[N][V])
优化的思路
我们看之前的代码的时候，其状态转移方程为
for(int i = 1; i <= N; ++i) // 先枚举物品
for(int j = 0; j <= V; ++j) // 再枚举体积 体积从0 开始，然后 ++, 最大不超过V
{
f[i][j] = f[i - 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
我们可以看到这两种情况中, 都是由 f[i - 1]这一层转移过来的,即计算这一层时只需用到上一层的计算状态,不会用到f[i-2],f[i - 3]的状态, 故这就有空间优化的思路, 我们可以直接砍掉f[1010][1010]的一维 --> f[1010]; 然后来对我们上面的代码作一个等价变形: 首先将原本代码f的第一维直接去掉
for(int i = 1; i <= N; ++i) // 先枚举物品
for(int j = 0; j <= V; ++j) // 再枚举体积 体积从0 开始，然后 ++, 最大不超过V
{
//f[i][j] = f[i - 1][j];
f[j] = f[j]
if(j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);
}
观察上式 第5行是一个恒等式故可以直接去掉
然后观察这一句 f[j] = max(f[j], f[j - v[i]] + w[i]); 跟原本的等价吗 ?
由于 j - v[i] < j 故 f[j - v[i]] 先于 f[j] 被计算出来, 故其实它是原本本层, 并不是上一层的。
故这里的话我们要作第二层循环做一个变化,即我们原本是从小到大枚举体积, 我们这里变为从大到小枚举体积即可.
因为这样的话 f[j] 就会比 f[j - v[i]] 先计算, 这样f[j - v[i]] 就是上一层没被计算的数值的了.
故第二层for改为:
for(int j = V; j >= v[i]; --j)
这里的终止条件改为 j >= V[i], 因为根据if(j >= v[i])知道, 若j < v[i]就不会进行状态转移了.
故最后经过空间优化后的代码为:
空间优化后的C++代码
#include<iostream>
using namespace std;
int v[1010], w[1010];
int f[1010];
auto main() -> int
{
ios::sync_with_stdio(false);
int N, V; cin >> N >> V;
for(int i = 1; i <= N; ++i) cin >> v[i] >> w[i];
for(int i = 1; i <= N; ++i)
for(int j = V; j >= v[i]; --j)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[V] << endl;
return 0;
}
改进的python版本
v, w = [0] * 1010, [0] * 1010
f = [0] * 1010
N, V = map(int, input().split())
for i in range(1, N + 1):
v[i], w[i] = map(int, input().split())
for i in range(1, N + 1):
for j in range(V, v[i] - 1, -1):
f[j] = max(f[j], f[j - v[i]] + w[i])
print(f[V])
相关题目
Leetcode 494.目标和
题目链接: 494.目标和
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
样例
示例1:
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例2:
输入：nums = [1], target = 1
输出：1
提示:
- 1 ≤ n u m s . l e n g t h ≤ 20 1 \le nums.length \le 20 1≤nums.length≤20
- 0 ≤ n u m s [ i ] ≤ 1000 0 \le nums[i] \le 1000 0≤nums[i]≤1000
- 0 ≤ s u m ( n u m s [ i ] ) ≤ 1000 0 \le sum(nums[i]) \le 1000 0≤sum(nums[i])≤1000
- − 1000 ≤ t a r g e t ≤ 1000 -1000 \le target \le 1000 −1000≤target≤1000
算法1 (DP动态规划)
思路分析
经典的01背包问题, 对于01背包问题来说每一件物品是选或者不选，这里对于每一个数字来说，是前面是 ”+“ 还是 “-”, 然后不超过背包的体积容量这个条件变为了刚好装满背包的体积,即题目中的使得运算结果为target。即这里的target就是容量.
闫氏DP分析法
| 集合 ： 从1 ~ i 个数字添加+/-, 使得前i个数字的运算结果为j的方案
|------------状态表示 -----|
| | 属性 : 可行的方案的个数
|
|
|
f[i][j]
|
|
|
|
|------------状态计算 : 由于每个数前面只能填 + / -,故这里集合的划分我们以最后一个数,即第i个数的前面
是+ 还是 -, 将集合分为两类.
(1) 第i个数前面是 "+" 号的子集表示:
由于是最后一项前面是"+",即表达式的结果最后是加上 nums[i]这一项才等于 target值, 故前面1 ~ i - 1应该
满足其表达式的结果为 target - nums[i]; 那这样的话第i个数前面填"+"号的总方案数就是前 i - 1 个数表达式
的结果为target - nums[i], 故子集表示为 f[i - 1][target - nums[i]]
(2) 同理第i个数前面是 "-" 号的子集表示为: f[i - 1][target + nums[i]]
故综合,f[i][j]的结果即为这两个子集的总方案数
f[i][j] = f[i - 1][target - nums[i]] + f[i - 1][target + nums[i]]
但并不是总是存在上面这个关系, 因为看提示中 0 <= sum(nums[i]) <= 1000
target + nums[i] > 1000 时是没有意义的,因为根本不可能达到,同理 < 1000时也是没有意义的。
C++ 代码
class Solution
{
public:
int f[30][2010];
int findTargetSumWays(vector<int>& nums, int target)
{
memset(f, 0, sizeof f);
int offset = 1000, n = nums.size(); // 由于target可能为负,故第二维加上一个偏移量是其为正
f[0][offset] = 1;
for(int i = 1; i <= n; ++i)
for(int j = -1000; j <= 1000; ++j) // 注意这里不是从0开始的,因为要考虑负数的情况
{
if(j - nums[i - 1] >= -1000) f[i][j + offset] += f[i - 1][j - nums[i - 1] + offset];
if(j + nums[i - 1] <= 1000) f[i][j + offset] += f[i - 1][j + nums[i - 1] + offset];
}
return f[n][target + offset];
}
};
// 空间优化版本
class Solution
{
public:
int findTargetSumWays(vector<int>& nums, int target)
{
int n = nums.size();
int m[2][4200]; memset(m, 0, sizeof m);
m[0][nums[0] + 2000]++;
m[0][-nums[0] + 2000]++;
for(int i = 2; i <= n; ++i)
for(int j = -1000; j <= 1000; ++j)
m[(i + 1) % 2][j + 2000] = m[i % 2][j - nums[i - 1] + 2000] + m[i % 2][j + nums[i - 1] + 2000];
return m[(n + 1) % 2][target + 2000];
}
};
时间复杂度 O ( n m ) O(nm) O(nm)
Leetcode 474. 一和零
题目链接: 474. 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
样例
示例1:
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1，大于 n 的值 3
示例2:
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
提示:
- 1 ≤ s t r s . l e n g t h ≤ 600 1 \le strs.length \le 600 1≤strs.length≤600
- 1 ≤ s t r s [ i ] . l e n g t h ≤ 100 1 \le strs[i].length \le 100 1≤strs[i].length≤100
- s t r s [ i ] 仅 由 0 和 1 组 成 strs[i] 仅由 0 和 1 组成 strs[i]仅由0和1组成
- 1 ≤ m , n ≤ 100 1 \le m, n \le 100 1≤m,n≤100
算法1 (DP动态规划)
思路分析
每个字符串只能选一次,且所选的所有字符串中, 所有0的个数的总和不超过m, 1的个数的总和不超过n, 问在这种情况下所能选择的最多的字符串的个数, 故这里的价值每一个字符串都是1. 这不过这里相比于经典的01背包问题有两个限制, 即这是一个二维的背包问题。这里就不用闫氏DP分析法展开, 因为跟之前的背包问题一样， f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] 表示的是 从 1 ~ i 个字符串中选, 且0的个数不超过j, 1的个数不超过k的情况下的所能选的最多的字符串个数。由于这里每一个字符串的0的个数和1的个数并没有直接给出, 故当遍历到第i个字符串的时候我们还要处理出这个字符串0的个数和1的个数。
C++ 代码
class Solution
{
public:
int f[610][110][110];
int findMaxForm(vector<string>& strs, int m, int n)
{
memset(f, 0, sizeof f);
int num = strs.size();
for(int i = 1; i <= num; ++i)
{
int zero = count(strs[i - 1].begin(), strs[i - 1].end(), '0');
int one = strs[i - 1].size() - zero; // 处理得到当前遍历字符串0的个数和1的个数
for(int j = 0; j <= m; ++j)
for(int k = 0; k <= n; ++k)
{
f[i][j][k] = f[i - 1][j][k]; // 第i个字符串不选的情况下
if(j >= zero && k >= one)
f[i][j][k] = max(f[i][j][k], f[i - 1][j - zero][k - one] + 1);
}
}
return f[num][m][n];
}
};
// 空间优化
class Solution
{
public:
int f[110][110];
int findMaxForm(vector<string>& strs, int m, int n)
{
memset(f, 0, sizeof f);
int num = strs.size();
for(int i = 1; i <= num; ++i)
{
int zero = count(strs[i - 1].begin(), strs[i - 1].end(), '0');
int one = strs[i - 1].size() - zero;
for(int j = m; j >= zero; --j)
for(int k = n; k >= one; --k)
f[j][k] = max(f[j][k], f[j - zero][k - one] + 1);
}
return f[m][n];
}
};
时间复杂度 O ( l e n g t h × n × m ) O(length \times n \times m) O(length×n×m)
Leetcode 1049.最后一块石头的重量
题目链接: Leetcode 1049. 最后一块石头的重量
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
-
如果 x == y，那么两块石头都会被完全粉碎；
-
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
样例
示例1:
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
示例2:
输入：stones = [31,26,33,21,40]
输出：5
示例3:
输入：stones = [1,2]
输出：1
提示:
-
1 ≤ s t o n e s . l e n g t h ≤ 30 1 \le stones.length \le 30 1≤stones.length≤30
-
1 ≤ s t o n e s [ i ] ≤ 100 1 \le stones[i] \le 100 1≤stones[i]≤100
算法1 (DP动态规划)
思路分析
题目中给出的条件是从一堆石头中任意选出两块石头进行粉碎, 然后问的是最后剩下的石头的最小的可能重量. 假如我们里面有两块石头a, b, 其中重量上 a ≥ b a \ge b a≥b , 故得到的新的石头重量为 a - b, 故每次从石头堆中选出两块石头进行粉碎的时候, 从表面上看是这两块石头消失, 然后增加一块石头其重量为这两块石头的差值, 上面的例子就是石头堆少了重量为a, 和重量为b的两块石头然后多了一块 a - b 的石头, 然后这块新石头后面可能跟一块重量为c的石头进行粉碎, 即后面可能得到的石头的重量为: c - (a - b) = c - a + b 或者 a - b - c; 故其实实际上a, b 这a, b 这两块石头并没有消失, 只不过换了一种存在的方式. 故最后的最后一块石头的重量的表达式必然是这种形式 + / − n 1 + / − n 2 + / − n 3 + / − n 4 + / − n 5..... +/- n1 +/- n2 +/- n3 +/- n4 +/- n5 ..... +/−n1+/−n2+/−n3+/−n4+/−n5.....这种形式, 即我们可以改写为 ( n a + n b + n c + n d + . . . . . ) − ( n e + n f + n g + . . . . ) (n_a + n_b + n_c + n_d + .....) - (n_e + n_f + n_g + ....) (na+nb+nc+nd+.....)−(ne+nf+ng+....) 的这种形式, 那么问题要求的最后一块石头最小的可能重量就变成了将这一堆石头划分为两堆, 然后这两堆的差值最小是多少. 设初始状态这一堆石头的总重量为 sum, 那么分为两堆的话，要想两堆的差值最小, 那么其中一堆的重量之和应该尽可能往 sum / 2 上靠, 那么问题就变成了在 1 ~ i 块石头中选, 在重量之和不超过sum / 2 的情况下, 所选的石头总重量最大是多少. 那么这就转化为了经典的01背包问题。
C++ 代码
class Solution
{
public:
int lastStoneWeightII(vector<int>& stones)
{
int n = stones.size();
if(n == 1) return stones[0];
if(n == 2) return abs(stones[0] - stones[1]);
int sum = accumulate(stones.begin(), stones.end(), 0); // 计算石头的总和
int target = sum / 2; // target值
int f[30010]; memset(f, 0, sizeof f); // 这里直接优化掉一维来写
for(int i = 0; i < n; ++i)
for(int j = target; j >= stones[i]; --j)
f[j] = max(f[j], f[j - stones[i]] + stones[i]); // 01背包问题的写法
return sum - 2 * f[target]; // 最后返回两堆的差值 (sum - f[target]) - f[target]
}
};
时间复杂度 O ( n 2 ) O(n^2) O(n2)
Leetcode 879.盈利计划
题目链接: 879. 盈利计划
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
有多少种计划可以选择？因为答案很大，所以 返回结果模 1 0 9 + 7 10^9 + 7 109+7 的值。
样例
示例1:
输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。
示例2:
输入：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) 。
提示:
-
1 ≤ n ≤ 100 1 \le n \le 100 1≤n≤100
-
0 ≤ m i n P r o f i t ≤ 100 0 \le minProfit \le 100 0≤minProfit≤100
-
1 ≤ g r o u p . l e n g t h ≤ 100 1 \le group.length \le 100 1≤group.length≤100
-
1 ≤ g r o u p [ i ] ≤ 100 1 \le group[i] \le 100 1≤group[i]≤100
-
p r o f i t . l e n g t h ≤ g r o u p . l e n g t h profit.length \le group.length profit.length≤group.length
-
0 ≤ p r o f i t [ i ] ≤ 100 0 \le profit[i] \le 100 0≤profit[i]≤100
算法1 (DP动态规划)
思路分析
题目的大意是是有1 ~ i个任务，每一个任务有两种属性, 一种是所需要的人数, 一种是该任务能产生的收益. 而我们现在有n名员工, 且需要得到总收益应该大于等于 minProfit, 即我们要求的答案为要在1 ~ i 个任务中选, 在用到的人数不超过n的情况且所选的所有任务产生的收益不小于 minProfit 的方案数的个数最多为多少。 因为每一个任务只有可能是选还是不选， 故这就是一个01背包问题, 而且因为有两种属性, 这是一个二维的背包问题. 故 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] 的含义为在 1 ~ i 个任务中选， 且所选的任务中其所有需要的人数总和不超过j, 且所选的所有任务其利润总和大于等于k的方案数。
状态计算:
f[i][j][k] 子集的划分, 同样以第i个任务是否被选 进而划分为两个子集:
|----------------(1) 不选择第 i 个任务, 这就变成了在 1 ~ i - 1个任务中选, 且且所选的任务中其所有
| 需要的人数总和不超过j, 且所选的所有任务其利润总和大于等于k的方案数。即该子集
| 表示为 f[i - 1][j][k]
|
f(i,j,k)
|
|
|----------------(2) 选择第 i 个任务, 此时由于选择了第i个任务, 此时能用的人的总数为j - group[i],
现在需要满足的利润总和应该大于等于 k - profit[i]. 故为了使得选了第i个任务的
方案数最多，应该满足的是在1 ~ i - 1个任务中选, 任务所需要用到的人 <= j - group[i]
且产生的利润 >= k - profit[i]的方案数最多, 即表示为
f[i - 1][j - group[i]][k - profit[i]]
由于f[i][j][k] 的值表示的是满足条件的方案数，故其值为这两个子集相加:
f[i][j][k] = f[i - 1][j][k] + f[i - 1][j - group[i]][k - profit[i]]
但这里要注意一下上面的形式并不是总是成立, 对于j - group[i] < 0 时是无意义的, 因为要求人不大于 0
显然不存在,故对于这种情况直接pass, 但对于k - profit[i] < 0 是有意义的, 因为其含义是要求利润大于一个负数
显然我们所有 0 <= profit[i] <= 100, 故对于k - profit[i] < 0的情况直接作为0处理即可, 这样就不用加上
偏移量.
* 同样计算这一层的状态的时候也只用到了上一层的状态, 故可以优化掉一维的空间
C++ 代码
class Solution
{
public:
static constexpr int N = 110;
int f[N][N];
int MOD = 1e+9 + 7;
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit)
{
memset(f, 0, sizeof f);
// 预处理,f[0][0][0],对于利润 > 0的方案的一个方案就是直接不选, 而f[0][x][0]又包含了f[0][0][0]这种情况
for(int i = 0; i <= n; ++i) f[i][0] = 1;
for(int i = 0; i < group.size(); ++i)
{
int g = group[i], m = profit[i];
for(int j = n; j >= g; --j)
for(int k = minProfit; k >=0; --k)
f[j][k] = (f[j][k] + f[j - g][max(0, k - m)]) % MOD; // 状态转移
}
return f[n][minProfit];
}
};