关于网站的毕业设计小程序页面设计报价

关于网站的毕业设计,小程序页面设计报价,做网站的公司经营范围,装修效果图网站推荐代码随想录算法训练营第三十二天任务完全背包理论卡码网52. 携带研究材料518.零钱兑换II377. 组合总和 Ⅳ卡码网57. 爬楼梯完全背包理论 有N件物品和⼀个最多能背重量为W的背包。第 i 件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品都有无限个#xff…代码随想录算法训练营第三十二天任务完全背包理论卡码网52. 携带研究材料518.零钱兑换II377. 组合总和 Ⅳ卡码网57. 爬楼梯完全背包理论有N件物品和⼀个最多能背重量为W的背包。第 i 件物品的重量是weight[i]得到的价值是value[i] 。每件物品都有无限个也就是可以放⼊背包多次求解将哪些物品装入背包里物品价值总和最大。完全背包和01背包问题唯一不同的地方就是每种物品有无限件。eg:背包最大重量为4。物品为每件商品都有无限个问背包能背的物品最大价值是多少确定dp数组的含义dp[i][j] 表示背包容量为j的背包能背[0~i]中物品的最大价值。确定递推公式。不装当前物品 i dp[i][j] dp[i - 1][j]装当前物品 i : dp[i][i] dp[i][j - weight[i]] value[i]因为每件商品有无限个所以不是dp[i - 1][i - weight[i]], 而是dp[i][j - weight[i]] 之前这个物品装入过但因为有空间还可以再装入。dp[i][j] max(dp[i - 1][j], dp[i][j - weight[i]] value[i])初始化dp[i][0]: 背包容量为0什么物品都装不下所以为0。因为dp[i][j] 由上方和左方推倒而来所以dp[0][j] 需要初始化。只要容量能装下物品0就可劲装j weight[0]: dp[0][j] dp[0][j - weight[0]] value[0];确定遍历顺序完全背包的物品是可以添加多次的所以要从小到大去遍历// 先遍历物品再遍历背包for(inti0;iweight.size();i)// 遍历物品{for(intjweight[i];jbagWeight;j)// 遍历背包容量{dp[i][j]max(dp[i-1][j],dp[i][j-weight[i]]value[i]);}}// 先遍历背包再遍历物品for(intj0;jbagWeight;j)// 遍历背包容量{for(inti0;iweight.size();i)// 遍历物品{if(j-weight[i]0)dp[i][j]max(dp[i-1][j],dp[i][j-weight[i]]value[i]);}}举例推导dp数组纯完全背包的面试题要求先用二维dp数组实现然后再用一维dp数组实现最后在问两个for循环的先后是否可以颠倒为什么如果求组合数就是外层for循环遍历物品内层for遍历背包。如果求排列数就是外层for遍历背包内层for循环遍历物品。 377.组合总和IV卡码网52. 携带研究材料题目链接卡码网52. 携带研究材料#includeiostream#includevectorusingnamespacestd;intmain(){intitem,totalWeight;cinitemtotalWeight;vectorintweight(item,0);vectorintvalue(item,0);for(inti0;iitem;i){cinweight[i];cinvalue[i];}// dp[i][j] [0~i]类物品中装入容量为j的行李中的最大价值vectorvectorintdp(item,vectorint(totalWeight1,0));// 初始化第一行for(intjweight[0];jtotalWeight;j){dp[0][j]dp[0][j-weight[0]]value[0];}for(inti1;iitem;i){// 物品for(intj0;jtotalWeight;j){// 容量if(jweight[i])dp[i][j]dp[i-1][j];else{dp[i][j]max(dp[i-1][j],dp[i][j-weight[i]]value[i]);}}}coutdp[item-1][totalWeight]endl;return0;}518.零钱兑换II题目链接518.零钱兑换II这道题很契合完全背包问题。coins数组相当于物品amount相当于背包。只不过这里的dp[i][j] 不表示价值而是表示凑成这个amount有多少种方式。多少和494. 目标和有点相似。目标和是01背包问题这道题是完全背包问题。确定dp[i][j]的含义dp[i][j] 表示 coins中下标为[0~i]的数凑成金额 j 的组合数。确定递推公式不包含当前下标为 i 的coindp[i][j] dp[i - 1][j]包含当前下标为 i 的coin, dp[i][j] dp[i][j - coins[i]]dp[i][j] dp[i - 1][j] dp[i][j - coins[i]]初始化凑成金额为0的组合数相当于什么都不选算一种方式即dp[i][0] 1;当 j % coins[0] 0, dp[0][j] 1;遍历顺序从小到大遍历举例推到dp数组classSolution{public:intchange(intamount,vectorintcoins){// dp[i][j] 表示 coins中下标为[0~i]的数凑成金额 j 的组合数。intncoins.size();vectorvectoruint64_tdp(n,vectoruint64_t(amount1,0));// 小面值硬币组合出大金额组合方式爆炸式增长可能超出64 位整数上限。// 初始化for(intj0;jamount;j){if(j%coins[0]0)dp[0][j]1;}for(inti1;in;i){dp[i][0]1;for(intj1;jamount;j){if(jcoins[i])dp[i][j]dp[i-1][j];elsedp[i][j]dp[i-1][j]dp[i][j-coins[i]];}}returndp[n-1][amount];}};377. 组合总和 Ⅳ题目链接377. 组合总和 Ⅳ这道题和518.零钱兑换II相似不同之处在于这道题把顺序不同的序列视为不同的组合。确定dp[i][j]的含义dp[i][j] 表示 使用下标为 0~i 数字凑成总和为 j 的排列数量。确定递推公式不包含当前下标为 i 的numdp[i][j] dp[i - 1][j]包含当前下标为 i 的coin, dp[i][j] dp[n][j - nums[i]]dp[i][j] dp[i - 1][j] dp[n][j - nums[i]]为什么不是 dp[i][j - nums[i]]当使用 nums[i] 时剩余和 j - nums[i] 的凑法必须允许再次使用所有数字才能体现排列。其中 n 是数组总长度dp[n][…] 表示所有数字都可用的状态。初始化凑成为0的组合数相当于什么都不选算一种方式即dp[i][0] 1;遍历顺序从小到大遍历举例推到dp数组classSolution{public:intcombinationSum4(vectorintnums,inttarget){// dp[i][j] 表示 nums中下标为[0~i]的数组合成和为 target 的组合排列数。intnnums.size();vectorvectoruint64_tdp(n1,vectoruint64_t(target1,0));// 初始化for(inti0;in;i){dp[i][0]1;// 凑成 0 都有 1 种方法}for(intj1;jtarget;j){for(inti1;in;i){if(jnums[i-1])dp[i][j]dp[i-1][j];elsedp[i][j]dp[i-1][j]dp[n][j-nums[i-1]];}}returndp[n][target];}};卡码网57. 爬楼梯题目链接卡码网57. 爬楼梯思路同上题#includeiostream#includevectorusingnamespacestd;intmain(){intn,m;cinnm;// n 相当于 背包容量 1 ~ m 相当于物品可以重复装vectorvectorintdp(m1,vectorint(n1,0));// 初始化for(inti0;im;i){dp[i][0]1;}for(intj1;jn;j){for(inti1;im;i){if(ji)dp[i][j]dp[i-1][j];elsedp[i][j]dp[i-1][j]dp[m][j-i];}}coutdp[m][n]endl;return0;}