背包问题的解决思路

如何让我的背包多放点儿东西

对于一组不同质量不可分割的物品，背包重量确定，如何让背包装的更多呢？首先想到就是把所有的可能都列举一遍，只要包还没超重，看哪个最多呗，嗯，不错的思路，先来实现一下看看情况如何。

用递归的方式穷举所有可能，找出所有组合中在满足条件的情况下，最大的是哪一个。每个阶段会决策一个物品是否放到背包中。每个物品决策（放入或者不放入背包）完之后，背包中的物品的重量会有多种情况，整体的执行过程可以用一棵树来描述

从树可以看出，在递归的过程中存在很多重复计算的状态，如果能使用备忘录的方式将一些计算状态保存，每次进行进行决策之前，从备忘录中查找一下是否有计算好的，如果有就直接返回。

用一个二维数组来保存中间的状态是否计算过，private boolean[][] mem = new boolean[n][w + 1]，数组中的值表示所有可能的状态，这里的状态指的是，决策到第i个品时当前背包重量是否计算过 ， 纵向代表第几个物品，横向代表当前背包重量，背包重量范围为0-w，即不装(0)和装满(9)。

动态规划

上面的第二种解法其实已经很接近动态规划的处理思路了，再重新梳理一下整体的思路：整个求解过程分为n(物品总数)个阶段,每个阶段都会决策一个物品是否放到背包里， 在决策完之后，背包的重量都会有多种状态，也就是对应到树的不同节点，那么我们把每一层重复的状态合并， 只保留不重复的状态，就可以保证每一层的不同状态个数不会超过w个(背包的承载总重量)，就可以成功避免计算状态的指数级增长， 因为所有计算状态的背包重量都会小于w，我们再合并掉重复的，所有状态都是唯一，所以一定会小于w， 还有在决策时都是基于前一层的计算状态

上面的算法中，使用的是二维数组来记录状态，但是在实际使用这个二维数组的时候，发现，我们其实只需要，前一层的计算状态，来计算当前层状态，最后得出结论也是看最后一层计算状态，那么我们完全可以用一个一维数组保存前一层计算状态就可以，每次决策只要更新这个数组，把新的计算状态加进去，数组中的值为状态，索引为当前背包重量。