【动态规划-多重背包】【hard】力扣2585. 获得分数的方法数
考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道，每道题目对应 marksi 分。
返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 109 +7 取余。
注意，同类型题目无法区分。
比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。
示例 1：
输入：target = 6, types = [[6,1],[3,2],[2,3]]
输出：7
解释：要获得 6 分，你可以选择以下七种方法之一：
- 解决 6 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 + 1 = 6
- 解决 4 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 1 + 2 = 6
- 解决 2 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 1 + 2 + 2 = 6
- 解决 3 道第 0 种类型的题目和 1 道第 2 种类型的题目：1 + 1 + 1 + 3 = 6
- 解决 1 道第 0 种类型的题目、1 道第 1 种类型的题目和 1 道第 2 种类型的题目：1 + 2 + 3 = 6
- 解决 3 道第 1 种类型的题目：2 + 2 + 2 = 6
- 解决 2 道第 2 种类型的题目：3 + 3 = 6
示例 2：
输入：target = 5, types = [[50,1],[50,2],[50,5]]
输出：4
解释：要获得 5 分，你可以选择以下四种方法之一：
- 解决 5 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 = 5
- 解决 3 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 2 = 5
- 解决 1 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 2 + 2 = 5
- 解决 1 道第 2 种类型的题目：5
示例 3：
输入：target = 18, types = [[6,1],[3,2],[2,3]]
输出：1
解释：只有回答所有题目才能获得 18 分。
多重背包
class Solution {
public:
int waysToReachTarget(int target, vector<vector<int>>& types) {
int MOD = 1e9 + 7, n = types.size();
vector<int> dp(target+1);
dp[0] = 1;
for(int i = 0; i < n; i++){
for(int j = target; j >= 0; j--){
for(int k = 1; k <= types[i][0]; k++){ //答对这种题的数目
int t = k * types[i][1];
if(t > j) break;
dp[j] = (dp[j] + dp[j-t]) % MOD;
}
}
}
return dp[target];
}
};
多重背包：物品可以重复选，有个数限制。
首先定义一个dp[j]向量，含义是得分为j的时候的方法数。
首先我们定义dp[0]为1。
然后进行三个嵌套for循环，第一层循环的目的是遍历每一种题目类型。
第二层倒序从target向下循环，目的是利用动态规划的方法记录当得分为j的方法数有多少。
第三次是由于题目类型i已经确定，我们定义k为答对这类题目的数量，所以t为这类题目的总得分。
当t如果大于我们的目标分数j的时候，就break，因为这时候dp[j-t]没有意义。
当我们确定某一类题目总得分t的时候，这时候方法数就是dp[j-t]，我们就将之前计算的方法数dp[j]加上dp[j-t]来确定一个新的dp[j]，这新的dp[j]会覆盖旧的dp[j]。
最后我们要求的就是dp[target]当目标分数为target时候的方案数。
原文地址：https://blog.csdn.net/sjsjs11/article/details/142531204
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！