信誉好的网站开发,有做网站动态效果软件,网店网页设计培训,观光农业规划设计完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品都有无限个#xff08;也就是可以放入背包多次#xff09;#xff0c;求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同…完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品都有无限个也就是可以放入背包多次求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是每种物品有无限件。
假设背包最大重量为4。物品为
重量价值物品0115物品1320物品2430
每件商品都有无限个。
因此在01背包中我们为了使每件物品只被加入背包一次在内层遍历的时候我们选择了倒序遍历。但是在完全背包中物品的数量是无限的因此可以被添加多次所以要从小到大去遍历。
// 先遍历物品再遍历背包
for(int i 0; i weight.size(); i) { // 遍历物品for(int j weight[i]; j bagWeight ; j) { // 遍历背包容量dp[j] max(dp[j], dp[j - weight[i]] value[i]);}
}
其实还有一个很重要的问题为什么遍历物品在外层循环遍历背包容量在内层循环
01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了一维dp数组的两个for循环先后循序一定是先遍历物品再遍历背包容量。
在完全背包中对于一维dp数组来说其实两个for循环嵌套顺序是无所谓的
因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
遍历物品在外层循环遍历背包容量在内层循环状态如图 遍历背包容量在外层循环遍历物品在内层循环状态如图 看了这两个图大家就会理解完全背包中两个for循环的先后循序都不影响计算dp[j]所需要的值这个值就是下标j之前所对应的dp[j]。 518. 零钱兑换II
题目要求给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount 5, coins [1, 2, 5]输出: 4
解释: 有四种方式可以凑成总金额:
55522152111511111
思路
完全背包问题容量就是amount物品是coins。dp[i]表示组成i大小背包容量的方式数量。同时题目中强调凑成总金额的是组合所以不强调元素之间的顺序。
状态转移方程就是dp[i] dp[j-coins[i]]与昨天遇到的题目相同。
这个递推公式大家应该不陌生了我在讲解01背包题目的时候在这篇494. 目标和 (opens new window)中就讲解了求装满背包有几种方法公式都是dp[j] dp[j - nums[i]];
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount1, 0);dp[0] 1;for (int i 0; i coins.size(); i) {for (int j coins[i]; j amount; j) {dp[j] dp[j - coins[i]];}}return dp[amount];}
};
377. 组合总和 Ⅳ
题目要求给定一个由正整数组成且不存在重复数字的数组找出和为给定目标正整数的组合的个数。
示例:
nums [1, 2, 3]target 4
所有可能的组合为 (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
请注意顺序不同的序列被视作不同的组合。
因此输出为 7。
思路
与上一个题目类似但是本题是排序强调序列的顺序。而上一个题目是组合不强调顺序。
确定遍历顺序
个数可以不限使用说明这是一个完全背包。
得到的集合是排列说明需要考虑元素之间的顺序。
本题要求的是排列那么这个for循环嵌套的顺序可以有说法了。、
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
如果把遍历nums物品放在外循环遍历target的作为内循环的话举一个例子计算dp[4]的时候结果集只有 {1,3} 这样的集合不会有{3,1}这样的集合因为nums遍历放在外层3只能出现在1后面
所以本题遍历顺序最终遍历顺序target背包放在外循环将nums物品放在内循环内循环从前到后遍历。
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(target1, 0);dp[0] 1;for (int i 0; i target; i) { // 遍历背包for (int j 0; j nums.size(); j) { // 遍历物品if (i - nums[j] 0 dp[i] INT_MAX - dp[i - nums[j]]) {dp[i] dp[i - nums[j]];}}}return dp[target];}
};
时间复杂度: O(target * n)其中 n 为 nums 的长度空间复杂度: O(target)
C测试用例有两个数相加超过int的数据所以需要在if里加上dp[i] INT_MAX - dp[i - num]。
Day43总结背包问题的遍历顺序是一门学问01背包物品只能用一次外层是物品内层倒叙是容量完全背包的组合问题不强调顺序物品可以用无限次外层是物品内层是背包容积的正序完全背包的排列问题强调顺序外层是背包容积内层是物品这样大编号的物品也可以出现在前面。
