这个压缩太好了
因为完全背包能递推下去，子问题最优，而多重背包不一定， 举个例子，假设有两类物品，一类物品是体积1价值2，数量是2，一类物品是体积2价值3，数量是2，书包体积是7，在这个情况下还按完全背包那个流程去遍历，最上面一层i循环是物品，下面是j循环，在循环到第二个物品时，当j=5时，考虑这时候的最大值，是23+11 两个体积2的物品1个体积1的物品，这时候是最大价值，但是这个最大价值无法退出7的最大价值，因为有f［5］推f[7]时你不能再选体积为2的物品了，因为已经用完了，当然也不能再选1，因为我们的i循环已经进行到第二个物品了，不能退回了，而容积为7时的最大价值其实是两个体积1两个体积2，但是f[5]为了保证自己的最大委屈求全去了一个体积1，导致后面容量充足时无法再找回体积1。 而假如是完全背包则不会出现上述情况
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 2, 4, 4, 4, 4, 4, 4, 0, 0] [0, 2, 4, 5, 7, 8, 10, 10, 0, 0] 你説的這種情況運行出來的矩陣是這個，雖然在j=5的時候最大值是取7但是并不影響他後面在j=7,8,9的時候能夠取到更大的之
为什么完全背包遍历j是正序，多重背包是逆序，不是只多一个限制条件吗？
你还是先看看二维写法吧，云
有没有人写个详解啊，太干货了
哇!好厉害的一位压缩，给你一波666哦
空间压缩到一维数组，即O(V)，赞！不过时间还是O(NVK)
硬核
ì
这个压缩太好了
因为完全背包能递推下去，子问题最优，而多重背包不一定，
举个例子，假设有两类物品，一类物品是体积1价值2，数量是2，一类物品是体积2价值3，数量是2，书包体积是7，在这个情况下还按完全背包那个流程去遍历，最上面一层i循环是物品，下面是j循环，在循环到第二个物品时，当j=5时，考虑这时候的最大值，是23+11 两个体积2的物品1个体积1的物品，这时候是最大价值，但是这个最大价值无法退出7的最大价值，因为有f［5］推f[7]时你不能再选体积为2的物品了，因为已经用完了，当然也不能再选1，因为我们的i循环已经进行到第二个物品了，不能退回了，而容积为7时的最大价值其实是两个体积1两个体积2，但是f[5]为了保证自己的最大委屈求全去了一个体积1，导致后面容量充足时无法再找回体积1。
而假如是完全背包则不会出现上述情况
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 4, 4, 4, 4, 4, 4, 0, 0]
[0, 2, 4, 5, 7, 8, 10, 10, 0, 0]
你説的這種情況運行出來的矩陣是這個，雖然在j=5的時候最大值是取7但是并不影響他後面在j=7,8,9的時候能夠取到更大的之
为什么完全背包遍历j是正序，多重背包是逆序，不是只多一个限制条件吗？
你还是先看看二维写法吧，云
有没有人写个详解啊，太干货了
哇!好厉害的一位压缩，给你一波666哦
空间压缩到一维数组，即O(V)，赞！不过时间还是O(NVK)
硬核