中国建设网站下载,seo资源网站排名,抚宁区建设局网站,网站开发流程联系方式背包问题身为一个非常经典的动态规划问题#xff0c;理清思路很重要#xff0c;在经过多次观看y总视频和b站解析#xff0c;加上CSDN的文章辅助#xff0c;我终于从很多不理解到大彻大悟#xff0c;下面是我对于背包问题思路的总结#xff0c;有问题的话欢迎指出。谈到背…背包问题身为一个非常经典的动态规划问题理清思路很重要在经过多次观看y总视频和b站解析加上CSDN的文章辅助我终于从很多不理解到大彻大悟下面是我对于背包问题思路的总结有问题的话欢迎指出。谈到背包问题先以下面这最经典的一道背包问题为例子有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi价值是 wi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。输入格式第一行两个整数NV用空格隔开分别表示物品数量和背包容积。接下来有 N 行每行两个整数 vi,wi用空格隔开分别表示第 ii 件物品的体积和价值。输出格式输出一个整数表示最大价值。数据范围0N,V≤10000vi,wi≤1000输入样例4 5
1 2
2 4
3 4
4 5输出样例8不废话直接给出两种思路可以结合看bilibili表格法b站中把背包问题转化为一个表格来理解我觉得特别有用对于背包问题光是靠说是很难理解的通过表格总结公式和方法对于该题非常有效入门背包问题必须要看看。链接【【动态规划】背包问题】 https://www.bilibili.com/video/BV1K4411X766/?share_sourcecopy_webvd_source7e63f1b6fa68c511b241d12721f0a4bc先从一个具体例子入手对于所给定的背包容量和物品状态我们需要找出价值最大的一个组合通过画图假设这是一个f(i,j)的数组则每一个fi,j的值都是前i物品编号件物品中不超过j背包容量体积下的最大值注意重中之重每个格子是只考虑前i件物品 当时我比较不能理解的是为什么只考虑前i件物品下不超过该体积的值编号i之后的物品不也可以放入该体积容量假如该方法价值更高那不是就不是该背包体积下最大价值了。当时就是不能理解啊后面思考之后终于悟了表格是所有情况都能考虑到因为每个格子是在选了和不选的情况下取的最大值我们只要只考虑前i件物品后面每一个格子就能由前面的推出来也能得到一个公式。比如这题假如我们要算第f48的值也就是该条件的最大价值假设我们不知道该值前面的数据我们都是知道的因此第4件物品有选和不选两种情况如果不选f48f38本来需要考虑前4个现在只需要考虑前3个而f38前面是已经算出来了。假如选则需要满足一个条件即此时背包剩余的容量一定大于第四件物品体积在此前提下我们选了第4件物品然后往前找选了4之后我们表格应该找到f38-第四件物品体积也就是f33此时只考虑前3个物品即f48第四件物品价值f33因为前面的f都是已经计算出来对应条件的价值最大值了f48的值也就出来了。最后在选和不选中取一个最大值即使f48的值。用表格容易理解但确定是该方法不容易运用到其他同题型中下面给出第二种2.闫式DP分析法此方法比较有规律和逻辑但对于新手不容易理解nnd当时我看了好多遍才懂但是第一种懂了第二种也应该学习因为该方法会了之后同题型就变得很简单了后面我也会发类似题目的博客用该方法来做会发现简单很多。大致思路与第一种是差不多的也是把fij分为两种情况这里不多做解释和第一种同理该方法很系统的对于该类题型的做题方法做了一个总结此时fij为一个集合每个fij的内容需要其属性来判断背包问题要求我们找最大值即属性为max因此fij为对应条件下的最大值然后进行状态计算如何计算fij找到最后一个不同点进行划分对于其他题型我们只需要对fij进行不同情况的划分考虑完就可以了。状态计算的核心如何将现有的集合划分为更小的子集,使得所有子集都可以计算出来这是我们需要做的事说了这么多没有代码就是空谈代码如下第一种和第二种方法都一样代码#includeiostream
using namespace std;
const int N1010;
int f[N][N];
int v[N],w[N];
int main()
{int n,m;cinnm;for(int i1;in;i) cinv[i]w[i];for(int i1;in;i)//i代表物品第一件开始考虑for(int j0;jm;j)//j代表背包容量可以为0一件都不选因此从0开始{f[i][j]f[i-1][j];//不选第i个物品if(jv[i]) f[i][j]max(f[i][j],f[i-1][j-v[i]]w[i]);//选第i个物品}coutf[n][m]endl;return 0;
}对于该代码我们是可以进行优化的把二维转化为一维可以节省空间和时间这里也给出优化后的代码想要了解为什么的这里也给出一个链接https://www.acwing.com/solution/content/1374/里面解释的非常好这里我就不多阐明优化后的代码#includeiostream
using namespace std;
const int N1010;
int f[N];
int v[N],w[N];
int main()
{int n,m;cinnm;for(int i1;in;i) cinv[i]w[i];for(int i1;in;i)for(int jm;jv[i];j--)//这里为什么从后往前遍历因为为了防止第i层前面先被更新{f[j]max(f[j],f[j-v[i]]w[i]);}coutf[m]endl;return 0;
}最后祝大家早日理解背包问题把动态规划用的行云流水以后也会常更新dp的
