本篇内容主要讲解“如何理解背包问题”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“如何理解背包问题”吧!
田家庵ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为创新互联公司的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:18982081108(备注:SSL证书合作)期待与您的合作!
0-1背包问题的二维bc
#include#include #include #include using namespace std; const int N=1010; int n,m; int v[N],w[N]; int f[N][N]; //价值总和 int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; //当选择0件物品时,价值总和为0,即f[0][0~m] = 0; //由于已定义为全局变量,已经初始化为0,所以可以不写了。 for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ //不选择第i个物品的方案 f[i][j]=f[i-1][j]; //选择第i个物品的方案可能不存在 //选择第i个物品————先去掉第i个物品,减去其重量再加上其价值。 if(j>=v[i]){ f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); } } } cout< 优化(转换成一维,滚动数组)
#include#include #include #include using namespace std; const int N=1010; int n,m; int v[N],w[N]; int f[N]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; for(int i=1;i<=n;i++) for(int j=m;j>=v[i];j--) f[j]=max(f[j],f[j-v[i]]+w[i]); cout< 到此,相信大家对“如何理解背包问题”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
分享名称:如何理解背包问题
文章转载:http://bjjierui.cn/article/jhooic.html