关于01背包个人的一些理解 - 晴天依旧天晴
source link: https://www.cnblogs.com/lzyan-blog/p/16452724.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
关于01背包个人的一些理解
1.当我们第一次看到题目的时候，很容易想到运用贪心的思想，每次拿性价比最大的物品。
容易举出反例：
3 76 10 //1.666...5 8 // 1.62 3 //1.5
2.接着我们很自然的就可以想到，既然运用贪心的思想不行，那么就枚举所有选取物品的情况，也就是组合。
于是我们就可以定义状态
dfs(i,v,ans)dfs(i,v,ans) 表示我搜索到了第 ii 个物品，此时已经选的物品的总体积为 vv , 所得到的价值为 ansans 。
当我们将 NN 个物品全都搜完后，若 v≤Mv≤M ，则更新我们的答案。
在这个过程中，我们可以发现 ， 对于一个状态 i,v,ansi,v,ans ,它可以从 i−1,v,ansi−1,v,ans 或 i−1,v−vi,（ans−wi）+wii−1,v−vi,（ans−wi）+wi 转移过来(分别对应了我选不选第 ii 个物品的情况)，但由于他所剩的物品个数一样，已经选的体积一样，所以尽管从两个不同的状态转移过来，所得的价值不同，但是之后能够遍历到的情况都是相同的。
显然有所得价值更大的状态，得到的结果优于价值更小的状态。
这就是最优子结构性质,正因为这个过程具有最优子结构性质，我们在进行下一阶段计算的时候，就免去了绝对不可能是最优的答案的多余的计算，所以我们可以通过他将搜索转化为DP,当然，这过程中同时具无后效性原则和重叠子问题。
简单解释一下重叠子问题优化的部分。当我已经知道状态 dpi,vdpi,v 所能获得的最大价值时，我将它记录下来，之后再遍历到这个状态，我直接就能返回我的最优解了，而不用继续搜下去，重新求解。这就要求了我们DP的问题具有该性质，否则就等同于没有记录，也就没有优化一说了。
无后效性则保证了我求出来的最优解不会被后面所影响，一定是最优的。
3.简单总结一下
状态： dpi,jdpi,j 表示以在前 ii 个物品中，选取体积为 jj 的物品，得到的最大价值。
状态转移方程：
dp[i][j]=max(dp[i−1][j],dp[i−1][j−vi]+wi)dp[i][j]=max(dp[i−1][j],dp[i−1][j−vi]+wi)
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>using namespace std;int n,m,v[3500],w[3500],dp[12885];int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]); memset(dp,0xcf,sizeof(dp));//赋值为-INF，表示该状态不可达，这里要特别注意，不能赋值为0，如果赋值为0的话，则表示容积为j的背包所能获得的最大价值，与我们所定义的状态相悖。 dp[0]=0; for(int i=1;i<=n;i++){ for(int j=m;j>=v[i];j--){ dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } int ans=0; for(int i=1;i<=m;i++) ans=max(ans,dp[i]);//找到最佳答案。 cout<<ans<<endl; return 0;}
唔，当然，如若是01背包的话，用 dpi,jdpi,j 表示前 ii 个物品中，用容积为 jj 的背包所能获得的最大价值也是ok的，但如果题目要我们恰好要把容积为 MM 的背包装满，这个状态所得到的答案就不一定正确了。
我给出的代码是已经优化过的版本，具体过程相信很多大佬都比我讲得好，这里主要分享我的一个思路，希望可以帮助自己巩固复习，也可以帮到大家理解。
-END--END-
2022.7.62022.7.6
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK