做流量网站挂广告还能挣钱吗,网络营销方式ppt,网站建设_app开发,备案用的网站建设规划书怎么写目录
一、【实验目的】
二、【实验内容】
三、实验源代码 一、【实验目的】
#xff08;1#xff09;熟悉贪心法的设计思想
#xff08;2#xff09;理解贪心法的最优解与正确性证明之间的关系
#xff08;3#xff09;比较活动选择的各种“贪心”策略#xff0c;…目录
一、【实验目的】
二、【实验内容】
三、实验源代码 一、【实验目的】
1熟悉贪心法的设计思想
2理解贪心法的最优解与正确性证明之间的关系
3比较活动选择的各种“贪心”策略探讨最优算法。
二、【实验内容】
有n项活动申请使用同一场所每项活动有一个开始和结束时间如果任何两个活动不能重叠问如何选择这些活动使得被安排活动数量达到最多。
要求选择两项“贪心”策略进行比较其中一个是最优的。建议最优算法参考教材P88的算法4.1.同时可以采用教材例4.1的数据进行验证。
三、实验源代码
#include bits/stdc.h
using namespace std;
//有n个需要在同一天使用同一个教室的活动a1, a2, …, an
//教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi。
//一旦被选择后活动ai就占据半开时间区间[si, fi)。如果[si, fi]和[sj, fj]互不重叠
//ai和aj两个活动就可以被安排在这一天。
//该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。《算法导论》struct activity
{int start;int end;
}a[200];int n;
vectoractivity set1, set2;//比较函数按结束时间排序
bool cmp1(activity x, activity y)
{if (x.end y.end)return x.start y.start;//不能加等于号会报错return x.end y.end;
}
//比较函数按开始时间排序
bool cmp2(activity x, activity y)
{return x.start y.start;//不能加等于号会报错
}int strategy1() //最佳策略
{sort(a, a n, cmp1);int cnt 1;//第一个活动已经选了所以初始是1 1,4int j 0;set1.push_back(a[0]);for (int i 1; i n; i){if (a[j].end a[i].start){cnt;j i;set1.push_back(a[i]);}}return cnt;
}int strategy2() //按开始时间排序策略
{sort(a, a n, cmp2);int cnt 1;//第一个活动已经选了所以初始是1 0,6int j 0;set2.push_back(a[0]);for (int i 1; i n; i){if (a[j].end a[i].start){cnt;j i;set2.push_back(a[i]);}}return cnt;
}int main()
{cin n;for (int i 0; i n; i){cin a[i].start a[i].end;}cout 策略1选择活动数量 strategy1() endl;cout 活动为;for (auto e : set1){cout ( e.start , e.end ) ;}cout endl;cout 策略2选择活动数量 strategy2() endl;cout 活动为;for (auto e : set2){cout ( e.start , e.end ) ;}
}
/*
input:
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13
*/
【输出结果】
