如果你跟我一样，是半天搞不懂一维01背包的小白，那么不妨看看这篇吧。 跟通常的解释不大一样哦。
大家都知道，01背包可以用制作N*M表格的方法解决，比如像下面这样 （如果这个忘了可以去文末看代码） 请注意，答案在哪里？有问题我们知道，答案必然是表格右下角里的数 既然如此·，为什么要保留完整的表格呢？有没有方法减少空间复杂度？
STEP 1 初步优化：全都需要吗？请关注我们填表的过程：第一列，第二列，第三列，第四列，第N列 在我们填第 i 列的时候，由状态转移方程 f[ i ][ j ]=max( f[ i-1 ][ j ] , f[ i-1 ][ j-w[ i ] ]+c[ i ]）可以知道: 第 i 列的数是什么，只跟第 i-1 列有关 而不需要再用到第 i-2 列的数。
节省存储空间的思路：不保留不需要用的数据，只保留需要用的。 注意！！！上面那句话是最重要的思想！！！我们称它为"原理1"理解了它接下来就好说了。
下面是具体方法： 1/ 在计算第 i 列时，因为只需要用到第 i-1 列，所以我们只保留第 i 列自身和第 i-1 列
2/ 由此产生思路：在每一次外层循环中，定义： 第 i 列为“当前列“， 第 i-1 列为”依据列“（因为第 i 列是依据 i-1 列推出来的）。 现在我们只需要一个2V的数组：[0][i]用于存储”依据列“，[1][i]用于存储”当前列“ 那么类似的有状态转移方程： f[ 1 ][ j ]=max( f [ 0 ][ j ] , f [ 0 ][ j - w[ i ] ]+c[ i ] ) 除方程不同外，2V的内层循环和N*V时相同
3/ 但是要注意！！！ 在我们计算完第 i 列后，我们接着就要计算第 i+1 列， 此时要注意：因为我们在计算 i+1 列，所以此时 i+1 列变成了”当前列“，而第 i 列变成了”依据列“ 所以我们就要”刷新“这个二维数组，把这个二维数组 目前的 ”当前列“变成”依据列“ （也就是让第 i 列成为”依据列“） 操作起来很简单：只需要把 [ 0 ][ x] 设为 [ 1 ][ x ]即可 同时[ 1 ][ x ] 我们并不需要动，因为待会计算时它们会被重新赋值
4/ 最后只需要输出 f [ 1 ][ v ] 即可 完整c++代码如下：
#include<bits/stdc++.h> using namespace std; int f[2][10005],w[1005],c[1005],n,v; int main(){ int i,j;//循环变量 cin>>n>>v;//读取物品种类N和背包体积V for(i=1;i<=n;i++)cin>>w[i]>>c[i];//读取每一种物品的体积和价值 for(i=0;i<=v;i++)f[0][i]=0; f[0][0]=0;//这一行还有上面那行是定义边界 for(i=1;i<=n;i++){ for(j=1;j<=v;j++){//内循环计算"当前列" if(j>=w[i])f[1][j]=max(f[0][j],f[0][j-w[i]]+c[i]); else f[1][j]=f[0][j]; } for(j=1;j<=v;j++)f[0][j]=f[1][j];//刷新"依据列" f[0][0]=0;//"依据列"最下面的数(容量为0时)的边界:0 } cout<<f[1][v]<<endl;//输出最后的"当前列"即可 return 0; } STEP 2 更进一步：一维数组！！！以上的内容都是很好理解的：我们为节省空间，抛弃了不需要的数据，就是除参与运算的两列以外的列
还能不能进一步优化呢 请看下图分析（依旧同一列代表物品种类数相同，同一行代表背包容量相同）： 其中，粉色方块是已经计算完成的，红色方块是正在计算的，蓝色方块是还没有计算的 黄色方块是计算红色方块可能需要的，因此我们应予以保留。 （额，准确的说，红色方块左边那个肯定用到，其他的是否会用到取决于 Wi 的值） 而绿色方块我们不需要！ 那么把绿色方块扔掉不就好了？
真的吗？好，现在我们假设我们就是不要绿色方块了，现在我们计算完了红色方块，要计算"当前列"中下一个方块了 我们用紫色表示这下一个方块： 注意！对于紫色方块，它可能用到所有黄色方块和 橙色方块！（注意上一张图里最上面的绿色方块变成了橙色的） 但是，我们刚才假定不存储黄色方块以下的绿色方块！ 因为没有这个橙色方块，我们无法计算紫色方块的值！
这说明了这个问题的症结： 因为内层循环是递增的循环，这就导致随着循环次数增多，计算过程中所需要用到的"依据列"中的数越来越多 因此，我们不能为了节省空间，把现在这次计算中用不到但是接下来会用到的值删掉！ 也就是说，橙色方块虽然在计算红色方块时用不到，但在计算紫色方块时需要用到！ 由此我们总结出：一个数据必须在现在和未来任何状态下都不会被使用，我们才可以不保留它。 我们管这个叫“原理2”。
/* 好吧，你可能还没有明白，举一个简单的例子： 你要参加一次考试，要考：数学、物理、化学、生物四门学科，你有四本相应的教材，而且假设你必须使用相应的教材来复习一个学科。这个考试有些特别，因为学科间关系很大 //就像动规里状态之间的依赖）： 具体是这样：物理需要数学知识，化学需要物理知识，生物需要化学知识。 如果考试顺序是：数学---->物理---->化学---->生物 //就像刚才方法中我们先算红色再算紫色 那么考完了数学你不能扔掉数学书，因为你还要考物理，而物理需要数学，就需要数学书； 同样的，考完物理你不能扔掉物理书…除非生物考完，否则你必须保留所有书! //就像我们使用二维数组时那样！ 显然要是这样，就没法节省你书包的空间了！
但是！如果我们改一下考试顺序， 让它变成：生物---->化学---->物理---->数学 那么考完生物，我们就可以愉快地扔掉生物书了，因为接下来用不到。 就这样，我们考完一科就扔掉一本书，书包空间就省了。 */
好，现在就让我们采用类似上面重新安排考试顺序的方法，修改一下一维数组的方案 在考试顺序的问题中，我们所需要的书本随着考试进行减少，后进行的考试（数学）用不到先考的学科（生物）的知识 类比程序，就是要改变内层循环的顺序！ 我们让内层循环倒着走不就行了！ 这就是必须逆序循环的原因！
现在，我们让"当前列"由下往上计算，如图： 红色方块计算完毕，接下来计算紫色方块： 红色方块左边那个方块在计算紫色方块时不再需要，所以它变成绿色的了。 这样的话，所有绿色的我们都可以愉快地扔掉。
现在我们再来分析一下，在我们计算紫色方块时，需要用到多少空间？ 需要：粉色方块+红色方块+黄色方块 总共是V个方块。 绿色方块在计算中不需要使用，容易理解为什么不存储它 但是为什么蓝色和紫色的方块也不需要存储呢？ 因为它们还没有被计算过！ 就像一个最简单的自加语句：i = i + 1，当然只有一个变量了。 或许你会问：蓝色和紫色方块未来将要被计算，不需要预留空间吗？ 之所以不需要，是因为我们采用了一种“覆盖”的方法 我们还是以刚才的过程为例：
注意！！！在第一张图中红色方块没有计算的时候，它左边的方块是黄色的，因为它要被使用，我们必须保留 但是，红色方块计算完之后，它左边的方块就不再需要于是变成绿的了，也就不用保留了 那么我们把红色方块的值存进它左边的绿色方块不就好了！ 这就是一个“覆盖”的过程。类比自加语句 i = i+1 很容易理解。 不妨把这个重要的技巧称为“原理3”
所以我们只需要开一个1*V的数组！ 然后我把这个数组单拎出来，还是在刚才的过程中，观察一下它的变化： 同时我们为了方便，就假设第三件物品重量是 5 ，因此需要调用棕色方块 （8 - 5 = 3）
现在让我们求出状态转移方程，解决问题！ 本质上，我们使用的方程还是 f[ i ][ j ]=max( f[ i-1 ][ j ],f[ i-1 ][ j-w[ i ] ]+c[ i ]） 我们要找的，只是它在一维存储方式下的变形
右侧长条代表我们的一维数组，在这里：
1/ 正在计算的·红色方块，在计算完成后被放进了 f [ 8 ] (注意是从上往下数，跟二维表格一样) 而在二维表格中，红色方块被表示为 f [ 3 ] [ 8 ]
2/ 红色方块左边的黄色方块，也是 f [ 8 ]，但是它马上要被红色方块覆盖，因此和红色方块共用一个存储空间 同时它对应二维时的 f [ 2 ] [ 8 ]
3/ max()里与黄色方块比较的棕色方块，是 f [ 3 ] 对应二维的 f [ 2 ] [ 3 ]
4/ 由此，我们得出，一维情况下： f [ j ] <=> f [ i ][ j ] f [ j - w [ i ] ] <=> f [ i-1 ] [ j - w [ i ] ] f [ j - w [ i ] ] + c [ i ] <=> f [ i -1 ] [ j - w [ i ] ] + c [ i ]
5/ 所以！ 一维的状态转移方程就是： f [ j ] = max ( f [ j ] , f [ j - w [ i ] + c [ i ] ]
大功告成，准备敲代码！ 哦，别忘了之前说过的，必须逆序循环！ 完整 c++ 代码如下：
#include<bits/stdc++.h> using namespace std; int f[10005],w[1005],c[1005],n,v; int main(){ int i,j; cin>>n>>v; for(i=1;i<=n;i++)cin>>w[i]>>c[i]; f[0]=0; for(i=1;i<=n;i++){ for(j=v;j>=1;j--){ if(j>=w[i])f[j]=max(f[j],f[j-w[i]]+c[i]); else f[j]=f[j]; } } cout<<f[v]<<endl; return 0; }啊哦，终于完成了，蒟蒻小白萌新的人生中的从第一篇博客 写出来目的主要是整理自己的思路吧（我这个废物脑子理解东西贼慢。。） （也可能是因为考完试闲得无聊） 期待大佬们可以多帮我挑错（很有可能代码都错了）
好吧，总结一下：
原理1：只保留需要用的数据，抛弃不需要用的。
原理2：一个数据在当前可能不需要，但未来可能需要，因此须考虑清楚是否保留 对于一维01背包，我们用逆序循环解决了此问题
原理3：如果两个数据，不会同时存在，或者没有必要同时存在，只开一个存储空间
最后的最后，我把最经典最传统的方法的代码拿来：
#include<bits/stdc++.h> using namespace std; int f[1005][10005],w[1005],c[1005],n,v; int main(){ int i,j; cin>>n>>v; for(i=1;i<=n;i++)cin>>w[i]>>c[i]; for(i=1;i<=v;i++)f[0][i]=0; for(i=1;i<=n;i++)f[i][0]=0; for(i=1;i<=n;i++){ for(j=1;j<=v;j++){ if(j>=w[i])f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]); else f[i][j]=f[i-1][j]; } } cout<<f[n][v]<<endl; return 0; }谢谢大家！！！
