动态规划之【背包DP】第16课：分组背包DP应用案例实践3

动态规划之【背包DP】第16课分组背包DP应用案例实践3题目描述总公司拥有高效设备M MM台准备分给下属的N NN个分公司。各分公司若获得这些设备可以为国家提供一定的盈利。问如何分配这M MM台设备才能使国家得到的盈利最大求出最大盈利值。其中M ≤ 15 M \le 15M≤15N ≤ 10 N \le 10N≤10。分配原则每个公司有权获得任意数目的设备但总台数不超过设备数M MM。输入格式第一行有两个数第一个数是分公司数N NN第二个数是设备台数M MM。接下来是一个N × M N \times MN×M的矩阵表明了第i ii个公司分配j jj台机器的盈利。最大盈利值相同时要求编号小的公司分得设备尽可能少。输出格式第一行为最大盈利值。接下来N NN行为第i ii分公司分x xx台。输入输出样例 1输入 13 3 30 40 50 20 30 50 20 25 30输出 170 1 1 2 1 3 1思路分析这是一个典型的资源分配问题分组背包 / 线性DP有N NN个公司组和M MM台设备总容量每个公司i ii分配j jj台设备可获得盈利a i , j a_{i,j}ai,j​。要求总盈利最大且当多个方案盈利相同时优先使编号小的公司分得设备数尽量少。DP状态定义令d p [ i ] [ j ] dp[i][j]dp[i][j]表示前i ii个公司总共分配j jj台设备能获得的最大盈利。用p r e [ i ] [ j ] pre[i][j]pre[i][j]记录在d p [ i ] [ j ] dp[i][j]dp[i][j]达到最优时第i ii个公司分配的设备台数即转移时选择的k kk。转移方程对于第i ii个公司它可以分配k kk台设备0 ≤ k ≤ j 0 \le k \le j0≤k≤j则前i − 1 i-1i−1个公司分配j − k j-kj−k台d p [ i ] [ j ] max ⁡ 0 ≤ k ≤ j ( d p [ i − 1 ] [ j − k ] a [ i ] [ k ] ) dp[i][j] \max_{0\le k\le j} \big( dp[i-1][j-k] a[i][k] \big)dp[i][j]0≤k≤jmax​(dp[i−1][j−k]a[i][k])其中a [ i ] [ 0 ] 0 a[i][0]0a[i][0]0分配0台盈利为0。字典序最小的处理题目要求盈利相同时编号小的公司分得设备尽可能少。在DP过程中若多个k kk使d p [ i ] [ j ] dp[i][j]dp[i][j]达到相同最大值我们应选择最大的k kk。因为较大的k kk意味着当前公司编号较大拿走更多设备留给前面公司编号较小的设备更少从而前面公司分配数更小。记录路径时从d p [ N ] [ M ] dp[N][M]dp[N][M]回溯即可得到每个公司的分配数。复杂度N ≤ 10 , M ≤ 15 N \le 10,\ M \le 15N≤10,M≤15DP 复杂度O ( N ⋅ M 2 ) ≤ 2250 O(N \cdot M^2) \le 2250O(N⋅M2)≤2250完全可行。代码实现#includebits/stdc.husingnamespacestd;intn,m;// n个公司m台设备inta[11][16];// a[i][j]: 公司i分配j台的盈利 (j0..m)intdp[11][16];// dp[i][j]: 前i个公司用j台的最大盈利intpre[11][16];// pre[i][j]: 最优时第i个公司分配的台数intans[11];// 存储最终每个公司的分配数intmain(){// 读入cinnm;for(inti1;in;i){for(intj1;jm;j)cina[i][j];}// 初始化 dp 为极小值memset(dp,0x80,sizeof(dp));// 0x80 -2139062144dp[0][0]0;// 前0个公司0台设备盈利0// DP过程for(inti1;in;i){// 枚举公司for(intj0;jm;j){// 枚举总设备数for(intk0;kj;k){// 当前公司分k台intvaldp[i-1][j-k]a[i][k];if(valdp[i][j]){dp[i][j]val;pre[i][j]k;// 记录最优时的分配}elseif(valdp[i][j]){// 盈利相同时让当前公司多拿使前面公司少拿if(kpre[i][j])pre[i][j]k;}}}}// 输出最大盈利值coutdp[n][m]endl;// 回溯路径得到每个公司的分配数intremm;// 剩余未分配设备数for(intin;i1;--i){ans[i]pre[i][rem];rem-ans[i];}// 按公司编号从小到大输出分配数for(inti1;in;i)couti ans[i]endl;return0;}功能分析输入处理读取N , M N,MN,M以及N × M N\times MN×M的盈利矩阵动态规划求解采用二维DP状态dp[i][j]记录前i ii个公司用j jj台设备的最大盈利。转移时枚举当前公司分配k kk台取最大值。利用pre数组记录最优转移时的k kk并在盈利相同时选择较大的k kk以保证字典序最小。路径回溯从dp[N][M]反向推出每个公司的实际分配台数。输出第一行输出最大盈利值随后N NN行按公司编号输出分配台数。完整系列资料请查看专栏《csp信奥赛C动态规划》https://blog.csdn.net/weixin_66461496/category_13096895.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}