【实验目的】
应用贪心算法求解活动安排问题。
【实验性质】
验证性实验（学时数：2H）
【实验内容与要求】
活动安排问题是可以用贪心算法有效求解的很好的例子。
问题：有n个活动的集合A={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。
求解：安排尽量多项活动在该场地进行，即求A的最大相容子集。
设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下：
2022-02-12 12:01:58
145KB
一．介绍贪心算法的一般步骤：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
二. 贪心算法适合解决什么样的问题
......
2022-01-23 00:40:51
47KB
1
1.Knapsack Problem
2.最优装载
3.程序存储问题
4.Maximum Tape Utilization Ratio
5.汽车加油问题
6.活动安排问题
7.硬币找零
8.整数连接
.
.
2022-01-09 21:38:45
11KB
1
Prim算法
设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树的Prim算法的基本思想是：
(1)置S={1}
(2)只要S是V的真子集，就作如下的贪心选择
选取满足条件i ∈ S，j ∈ V-S，且c[j]最小的边，将顶点j添加到S中。一直到S=V时为止。
(3)选取到的所有边恰好构成G的一棵最小生成树。
2022-01-02 10:10:17
235KB
1
基础算法实现的车辆路径问题。其中运用了三种方法。两种代码（更新前）为下面
https://blog.csdn.net/qq_44785318/article/details/110124701
2021-12-30 21:05:43
6KB
1
背包问题的贪心算法实现，简答易懂
if(m>=weight[i])
{
value=value+profit[i];
m-=weight[i];
s[i]=1;
}
else if(m!=0)
{
value=value+profit[i]*(1.0*m/weight[i]);
s[i]=1.0*m/weight[i];
m=0;
}
else break;
2021-12-30 01:41:13
596B
1
本实验报告问题描述：
0-1 背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。在选择物品i装入背包时，可以选择i的一部分，而不一定要全部装入。应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
Prim算法：一个无向连通图的生成树是一个极小连通子图，它包括图中全部的结点，并且尽可能少的边。遍历一个连通图得到图的一颗生成树。
Kruskal算法：一个无向连通图的生成树是一个极小连
2021-12-28 21:46:45
570KB
1