再谈背包问题(涉及思想层面)

背包问题的本质:穷举背包的容量和可供选择的物品(物品),取得最优解,只不过在穷举的过程中,只去考虑可能会取得最优解的地方,不能取得最优解的不考虑。 思想便是用每一个可执行的动作(或者物品)去更新当前的状态 某物品在取或者不取的时候用的是前面的状态 那么如何证明当前的状态一定正确呢? 1.状态的转移正确(状态转移方程正确) 2.之前的状态正确(最优解) 那么为什么背包问题的求解要从最大的背包容量数开始, 那是因为大的背包容量的状态会因小的背包容量最优解的选择而更新,当前只能控制一件物品 打个比方,如排队,后来的人得要排在后面,而排在后面的位置又取决于之前队伍的长度,如果插队了,不就直接乱了阵型了