“恰好装满求最值”背包问题的初始化解析

【问题描述】
不同于普通的没有“恰好装满”约束的背包问题，有时我们会遇到“恰好装满求最值”的背包问题。怎么求解？
其实，也很简单，只需要对普通的没有“恰好装满”约束的背包问题的初始状态进行微调便可。可见，两者在解法上差别不大。

【解决方法】
设 n 为物品种数，V 为背包容量，c[i] 表示容量为 i 的背包能够装的最大价值，vol[i] 为第 i 中物品的容积，val[i] 为第 i 种物品的价值。

现在分情况给出结论：
● 不用恰好装满背包问题的初始化：c[i]=0，其中 0<=i<=V
● 恰好装满求最大值背包问题的初始化：c[0]=0，c[i]=-inf，其中 1<=i<=V
● 恰好装满求最小值背包问题的初始化：c[0]=0，c[i]=inf，其中 1<=i<=V

恰好装满求最小值背包问题的初始化实例可参考 HDU 1114 - Piggy-Bank 的解法：
https://blog.csdn.net/hnjzsyjyj/article/details/126153528

【知识解析】
初始化的 c[] 数组，事实上就是没有任何物品放入背包时的合法状态。
● 如果背包不用恰好装满，那么任何容量的背包都有一个合法状态“什么也不装” ，此时背包的价值为0。故此类问题初始化为“c[i]=0，其中 0<=i<=V”。

● 如果背包恰好装满求最大值，那么此时只有一个合法状态，即容量为0的背包可以在什么也不装的状态下被 “恰好装满” ，此时背包的价值为0。其他容量的背包在“恰好装满求最大值”的约束下均没有合法的解，属于未定义的状态。且由于要求的是最大值，所以都应该被赋值为 −inf 。故此类问题初始化为“c[0]=0，c[i]=-inf，其中 1<=i<=V”。经过计算，若最终c[V]=-inf，则背包不能恰好装满。

● 如果背包恰好装满求最小值，那么此时只有一个合法状态，即容量为0的背包可以在什么也不装的状态下被 “恰好装满” ，此时背包的价值为0。其他容量的背包在“恰好装满求最小值”的约束下均没有合法的解，属于未定义的状态。且由于要求的是最小值，所以都应该被赋值为 inf 。故此类问题初始化为“c[0]=0，c[i]=inf，其中 1<=i<=V”。经过计算，若最终c[V]=inf，则背包不能恰好装满。

【参考文献】
https://blog.csdn.net/Iseno_V/article/details/100697105
https://blog.csdn.net/m0_52043808/article/details/122815072