算法设计与分析 例题解答 解空间与搜索

1.请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20, 15, 10},价值为{20, 30, 25},背包容量为25时搜索空间树。

答:

解空间树:

搜索空间树:

2.

考虑用分支限界解0-1背包问题

给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?

示例:n=3, C=30, w={16, 15, 15}, v={45, 25, 25}

求:1、问题的解空间树

 2、约束条件

2、如何剪枝?

问题的解空间树:

设r是当前尚未考虑的剩余物品价值总和;Cv是当前价值;bestv是当前最优价值。

当r+Cv≤bestv时,可剪去右子树。

3.请画出用回溯法解4皇后问题的解空间树和搜索空间树:

4.

 考虑使用动态规划方法求解下列问题:

01背包数据如下表,求:能够放入背包的最有价值的物品集合。

如设: V(i, j) —— 前 i 个物品中能够装入承重量 j 的背包中的最大总价值。请将如下递推式填写完整:

V(0, j) = 0(0个物品),V(i, 0) = 0(承重量0)

 V(i, j) = V(i-1, j)   第 i 个物品不能装入,  j < wi  (超重)

 V(i, j) = max {                ,                 }   j > wi (不超重)

           i在最优子集中     i不在最优子集中

自底向上:按行或列填写下表。

V

j=0

1

2

3

4

5

i=0

0

0

0

0

0

0

1

0

2

0

3

0

4

0

答:

V(0, j) = 0(0个物品),V(i, 0) = 0(承重量0)

V(i, j) = V(i-1, j)   第 i 个物品不能装入,  j < wi  (超重)

V(i, j) = max { vi + V(i-1,j-wj)        ,   V(i-1, j)        }   j > wi (不超重)

            i在最优子集中         i不在最优子集中

V

j=0

1

2

3

4

5

i=0

0

0

0

0

0

0

1

0

2

0

3

0

4

0

V

j=0

1

2

3

4

5

i=0

0

0

0

0

0

0

1

0

0

12

12

12

12

2

0

10

12

22

22

22

3

0

10

12

22

30

32

4

0

10

15

25

30

37

5.

考虑在序列A[1..n]中找最大最小元素的问题。一个分治算法描述如下:如果n≤2 就直接求解。否则,将序列等分成两个子序列A[1..n/2]和A[n/2+1..n],分别找出这两子序列的最大最小元素x1,y1 和x2,y2;然后据此求出A[1..n]的最大元素x=max{x1,x2}及最小元素y=min{y1,y2}。请给出该算法计算时间T(n)满足的递归方程,并解方程来确定算法的时间复杂度。假定n=2k(k 为正整数)。

答:

算法时间复杂度满足如下递归方程:

T(n)=2T(n/2)+2(n>2);T(2)=1。

因为 n=2 kk 为正整数),所以,

T(n)= T(2 k)= 2T(2 k-1)+2= 22T(2 k-2)+ 22+2

= 2k-1T(2)+ 2k-2+⋯+23+22+2

= 2k-1+⋯+23+22+2。因此,T(n)=Q(n)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/324704.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2 GPIO控制

ESP32的GPIO的模式&#xff0c;一共有输入和输出模式两类。其中输入模式&#xff1a;上拉输入、下拉输入、浮空输入、模拟输入&#xff1b;输出模式&#xff1a;输出模式、开漏输出&#xff08;跟stm32八种输入输出模式有所不同&#xff09;。库函数中控制引脚的函数如下&#…

行业新应用:电机驱动将成为机器人的动力核心

电机已经遍布当今社会人们生活的方方面面&#xff0c;不仅应用范围越来越广&#xff0c;更新换代的速度也日益加快。按照工作电源分类&#xff0c;可以将它划分为直流电机和交流电机两大类型。直流电机中&#xff0c;按照线圈类型分类&#xff0c;又可以分为有铁芯的电机、空心…

FFmpeg常用API与示例(四)——过滤器实战

1.filter 在多媒体处理中&#xff0c;filter 的意思是被编码到输出文件之前用来修改输入文件内容的一个软件工具。如&#xff1a;视频翻转&#xff0c;旋转&#xff0c;缩放等。 语法&#xff1a;[input_link_label1]… filter_nameparameters [output_link_label1]… 1、视…

书生浦语训练营第四次课作业

基础作业 环境配置 拷贝internlm开发机内的环境 studio-conda xtuner0.1.17# 激活环境 conda activate xtuner0.1.17 # 进入家目录 &#xff08;~的意思是 “当前用户的home路径”&#xff09; cd ~ # 创建版本文件夹并进入&#xff0c;以跟随本教程 mkdir -p /root/xtuner0…

27.哀家要长脑子了!---栈与队列

1.739. 每日温度 - 力扣&#xff08;LeetCode&#xff09; 用单调栈的方法做&#xff1a; 从左到右遍历数组&#xff1a; 栈中存放的是下标&#xff0c;每个温度在原数组中的下标&#xff0c;从大到小排列&#xff0c;因为这样才能确保的是最近一天的升高温度 如果栈为空&am…

优化重启Redis服务脚本

#!/bin/sh echo -e "\033[33m正在关闭redis服务和测试redis进程是否关闭...\033[0m" pkill redis-server sleep 1 #echo -e "\033[33m测试redis进程是否关闭...\033[0m" ps -ef|grep redis-server sleep 1 echo "" echo -e "\033[33m正在…

【人工智能Ⅱ】实验5:自然语言处理实践(情感分类)

实验5&#xff1a;自然语言处理实践&#xff08;情感分类&#xff09; 一&#xff1a;实验目的与要求 1&#xff1a;掌握RNN、LSTM、GRU的原理。 2&#xff1a;学习用RNN、LSTM、GRU网络建立训练模型&#xff0c;并对模型进行评估。 3&#xff1a;学习用RNN、LSTM、GRU网络做…

2010年认证杯SPSSPRO杯数学建模D题(第一阶段)服务网点的分布全过程文档及程序

2010年认证杯SPSSPRO杯数学建模 D题 服务网点的分布 原题再现&#xff1a; 服务网点、通讯基站的设置&#xff0c;都存在如何设置较少的站点&#xff0c;获得较大效益的问题。通讯基站的覆盖范围一般是圆形的&#xff0c;而消防、快餐、快递服务则受到道路情况和到达时间的限…

【前端基础】CSS样式+Vue中绘制时间轴

深度选择器 在 Vue.js 中&#xff0c;/deep/、>>>、:deep 和 ::v-deep 这些都是深度选择器&#xff0c;用于修改子组件的样式。它们主要用于解决作用域样式和组件样式之间的冲突问题。 1. /deep/ 或 >>> /deep/ 和 >>> 是相同的选择器&#xff0c;…

华为机考入门python3--(23)牛客23- 删除字符串中出现次数最少的字符

分类&#xff1a;字符串 知识点&#xff1a; 访问字典中keychar的值&#xff0c;不存在则返回0 my_dict.get(char, 0) 字典的所有值 my_dict.value() 列表中的最小值 min(my_list) 题目来自【牛客】 import sysdef delete_min_freq_char(s):# 计算字母出现的频次…

将来会是Python、Java、Golang三足鼎立吗?

在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「 Java的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff01; 软件工程里没有银弹&#xff…

word图片水印

一、word中旧水印如何删除 打开word模板&#xff0c;想要删除旧水印&#xff0c;如下图所示操作&#xff0c;但是旧水印删除不掉。 以为上传新水印图片会替换掉旧水印&#xff0c;结果显示了2个水印&#xff0c;要怎么删除呢&#xff1f; 如下截图所示&#xff0c;双击打开页…

雷森托尔环保科技有限公司见证2024杭州数字供应链装备展潮流

参展企业介绍 青岛雷森托尔环保科技有限公司创建于2018年&#xff0c;位于山东青岛&#xff0c;现注册资本3000万。公司主营生产模压木托盘、化工木托盘、大型设备木包装、出口木托盘、酒柜木酒架等&#xff0c;公司拥有技术人员6人&#xff0c;均为包装设计专业毕业&#xff0…

Qt | QSpinBox 类 QDoubleSpinBox 类(微调框)

01、QSpinBox 类 1、QSpinBox类是 QAbstractSpinBox 类的直接子类和具体实现, 2、QSpinBox 类被设计用于处理整数和离散值集合,对于浮点值使用 QDoubleSpinBox 类实现。 3、QSpinBox 默认只支持整数值,但可通过其内部的成员函数进行扩展,以支持使用不同的 字符串。 02…

【数组算法】598. 区间加法

给你一个 m x n 的矩阵 M 和一个操作数组 op 。矩阵初始化时所有的单元格都为 0 。ops[i] [ai, bi] 意味着当所有的 0 < x < ai 和 0 < y < bi 时&#xff0c; M[x][y] 应该加 1。 在 执行完所有操作后 &#xff0c;计算并返回 矩阵中最大整数的个数 。 示例 1: …

深入理解指针(1)

在之前我们学习了许多c语言的基础知识&#xff0c;让我们初步了解了c语言&#xff0c;接下来将来到c语言中一个重点的知识章节--指针&#xff0c;学习完指针后将会让我们对c语言有更深入的理解&#xff0c;接下来就开始指针的讲解 1.内存与地址 1.指针 在了解内存与地址前&am…

2024.5.8 关于 SpringCloud —— Ribbon 的基本认知

目录 Ribbon 负载均衡原理 工作流程 Ribbon 负载均衡规则 Ribbon 负载均衡自定义化 代码方式修改规则 配置文件方式修改规则 小总结 Ribbon 设定饥饿加载 Ribbon 负载均衡原理 工作流程 order-service 使用 RestTemplate 发送请求&#xff0c;随后该请求将会被 Ribbon 所…

修改el-checkbox样式

一定要在最外层&#xff1b; //未选中框/deep/ .el-checkbox__inner{border-color: #0862a3;}//选中框/deep/ .el-checkbox__input.is-checked .el-checkbox__inner{background-color: #0862a3;border-color: #0862a3;}//未选中框时右侧文字/deep/ .el-checkbox__label{}//选中…

认养小游戏功能介绍

认养小游戏通常模拟了真实的农业生产过程&#xff0c;让玩家能够在线上体验种植、养殖的乐趣。以下是一些常见的认养小游戏功能介绍&#xff1a; 选择认养的农产品&#xff1a;首先&#xff0c;玩家可以从游戏中提供的多种农产品中选择自己想要认养的种类&#xff0c;如蔬菜、…

JavaEE技术之MySql高级-搭建主从复制(主从同步原理、一主多从配置)

文章目录 MySQL主从同步1、MySQL主从同步原理2、一主多从配置2.1、准备主服务器2.2、准备从服务器2.3、启动主从同步2.4、实现主从同步2.5、停止和重置2.6、常见问题问题1问题2 MySQL主从同步 1、MySQL主从同步原理 基本原理&#xff1a; slave会从master读取binlog来进行数据…