使用动态规划解决01背包问题——优化版一、引言二、优化说明三、优化思路四、重点细节五、优化代码展示一、引言在上一篇文章“使用动态规划解决01背包问题(附详细代码及图解)”中介绍了使用动态规划解决01背包问题的思想以及详细代码。在本篇文章主要会对代码进行进一步的优化。二、优化说明在上一篇文章的代码中二维数组dp[i][j]存储了 “在前 i 个物品中不超过容量 j 的情况下可以获得的最大价值” 。这时候我们代码的空间复杂度为n*m。其实在dp[i][j]这个二维数组中前i-1维的数组所存储的数值都是十分鸡肋的这对我们的空间复杂度十分不友好。因此在优化代码中会用一个一维数组dp2[j]来改善这个问题使得程序的空间复杂度降低。三、优化思路首先代码的思路和使用二维数组时是一样的即逐一对每个i与j进行遍历获得“在前 i 个物品中不超过容量 j 的情况下可以获得的最大价值” 。但存储这个最大价值的二维数组变成了一维数组。核心代码实现的变化如下图所示。在优化后的代码中:最外层的循环每遍历完一次dp2记录的就是在前i个物品中不超过容量 j 的情况下可以获得的最大价值最外层的循环在每次遍历前dp2记录的就是在前i -1个物品中不超过容量 j 的情况下可以获得的最大价值。max(dp2[j],dp2[j-w[i]]v[i])和 **max(dp[i-1][j],dp[i-1][j-w[i]]v[i])**的作用其实是一样的。dp2[j]在没有进行赋值改变时他记录的是在前i -1个物品中不超过容量 j 的情况下可以获得的最大价值所以dp2[j]与dp[i-1][j]其实是同一个值。dp2[j-w[i]]v[i]和dp[i-1][j-w[i]]v[i]也是同理。四、重点细节在优化后的代码中有一个细节在里面那层循环中j一开始是为m然后递减的进行遍历。也就是说在遍历m时是从大到下进行遍历的。如果从小到大遍历那么就会出现下面这种情况在i2j5时dp2[5]max(dp2[5],dp2[5-w[2]]v[2])dp2[5]就会由1变为5j继续向后面遍历在i2j8时dp2[8]max(dp2[8],dp2[8-w[2]]v[2])dp2[8]就会由5变为9我们每种物品只有一种这明显不符合这是因为在遍历前dp2[j]记录的还是j-1层的数值如果从小到大去遍历进行改变那么前面部分的dp2[j]所记录的值就会变成当前j层的数值到后面部分的j就会以当前层的数值进行比较这会导致当前物品可不止放入一件的问题。而从大到小遍历j的话就可以完美解决这一问题。五、优化代码展示#includebits/stdc.h#includemath.husingnamespacestd;intmain(){vectorintw,v;vectorintdp2;intm,n;cout请输入背包的总重量endl;cinm;cout请输入物品数量endl;cinn;vectorvectorintdp(n1,vectorint(m1));w.push_back(0);v.push_back(0);for(inti0;in;i){cout请输入物品i1的重量和价值endl;intnew_w,new_v;cinnew_wnew_v;w.push_back(new_w);v.push_back(new_v);}// 一维数组背包问题for(inti1;in;i){for(intjm;w[i]j;j--){dp2[j]max(dp2[j],dp2[j-w[i]]v[i]);}}coutdp2[m]endl;return0;}