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

4a级旅游网站建设的要求aso优化服务站

4a级旅游网站建设的要求,aso优化服务站,网页制作范例,wordpress中文图片插件下载目录 前言#xff1a; 01背包问题#xff1a; 二维数组思路#xff1a; 一维数组思路#xff1a; 总结#xff1a; 前言#xff1a; 在前面我们学习动态规划理论知识的时候#xff0c;我就讲过要介绍一下背包问题#xff0c;那么今天我们就来讲解一下背包问题。 在这…  目录 前言 01背包问题 二维数组思路 一维数组思路 总结 前言 在前面我们学习动态规划理论知识的时候我就讲过要介绍一下背包问题那么今天我们就来讲解一下背包问题。 在这里我们只介绍01背包至于分组背包和混合背包这种的已经属于竞赛级别的了难度过高我们在这里就不学习了。 【夜深人静学数据结构与算法 | 第十篇】动态规划_我是一盘牛肉的博客-CSDN博客 01背包问题 该问题的背景是一个背包和一组物品每个物品都有自己的价值和重量。目标是选择一些物品放入背包中使得放入的物品总重量不超过背包的容量且总价值最大化。 具体来说给定 n 个物品其重量分别为 w1, w2, …, wn价值分别为 v1, v2, …, vn以及一个背包的容量 W。如何在不超过背包容量的情况下拿到的物品可以实现价值最大 我们还是严格按照动态规划五步走来确定解题思路 二维数组思路 1.dp数组的含义以及下标的含义dp[i][j]的含义为把[0,i]的物品放到容量为j的背包里 的最大价值。 如果不放当前第 i 个物品那么此时的最大价值就是 dp[ i-1] [ j ]如果放当前第 i 个物品那么此时的最大价值就是 dp [ i-1 ][ j-weight[i]] value[i] 2.递推公式的推导dp[i][j] max(dp[ i-1] [ j ],dp [ i-1 ][ j-weight[i]] value[i]) 3.dp数组的初始化对于dp数组应该如何初始化我们可以用画图的方式来表示一下dp数组 如果此时我们动态规划到红色的这块区域由dp数组的公式 dp[i][j] max(dp[ i-1] [ j ],dp [ i-1 ][ j-weight[i]] value[i])我们可以知道这块红色的区域的值一定是由整个数组的左上角区域慢慢推过来的。因此在开始我们就要把左上角的全部初始化防止出现减不了的情况 而具体的初始化值我们简单想一想就可以知道当背包容量为0的时候就装不了东西那么最大价值就是0那么我们就把竖行的值初始化为0也就是dp[i][0]初始化为0横行就是始终装物品0那么只要背包的容量大于物品0的容量最大的价值就是dp[0][j]value.(物品0。 4.dp数组遍历顺序对于二维数组的这两个for循环无论是先便利背包还是物品都是可以的。 那么用一个例子来实现一下动态规划 #include iostream #include vectorusing namespace std;// 定义物品结构体包含重量和价值 struct Item {int weight;int value; };int knapsack(int W, vectorItem items) {int size items.size();vectorvectorint dp(n 1, vectorint(W 1, 0));for (int i 1; i n; i) {for (int j 1; j W; j) {// 当前物品重量大于背包容量无法放入背包if (items[i - 1].weight j) {dp[i][j] dp[i - 1][j];}else {// 考虑放入或不放入当前物品的两种情况取最大值dp[i][j] max(dp[i - 1][j], dp[i - 1][j - items[i - 1].weight] items[i - 1].value);}}}return dp[n][W]; // 返回最优解 }int main() {int W 10; // 背包容量vectorItem items { {2, 6}, {2, 10}, {3, 12} }; // 物品列表int maxValue knapsack(W, items); // 求解最优解cout 最大总价值为: maxValue endl;return 0; } 一维数组思路 在一维数组优化中我们只需要创建一个长度为背包容量1的一维数组用于记录在不超过当前背包容量下的最优解。具体优化过程如下 原始的二维dp数组定义为dp[n 1][W 1]其中dp[i][j]表示在前i个物品中选择不超过重量j的物品时的最优解。 将二维dp数组优化为一维数组dp[W 1]其中dp[j]表示在不超过背包容量j的情况下的最优解。 优化后的代码示例 #include iostream #include vectorusing namespace std;// 定义物品结构体包含重量和价值 struct Item {int weight;int value; };int knapsack(int W, vectorItem items) {int n items.size();// 创建一维dp数组并初始化为0vectorint dp(W 1, 0);for (int i 0; i n; i) {for (int j W; j items[i].weight; j--) {// 考虑放入或不放入当前物品的两种情况取最大值dp[j] max(dp[j], dp[j - items[i].weight] items[i].value);}}return dp[W]; // 返回最优解 }int main() {int W 10; // 背包容量vectorItem items { {2, 6}, {2, 10}, {3, 12} }; // 物品列表int maxValue knapsack(W, items); // 求解最优解cout 最大总价值为: maxValue endl;return 0; }在上述代码中我们使用一个长度为背包容量1的一维数组dp[W 1]来记录在不超过当前背包容量下的最优解。在计算时我们从后往前遍历物品并从后往前更新一维dp数组。这样可以确保在更新dp[j]时所需的dp[j - items[i].weight]已经是前一轮的值并且不会影响当前轮的计算结果。通过这种方式可以实现将二维dp数组优化为一维数组的目的并得到正确的最优解。 总结 本文我们学习了01背包其实我们可以发现动态规划题目还是有比较强的套路性的我们把动态规划拆分成为了五部我们只要按照这五步进行实际上解决动态规划题目还是很简单的。 如果我的内容对你有帮助请点赞评论收藏。创作不易大家的支持就是我坚持下去的动力
http://www.sadfv.cn/news/281377/

相关文章:

  • 沈阳医疗网站建设建设cpa网站需要什么
  • 手机导航网站模板wordpress调用当前分类描述
  • 电子业网站建设网站上的文章用秀米可以做吗
  • 西安优化网站wordpress 摘要显示
  • 深圳网站平台珠海市企业网站建设
  • 怀仁建设局网站创意设计说明范文
  • 成都网站搜索排名优化哪家好清新区住房和城乡建设局网站
  • wordpress区块链四川二级站seo整站优化排名
  • 常州企业网站建设dz论坛模板
  • wordpress 做外贸站中国建设网官方网站建筑工程税率
  • 怎么建立自己的网站平台扬州市工程信息网
  • 天津网站建设noajtwordpress需要什么安装环境
  • 学生组织网站建设产品推广平台有哪些
  • 网站建设管理分工的说明湘潭网站seo
  • 个人网站建设模板wordpress 内存溢出
  • 网站运营现状confluence和wordpress
  • jsp开源网站ui设计培训哪家好
  • 做内贸哪个网站找客户下载网站建设
  • 如何让新网站被收录免费app大全下载
  • 网站备案流程解答赶集直招找工作
  • 彬县网站建设茌平网站开发
  • 黄金网站软件app大全视频营销型企业网站分析与诊断
  • 网站备案流程慢建设部网站注册查询
  • 个人网站建设案例教程广州番禺核酸检测点
  • 四川专门做招聘酒的网站十五种网络营销工具
  • 微商城网站建设行情网站开发团队工作总结
  • 什么网站做问卷好龙岩到永定
  • 大连网络推广网站优化找哪家好做足彩推荐赚钱的网站
  • 033340网站建设与管理蒙文网站建设
  • 网站开发 工期安排百度扫一扫识别图片在线