背包九讲最后一讲了,学完这个,然后去做10道左右的背包训练题,再总结一次,这部分就结束了.
背包问题的一些基础问法
给定背包的体积限制,求最大价值
给定背包的体积限制,求最小价值 (max改为min)
给定背包的体积限制,求最大件数 (价值为1)(或贪心)
给定背包的体积限制,求最小件数 (贪心)
给定背包的体积限制,求最多装满多少空间(判断每个体积是否可达)
输出方案
去掉空间优化,变成二维数组
记录每个最优的子问题是由max的哪项推过来的,倒推回去即可得到是否选择某件物品
不用显示记录,倒推时比较两项即可.
输出字典序最小的方案
由于前方物品比后方物品重要,最好将子问题从前i件物品改成后i件物品.
每次倒推时,如果dp[i-1][j]与dp[i-1][j-volu]+valu并列,选择后者.
也可以不改状态表示,而是将所有物品做一个转换x=n+1-x
输出方案时转换回来即可
对某个体积求方案数
转移方程改为sum
初始条件改为dp[0][0]=1
最优方案总数
多增加一个数组mem[i][j]表示dp[i][j]最优时方案数有几种
初始条件mem[0][0]=1
状态转移(在dp转移后):if(dp[i][j]==dp[i-1][j]) mem[i][j]+=dp[i-1][j]
if(dp[i][j]==dp[i-1][j-volu]+valu) mem[i][j]+=mem[i-1][j-volu]
求次优解或第k优解
每个dp状态实际是一个有序数组,代表前k优解
转移时将dp[i-1][j]与dp[i-1][j-volu]+val进行一个merge操作,即可得到dp[i][j]
复杂度O(NVK)
一个正确的状态转移方程实际遍历了所有的解法,只不过忽略了很多非最优解
---------------------
版权声明：本文为CSDN博主「Little_Fall」的原创文章，遵循CC 4.0 by-sa版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_37809890/article/details/79987367