文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 算法设计与分析习题集
侵权投诉

算法设计与分析习题集

一、假设有7个物品,它们的重量和价值如下表所示。若这些物品均不能被分割,且背包容量M

=150,使用回溯方法求解此背包问题。请写出状态空间搜索树(20分)。

算法设计与分析习题集

答:按照单位效益从大到小依次排列这7个物品为:FBGDECA。将它们的序号分别记为1~7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得:【排序1分】

算法设计与分析习题集

x5 x6 x7 每个节点1分】

17分,

a.40 40 30 50 35 150 115 190.625 (1,1,1,1,7,0,0)

40

8

b. 40 40 30 50 30 150 115 177.5(1,1,1,1,0,7,0)

60

12

c.40 40 30 50 10 170

60

(1,1,1,1,0,0,1)

4

d. 40 40 30 35 30 150 105 167.5 (1,1,1,0,1,3,0) e. 40 40 50 35 30 150 130 175

60

1

(1,1,0,1,1,,0)

3

4 (1,1,0,1,1,0,)7

f. 40 40 50 35 10 150 130 170.71

35

g. 40 40 50 30 160

(1,1,0,1,0,1,0)

第1页

你可能喜欢

  • 算法设计与分析期末考试题
  • 算法设计与分析第三版王晓东
  • 计算机算法设计与分析
  • 递归算法
  • C语言经典算法
  • C语言经典程序
  • 算法设计与分析第二版答案

热门文档

相关文档

  • 算法设计与分析习题集—第1章 算法引论(补:倒推法、蛮...

    算法设计与分析习题集—第1章 算法引论(补:倒推法、蛮力法) 隐藏>> 一、填空题: 1、算法运行所需要的计算机资源的量,称为算法复杂性,主要包括时间复杂度 ...

  • 算法分析与设计习题集

    序号 项目名称 任务描述 设计要求 1. C 语言 词法分 析算法 设计与 实现 编制一个读单词过程,从输入的源程序中,识别出各个具有 用 Java 语言,或者 C 语 ...

  • 算法设计与分析-习题集

    算法设计与分析-习题集 隐藏>> 第一章 3. 最大公约数为 1。快 1414 倍。 程序 1-2 的 while 循环体做了 10 次,程序 1-3 的 while 循环体做了 ...

  • 算法分析与设计习题集整理

    算法分析与设计习题集整理_理学_高等教育_教育专区。算法分析与设计复习习题算法分析与设计习题集整理 第一章算法引论 一、填空题: 1、算法运行所需要的计算机资源...

  • 算法设计与分析课后习题集答案

    算法设计与分析课后习题集答...算法设计与分析课后习题集答案 今日推荐 68份文档 新市场营销法则 助推企业成长...

  • 算法分析与设计习题集

    算法分析与设计习题集基础篇 1、 算法有哪些特点?它有哪些特征?它和程序的主要区别是什么? 2、 算法的时间复杂度指的是什么?如何表示? 3、 算法的空间复杂度...

  • 《算法设计与分析》课后习题

    《算法设计与分析》课后习题 隐藏>> 算法设计与分析-第四章 排序 姓名:王强 学号:20509345 4.1: 在我们所了解的早期排序算法之中有一种叫做 Maxsort 的算法...

  • 算法设计与分析

    习题集习题集隐藏>> 算法设计与分析期末综合实验试题清单分治与递归 1-1 合并排序 问题描述:给定 n 个整数,利用合并排序思想将其调整成单调序列。 输入:整数的...

  • 算法设计与分析 考试题

    ③ 分析最好情况、最坏情况下的时间复杂度。 2 2010-2011 学年第一学期 算法设计与分析》试卷( 第一学期《 2010-2011 学年第一学期《算法设计与分析》试卷(A...

  • java算法分析习题集

    java算法分析习题集有很多题,从易到难,多练习,循环渐进,慢慢提高,提高思维能力。隐藏>> 序号 项目名称 任务描述 设计要求 1. C 语言 词法分 析算法 设计与 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email