当前位置： 首页 > news >正文

陕西省建设监理协会网站证书网络推广宣传方式

news 2025/7/1 9:42:28
陕西省建设监理协会网站证书,网络推广宣传方式,百度云分享tp响应式网站开发,知名网站建设哪家好目录 前言 一 01背包问题 二 二维费用的背包问题​编辑 三 完全背包问题 总结 前言 这里是背包系列问题，需要知道动态规划地知识才可以理解这个一个东西，所以可以先去看看我的动态规划地文章 算法 动态规划-CSDN博客 一 01背包问题 首先背包问题…

目录

前言

一  01背包问题

二  二维费用的背包问题​编辑

 三  完全背包问题

总结

前言

这里是背包系列问题，需要知道动态规划地知识才可以理解这个一个东西，所以可以先去看看我的动态规划地文章
算法 动态规划-CSDN博客

一  01背包问题

首先背包问题是动态规划地十分经典的问题 
首先我们自己动手把这个dfs版本和记忆化搜索自己写出来
dfs版本

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 1010;
int n,v;
int bg[N];
int val[N];int dfs(int x, int bgv){if(x > n) return 0;else if(bgv < bg[x]) return dfs(x+1, bgv);else return max(dfs(x+1 , bgv),dfs(x+1 , bgv-bg[x])+val[x]);
}int main(){scanf("%d %d",&n,&v);for(int i = 1; i <= n; i++)scanf("%d %d",&bg[i],&val[i]);int result = dfs(1,v);  printf("%d",result);
}

记忆化搜索版本

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 1010;
int n,v;
int bg[N];
int val[N];
int mem[N][N];
int dfs(int x, int bgv){if(mem[x][bgv]) return mem[x][bgv];int sum = 0;if(x > n) return 0;else if(bgv < bg[x]) sum = dfs(x+1, bgv);else sum = max(dfs(x+1 , bgv),dfs(x+1 , bgv-bg[x])+val[x]);mem[x][bgv] = sum;return sum;
}int main(){scanf("%d %d",&n,&v);for(int i = 1; i <= n; i++)scanf("%d %d",&bg[i],&val[i]);int result = dfs(1,v);  printf("%d",result);
}

 这些在动态规划是有讲过的，所以这里就不多叙述了，接下来看看动态规划版本

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 1010;
int n,v;
int bg[N];
int val[N];
int dp[N][N];int main(){scanf("%d %d",&n,&v);for(int i = 1; i <= n; i++)scanf("%d %d",&bg[i],&val[i]);memset(dp ,0 , sizeof dp);//倒序for(int i = n; i>=1 ;i--){for(int j = 0; j<=v ;j++){if( j < bg[i]) dp[i][j] = dp[i+1][j];else{dp[i][j] = max(dp[i+1][j],dp[i+1][j-bg[i]]+val[i]);}}}printf("%d\n",dp[1][v]);//正序for(int i = 1; i<=n; i++){for(int j = 0; j <= v; j++){if(j < bg[i]) dp[i][j] = dp[i-1][j];else{dp[i][j] = max(dp[i-1][j],dp[i-1][j-bg[i]]+val[i]);}}}printf("%d\n",dp[n][v]);
}

这里写了两个版本，一个是正序的一个是逆序的

倒序分析
我们可以先来看一个图
样例

3 5
2 3
3 4
4 5

 我们先进性最底下的判断，我们输入了3个物品，背包的数值是5
注意这个最后一行是十分关键的，所以一定要弄出一行且数字为0
行就是要拿第几个物品，列就是背包容量，为1的话就是1，为0就是0

if( j < bg[i]) dp[i][j] = dp[i+1][j];else{dp[i][j] = max(dp[i+1][j],dp[i+1][j-bg[i]]+val[i]);}

这个是倒叙的核心代码
如果背包容器不够的话这个数组里面就填写上一行的值，也就是看上一行这个时候背包容量的最值，所以为什么要设置下一行为0，就是这个原因
如果可以存放，那么我们就要拿出最大值，我们就进行对比，也是这个时候背包容量，但是是拿上一个物品的最值，如果利用上一个物品的最值和这一次利用这个书包去装别的物品，看哪一个最大，哪一个更大就选择哪一个

正序，也就是和倒叙的表格是相反的，但是思路是正确的

因为倒叙我们是先拿最大的，所以正序不是先拿最大的，所以这个图会有些差别的，但是思路是一样

综上所述

dp的理解
动态规划01背包问题就是取上一行物品对应的最值和上一行减去这个背包容量的最值，然后放入当前新的物品进行比较看哪一个大就更新对应的位置

正序倒序的理解
正序就是减，为什么要减，因为我们是从上面开始排的
倒序就是加，为什么要加，因为我们是从下面开始排的

滚动数组的降维

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 1010;
int n,v;
int bg[N];
int val[N];
int g[N];
int f[N];int main(){scanf("%d %d",&n,&v);for(int i = 1; i <= n; i++)scanf("%d %d",&bg[i],&val[i]);for(int i = 1; i<=n; i++){for(int j = 0; j <= v; j++){if(j < bg[i]) g[j] = f[j];else{g[j] = max(f[j],f[j - bg[i]] + val[i]);}}memcpy(f , g , sizeof f);}printf("%d\n",f[v]);
}

我们不难从上面那个例子可以看出这个最后的结果始终与它的周围的一行像关联，那么我们就可以使用两个数组进行滚动，那么就可以不用开辟那么多的空间，实现了空间的优化

二  二维费用的背包问题

首先我们还是用dfs进行书写，这个就是多了一个重量

#include<iostream>
#include<cstring>
#include<cstring>
using namespace std;const int N = 1010;
int n,v,m;
int bg[N];
int mg[N];
int val[N];int dfs(int x, int bgv, int bgm){if(x > n) return 0; else if(bgv < bg[x] || bgm < mg[x]) return dfs(x+1 ,bgv ,bgm);else return max(dfs(x+1, bgv,bgm) , dfs(x+1,bgv - bg[x],bgm - mg[x]) + val[x]);
}int main(){scanf("%d %d %d",&n,&v,&m);for(int i = 1; i<n ;i++){scanf("%d %d %d",&bg[i],&mg[i],&val[i]);}int result = dfs(1,v,m);printf("%d",result);return 0;
}

这个肯定是过不去得，我们接下来用记忆化搜索试试

#include<iostream>
#include<cstring>
#include<cstring>
using namespace std;const int N = 1010;
int n,v,m;
int bg[N];
int mg[N];
int val[N];
int mem[N][100][100];int dfs(int x, int bgv, int bgm){if(mem[x][bgv][bgm]) return mem[x][bgv][bgm];int sum = 0;if(x > n) sum = 0; else if(bgv < bg[x] || bgm < mg[x]) sum = dfs(x+1 ,bgv ,bgm);else sum = max(dfs(x+1, bgv,bgm) , dfs(x+1,bgv - bg[x],bgm - mg[x]) + val[x]);mem[x][bgv][bgm] = sum;return sum;
}int main(){scanf("%d %d %d",&n,&v,&m);for(int i = 1; i<n ;i++){scanf("%d %d %d",&bg[i],&mg[i],&val[i]);}int result = dfs(1,v,m);printf("%d",result);return 0;
}

记忆化搜索是通过了，但是这个三维数组太大了，所以不推荐，下面我们用动态规划进行书写

#include<iostream>
#include<cstring>
#include<cstring>
using namespace std;const int N = 1010;
int n,v,m;
int bg[N];
int mg[N];
int val[N];
int f[N][110][110];int main(){scanf("%d %d %d",&n,&v,&m);for(int i = 1; i<n ;i++){scanf("%d %d %d",&bg[i],&mg[i],&val[i]);}for (int i = n; i >= 1; i--) {for (int j = 0;j <= v;j++) {for (int k = 0; k <= m;k++) {if (j < bg[i] || k < mg[i]) f[i][j][k] = f[i + 1][j][k];else {f[i][j][k] = max(f[i + 1][j][k], f[i + 1][j - bg[i]][k - mg[i]] + val[i]);}}}
}printf("%d",f[1][v][m]);return 0;
}

ok只能说学完动态规划，这个真的是太简单了 

 三  完全背包问题

这个题目就是实现了物品无限次拿，这个就是与01背包得差别
我们可以看到01背包得dfs

int dfs(int x, int bgv){if(x > n)return 0;else if(bgv < bg[x]) return dfs(x+1, bgv);else return max(dfs(x+1, bgv),dfs(x+1, bgv - bg[x])+ val[x]);
}

我们可以看到这个dfs，这个其实是有两个x+1的，也就是说这个+1限制了它无限拿去的条件，那么我们只需要删除一个+1就好了

dfs

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 1010;
int n,v;
int bg[N];
int val[N];int dfs(int x, int bgv){if(x > n)return 0;else if(bgv < bg[x]) return dfs(x+1, bgv);else return max(dfs(x+1, bgv),dfs(x, bgv - bg[x])+ val[x]);
}int main(){scanf("%d %d",&n,&v);for(int i = 1; i <= n; i++){scanf("%d %d",&bg[i],&val[i]);}int result = dfs(1,v);printf("%d",result);
}

 当我们在写这个代码的时候，我们是删除了后面的x+1的+1，但是有人就会说，为什么不可以删除前面的一个，因为我们删除前面的，按照原理上是应该可以的，但是你要知道递归式先递归前面的，也就是说你这个x一直都是x那么就会生成内存超出限制的错误，也就是S了，所以改动后面的

记忆化搜索

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 1010;
int n,v;
int bg[N];
int val[N];
int mem[N][N];int dfs(int x, int bgv){if(mem[x][bgv]) return mem[x][bgv];if(x > n)return 0;int sum = 0;if(bgv < bg[x]) sum = dfs(x+1, bgv);else sum = max(dfs(x+1, bgv),dfs(x, bgv - bg[x])+ val[x]);mem[x][bgv] = sum;return sum;
}int main(){scanf("%d %d",&n,&v);for(int i = 1; i <= n; i++){scanf("%d %d",&bg[i],&val[i]);}int result = dfs(1,v);printf("%d",result);
}

dp
我们来把这个转换为dp

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 1010;
int n,v;
int bg[N];
int val[N];
int f[N][N];int main(){scanf("%d %d",&n,&v);for(int i = 1; i <= n; i++){scanf("%d %d",&bg[i],&val[i]);}for(int i = n;i >= 1; i--){for(int j = 0; j <= v; j++){if(j < bg[i]) f[i][j] = f[i+1][j];else {f[i][j] = max(f[i+1][j],f[i][j - bg[i]] + val[i]);}}}printf("%d",f[1][v]);
}

总结

我们还是学习了dsf，记忆化，动态规划
这个背包问题就是需要一个max来求取最优子问题，然后前面再加几个判断条件就好了
然后记忆化搜索就是创建一个变量进行保存，然后再创建一个数组进行保存数据就好了
01背包式需要x+1进行限制，完全背包不需要
二维费用背包就是需要条件的限制而已
需要注意的是，我们需要进行限制的条件就是我们函数的形参

http://www.cadmedia.cn/news/14212.html

相关文章：

  • 母婴网站设计开发广州疫情最新消息今天封城了
  • 北京朝阳做网站搜索引擎推广方案案例
  • c 网站开发流程移动慧生活app下载
  • 江西抚州建设网站信息流优化师面试常见问题
  • 想建书画网站怎么做的徐州百度seo排名
  • 庆阳网站设计最热门的短期培训课程
  • 济宁任城区建设局网站百度联盟官网登录入口
  • 12306网站开发语言收录网站查询
  • 企业解决方案是什么seo优化排名软件
  • 简历做的很棒的网站公司网站制作流程
  • 广州建设网站专家seo排名优化教学
  • 一流的嘉兴网站建设广州30万人感染
  • 网络营销策略相关理论威海seo优化公司
  • 太原做网站baidu百度推广怎么注册账号
  • 简单的房源展示网站开发单页应用seo如何解决
  • 响应式网站的优点优化营商环境的金句
  • 沧州网站改版优化百度小说风云榜总榜
  • 武汉最好的网站建设公司软件测试培训班多少钱
  • 武汉网站优化公司seo优化官网
  • 巩义网站建设案例课堂app推广方案
  • 中交路桥建设有限公司网站百度seo外链推广教程
  • python网站开发pdf腾讯企业邮箱登录入口
  • 重庆大山建设有限公司网站百度全网营销
  • 鑫牛元网站建设吉林网站推广公司
  • 淄博网站建设铭盛信息seo的概念是什么
  • wordpress地方门户新手怎么做seo优化
  • 网站设计做微信发现界面农夫山泉软文300字
  • 傻瓜式建站平台外贸营销型网站制作公司
  • 珠海网站制作套餐优化搜索曝光次数的方法
  • 免费流量优化网站排名方法