动态规划01背包问题

动态规划:01背包问题

情景

现在有一个容量有限的背包(比如能装10公斤的东西)，现在有价值不同，重量也不同的几件物品，我们要怎样装才能让这个背包尽可能的装的价值最高

这就是为什么这个问题叫01背包问题，每个物品只有两种状态,放入(1)和不放入(0)

问题

有一个背包，最大承重W=10。有4件物品：

• 物品1：重量2，价值3
• 物品2：重量3，价值4
• 物品3：重量4，价值5
• 物品4：重量5，价值6

问题：选择哪些物品放入背包，使总价值最大且总重量≤10？

普通解法

1. 暴力计算

我们如果想把每个组合都试一遍，总能试出答案

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intbruteForce01(vector<int>&values,vector<int>&weights,intcapacity){intn=values.size();intmaxVal=0;for(intmask=0;mask<(1<<n);mask++){intcurWeight=0,curValue=0;for(inti=0;i<n;i++){if(mask&(1<<i)){curWeight+=weights[i];curValue+=values[i];}}if(curWeight<=capacity){maxVal=max(maxVal,curValue);}}returnmaxVal;}intmain(){vector<int>values={3,4,5,6};vector<int>weights={2,3,4,5};intcapacity=10;cout<<"暴力解法结果: "<<bruteForce01(values,weights,capacity)<<endl;return0;}

确实算出了结果，但这个方法非常非常的麻烦，n = 4的情况下用了16种方法才试出答案，时间复杂度时O(n^2)

2. 递归

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intknapsackRecursive(inti,intremaining,vector<int>&values,vector<int>&weights){if(i==values.size())return0;intnotTake=knapsackRecursive(i+1,remaining,values,weights);inttake=0;if(remaining>=weights[i]){take=knapsackRecursive(i+1,remaining-weights[i],values,weights)+values[i];}returnmax(notTake,take);}intmain(){vector<int>values={3,4,5,6};vector<int>weights={2,3,4,5};intcapacity=10;cout<<"递归解法结果: "<<knapsackRecursive(0,capacity,values,weights)<<endl;return0;}

递归解法将这个二问题拆成小问题来解决，将选取这个物品和不选这个物品作比较，取最大值

这个解法看似没有暴力计算这么麻烦，但是在计算的过程中会有重叠子问题，重复的计算还是会带来效率的低下，那么为了避免重叠子问题，我们要使用动态规划

动态规划

二维数组

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intknapsackDP(vector<int>&values,vector<int>&weights,intcapacity){intn=values.size();vector<vector<int>>dp(n+1,vector<int>(capacity+1,0));for(inti=1;i<=n;i++){intweight=weights[i-1];intvalue=values[i-1];for(intw=0;w<=capacity;w++){if(w<weight){dp[i][w]=dp[i-1][w];}else{dp[i][w]=max(dp[i-1][w],dp[i-1][w-weight]+value);}}}returndp[n][capacity];}intmain(){vector<int>values={3,4,5,6};vector<int>weights={2,3,4,5};intcapacity=10;cout<<knapsackDP(values,weights,capacity)<<endl;return0;}

我们创建了一个二维的数组，行代表考虑前i个物品，列代表背包当前的容量，两者合起来就是在考虑前i个物品时，背包容量为w时的最大值

现在将它初始化

现在对前k个物品进行外层遍历，在对背包的容量进行内层遍历，对于每个dp[i][w]我们都有两种情况，装的下和装不下，装不下那只能不选了，重在在于这个装的下，在这个时候，我们会有两种选择，装和不装，这时候就要比较不装的时候，和腾出该空间后剩下的价值比较

所以同样是比较，动态规划只需要计算一遍即可，比递归要快的多

一维数组

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intknapsack01_1D(vector<int>&values,vector<int>&weights,intcapacity){intn=values.size();vector<int>dp(capacity+1,0);for(inti=0;i<n;i++){for(intw=capacity;w>=weights[i];w--){dp[w]=max(dp[w],dp[w-weights[i]]+values[i]);}}returndp[capacity];}intmain(){vector<int>values={3,4,5,6};vector<int>weights={2,3,4,5};intcapacity=10;cout<<knapsack01_1D(values,weights,capacity)<<endl;return0;}

dp[w]代表背包容量为w时的最大价值，仍然是熟悉的两层遍历，唯一不同的一点就是内层遍历变成了逆序遍历

为什么会这样？

这个数组只有一维，有限的空间使得计算时会包含当前的物品如果我们使用正序遍历，在dp的计算中会出现重复的计算，会存在一个物品被用了两次

所以我们使用逆序，从大容量向小容量思考，在计算dp时保证不含当前物品

解法对比表

总结

学习01背包问题更能理解动态规划的本质，理解其中空间换时间的思想，这篇文章是我之前动态规划的进一步学习，也为学习后边其他背包问题做铺垫