【题目来源】洛谷P17012 [GESP202606 六级] 条形蛋糕 - 洛谷【题目描述】寒假到了小杨同学打算找一份兼职顺便体验一下打工人的生活。小杨同学给一家蛋糕店发送了一份自己的简历希望可以在寒假来这里帮忙。店长最近正好遇到了一个难题店里每天会做一条长条蛋糕但是不同长度的蛋糕块卖出的价格不同应该怎么分才能卖得最多呢有趣的是店长曾经学习过计算机专业。他最近对动态规划算法很感兴趣于是打算用这个问题考一考小杨同学问题如下给定一条长度为n nn的长条蛋糕和一个价格表该价格表表示长度为i ii(i 1 , 2 , … , n i 1, 2, \dots, ni1,2,…,n) 的蛋糕块的价格为p i p_ipi​。求蛋糕的分割方案使得总销售价格最大注意蛋糕块的长度必须为整数。【输入】第一行一个正整数n nn(1 ≤ n ≤ 10 3 1 \le n \le 10^31≤n≤103)表示长条蛋糕的总长度。第二行n nn个正整数p 1 , p 2 , … , p n p_1, p_2, \dots, p_np1​,p2​,…,pn​(1 ≤ p i ≤ 10 5 1 \le p_i \le 10^51≤pi​≤105)表示不同长度蛋糕块的价格。【输出】一行一个正整数表示最大总销售价格。【输入样例】4 1 5 8 9【输出样例】10【核心思想】问题分析给定长度为n nn的蛋糕和价格表p 1 , p 2 , … , p n p_1, p_2, \ldots, p_np1​,p2​,…,pn​要求将蛋糕分割为若干整数长度的块使得总价格最大。这是一个完全背包问题核心在于每种长度的蛋糕块可以无限选取在总长度限制下最大化总价值。算法选择动态规划完全背包设d p [ j ] dp[j]dp[j]表示总长度为j jj时的最大价格每种长度i ii的物品可以无限次选取状态转移d p [ j ] max ⁡ ( d p [ j ] , d p [ j − i ] p i ) dp[j] \max(dp[j], dp[j-i] p_i)dp[j]max(dp[j],dp[j−i]pi​)表示在总长度j jj中选择一块长度为i ii的蛋糕关键步骤初始化d p [ 0 ] 0 dp[0] 0dp[0]0其余d p [ j ] 0 dp[j] 0dp[j]0正整数价格保证非负初始化为0 00即可外层枚举物品i ii从1 11到n nn遍历每种可选的蛋糕长度内层枚举容量j jj从i ii到n nn正序遍历允许同一物品重复选取状态转移d p [ j ] ← max ⁡ ( d p [ j ] , d p [ j − i ] p i ) dp[j] \leftarrow \max(dp[j], dp[j-i] p_i)dp[j]←max(dp[j],dp[j−i]pi​)输出结果d p [ n ] dp[n]dp[n]时间/空间复杂度时间复杂度O ( n 2 ) O(n^2)O(n2)外层n nn种长度内层最多n nn的容量空间复杂度O ( n ) O(n)O(n)一维d p dpdp数组即可二维数组可优化为一维完全背包的核心思想无限选取特性与0 / 1 0/10/1背包不同完全背包中每种物品可以选取任意多次因此内层循环正序遍历j jj从i ii到n nn使得d p [ j − i ] dp[j-i]dp[j−i]可能已经包含了当前物品i ii实现无限选取最优子结构总长度为j jj的最优解可以由总长度为j − i j-ij−i的最优解加上一块长度为i ii的蛋糕得到即d p [ j ] max ⁡ 1 ≤ i ≤ j { d p [ j − i ] p i } dp[j] \max_{1 \leq i \leq j}\{dp[j-i] p_i\}dp[j]max1≤i≤j​{dp[j−i]pi​}空间优化一维数组即可满足需求d p [ j ] dp[j]dp[j]在更新时引用的是同一轮已更新的d p [ j − i ] dp[j-i]dp[j−i]隐含了无限选取的语义与0 / 1 0/10/1背包的区别0 / 1 0/10/1背包内层逆序遍历防止重复选取完全背包正序遍历允许重复选取适用于物品无限供应、在容量限制下最大化价值的资源分配类问题【算法标签】#普及- #完全背包【代码详解】#includebits/stdc.husingnamespacestd;constintN1005;// 常量最大蛋糕长度intn;// n: 蛋糕总长度intp[N];// p[i]: 长度为 i 的蛋糕块的价格intdp[N][N];// dp[i][j]: 考虑前 i 种长度总长度为 j 时的最大价格intmain(){cinn;// 读入蛋糕总长度for(inti1;in;i)// 读入各长度蛋糕块的价格cinp[i];for(inti1;in;i)// 枚举考虑的蛋糕长度种类1到ifor(intj0;jn;j)// 枚举当前总长度{dp[i][j]dp[i-1][j];// 不选长度为 i 的蛋糕块if(ji)// 如果当前总长度可以放下长度为 i 的蛋糕块dp[i][j]max(dp[i][j],dp[i][j-i]p[i]);// 选一块长度为 i 的蛋糕}coutdp[n][n]endl;// 输出最大总销售价格return0;}【运行结果】4 1 5 8 9 10