盐都区城乡建设局网站,阿里云网站备份,html模板库,坪山附近公司做网站建设哪家效益快今天开始《动态规划#xff1a;完全背包》的学习#xff01;
前言#xff1a;
完全背包和01背包的区别在于完全背包里的物品能无限次使用#xff0c;01背包只能用一次。
第一题#xff1a; 简介#xff1a;
本题是纯完全背包的使用。可以看一看和01背包的区别。
代码…今天开始《动态规划完全背包》的学习
前言
完全背包和01背包的区别在于完全背包里的物品能无限次使用01背包只能用一次。
第一题 简介
本题是纯完全背包的使用。可以看一看和01背包的区别。
代码实现
#include iostream
#include vector
using namespace std;
int test_bag(vectorint weight, vectorint value, int bagWeight){vectorint dp(bagWeight 1, 0);for(int i0;iweight.size();i){for(int jweight[i];jbagWeight;j){dp[j] max(dp[j],dp[j - weight[i]] value[i]);}}return dp.back();
}
int main(){vectorint weight;vectorint value;int N,V;cinNV;for(int i0;iN;i){int w;int v;cinwv;weight.push_back(w);value.push_back(v);}couttest_bag(weight,value,V)endl;;return 0;
}
第二题 简介
本题是对完全背包的场景应用题在本题与下一题我们将会了解 如果求组合数无需排序就是外层for循环遍历物品内层for遍历背包。 如果求排列数需要排序就是外层for遍历背包内层for循环遍历物品。 先看本题动态规划五部曲 1.确定dp数组的含义和下标 dp[j]:表示当金额为j时所需硬币有几种组合 2.确定递归公式 dp[j] dp[j-coins[i]]; 3.确定dp数组的初始化 dp[0] 1; 4.遍历数组 5.查看dp数组是否符合要求 代码实现 //dp[j]表示凑成j有几种方式int change(int amount, vectorint coins) {vectorint dp(amount1,0);dp[0] 1;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){dp[j] dp[j-coins[i]];}}return dp.back();}
第三题 简介
大家通过示例可以看出本题对数组元素的顺序有要求所以本题是求排列数。
同样动态规划五部曲
1.确定dp数组的含义及下标 dp[j] 表示数为j时有几种组合方式
2.确定递归公式 dp[j] dp[j-nums[i]];
3.确定dp数组的初始化 dp[0]1;
4.确定遍历的顺序注意本题的遍历顺序 for(int j0;jtarget;j){ // 背包for(int i0;inums.size();i){ //物品if (j - nums[i] 0 dp[j] INT_MAX - dp[j - nums[i]])dp[j] dp[j-nums[i]];}for(int i0;idp.size();i){coutdp[i] ;}coutendl;} 个数可以不限使用说明这是一个完全背包。 得到的集合是排列说明需要考虑元素之间的顺序。 本题要求的是排列那么这个for循环嵌套的顺序可以有说法了。 在上一题中就已经讲过了。 如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品。 如果把遍历nums物品放在外循环遍历target的作为内循环的话举一个例子计算dp[4]的时候结果集只有 {1,3} 这样的集合不会有{3,1}这样的集合因为nums遍历放在外层3只能出现在1后面 所以本题遍历顺序最终遍历顺序target背包放在外循环将nums物品放在内循环内循环从前到后遍历。 5.确定dp数组符合要求 代码实现 int combinationSum4(vectorint nums, int target) {vectorint dp(target1,0);dp[0]1;for(int j0;jtarget;j){ // 背包for(int i0;inums.size();i){ //物品if (j - nums[i] 0 dp[j] INT_MAX - dp[j - nums[i]])dp[j] dp[j-nums[i]];}for(int i0;idp.size();i){coutdp[i] ;}coutendl;}return dp.back();}
总结
今天总体来说比昨天要好今天接受的快并且后两道题了解
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品
之后都可以A出来。继续加油
