算法分析与设计实验报告

算法分析与设计实验报告Tag内容描述：<p>1、0-1背包问题的多种算法设计与分析一、实验内容和要求： 0-1背包问题是一例典型的组合优化的NP完全问题。问题可以描述为：给定一组共n个物品，每种物品都有自己的重量wi, i=1n和价值vi, i=1n，在限定的总重量（背包的容量C）内，如何选择才能使得选择物品的总价值之和最高。选择最优的物品子集放置于给定背包中，最优子集对应n元解向量(x1,xn), xi0或1，因此命名为0-1背包问题。0-1背包问题是许多问题的原型，但它又是一个NP完全问题。此实验主要研究和实现n(0=n=200)和C(C=2000, C为整数)都较大的情形，随机产生n个物品的重量向量wi(1=wi=。</p><p>2、算法分析大型实验报告编号标题算法题目一1005Jugs模拟题目二1007Do the Untwist字符串班 级：姓 名：学 号：指导老师：2011年8月ZJUT-1005 Jugs浙江大学，Turing Cup 2001，http:/acm.zju.edu.cn/show_problem.php?pid=1005Special JudgeTime limit: 1 Seconds Memory limit: 32768KIn the movie Die Hard 3, Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug and were asked to fill the 5-g。</p><p>3、安 徽 工 业 大 学专 业：班 级：姓 名：学 号：实验一：回溯法完成0-1背包问题代码如下：#include stdafx.h#include#include#include#includeusing namespace std;templateclass Knappublic:friend void Init();friend void Knapsack();friend void Backtrack(int i);friend float Bound(int i);bool operator a)constif(fla.fl) return true;else return fal。</p><p>4、项目序号1项目名称分治法实验成绩小标题找最大值和最小值1、 方法思想分治法是把规模大的问题，分割成n个形式相同规模一定或不可再分的子问题，递归地解决每个子问题，再把子问题的结果汇总，合并得到原问题的解。分治法在每一层递归上由三个步骤组成： (1) 划分(divide)：将原问题分解为若干规模较小、 相互独立、 与原问题形式相同的子问题。 (2) 解决(conquer)： 若子问题规模较小，则直接求解；否则递归求解各子问题。 (3) 合并(combine)： 将各子问题的解合并为原问题的解。 2、问题描述我们将分治策略用于此问题，每次将问题分成大。</p><p>5、计算机算法与设计分析实验报告班级： 姓名：学号：目录实验一 分治与递归 11、基本递归算法12、棋盘覆盖问题23、二分搜索34、实验小结5实验二 动态规划算法 51、最长公共子序列问题 52、最大子段和问题73、实验小结8实验三 贪心算法 81、多机调度问题。</p><p>6、课程名称： 算法分析与设计 学 号： 08220429 姓 名： 王 洪 朋 专业班级： （非师范）计算机科学与技术081 学 院： 数理与信息工程学院 指导老师： 宋 炯 数理与信息工程学院实验一 递归与分治策略一、实验目的1、熟练掌握递归与分治策略的思想并应用其解决实际问题。2、利用递归与分治策略的思想解决Gray码问题。二、实验要求Gray码是一个长度为2n的序列。序列中无相同元素，每个元素都是长度为n 位的串，相邻元素恰好只有1位相同。用分治策略设计一个算法对任意的n构造相应的Gray码。三、算法实现#include using namespace std;void pr。</p><p>7、算法分析与设计课程实验报告班 级： 131213 学 号： 13121XXX 姓 名： XXX 指导老师： 邓 凡 目录算法分析与设计课程实验报告1实验一 排序11. 课本练习2.3-712. 实现优先队列23.快速排序24. 第k大元素3实验二 动态规划41. 矩阵链乘42. 最长公共子序列53. 最长公共子串74. 最大和95. 最短路径10实验三 贪心策略111. 背包问题112. 任务调度143. 单源点最短路径154. 任意两点间最短路径16实验四 回溯法181. 0-1背包问题182. 8-Queen问题21实验一 排序1. 课本练习2.3-7(1) 问题描述描述一个运行时间为(nlgn)的算法，给定n个整数的集合S和另一。</p><p>8、排序问题求解 实验日志实验题目：排序问题求解实验目的：1）以排序（分类）问题为例，掌握分治法的基本设计策略。2）熟练掌握一般插入排序算法的实现；3）熟练掌握快速排序算法的实现；4) 理解常见的算法经验分析方法；实验要求：1. 生成实验数据.要求：编写一个函数datagenetare，生成2000个在区间1,10000上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为后面算法的实验数据。2. 实现直接插入排序算法.3. 实现快速排序算法.实验主要步骤：#include#include#include#include#define RAND_MAX 10000#define Max 1000int I_Ch。</p>