计算机问题求解一论题3-2 贪心算法 2022年09月14日
计算机问题求解 – 论题3-2 - 贪心算法 2022年09月14日
间题1： 你还记得什么是“Optimal Substructure”吗？该结构特 性对求解最优解间题有什么启 发？
Activity Selection Problem Activities: 口S={a1;a2;…an} wish to use a resource,which can serve only one activity at a time. oa has a start time s and a finish time fi, Compatible Activities a and a: the intervals [si;fi)and [sj;fj)do not overlap. activity-selection problem: select a maximum-size subset of mutually compatible activities
Activity Selection Problem ◼ Activities: ❑ S={a1 ; a2 ;…;an } ❑ wish to use a resource, which can serve only one activity at a time. ❑ ai has a start time si and a finish time fi, ❑ Compatible Activities ai and aj : ◼ the intervals [si; fi) and [sj; fj) do not overlap. ◼ activity-selection problem: ❑ select a maximum-size subset of mutually compatible activities
Activity Selection Problem The activities are sorted in monotonically increasing order of finish time: 一个样本输入： 00 110 11 2 26 a;ag;a:mutually compatible activities. a;a;ag;a:a largest subset of mutually compatible activities;
Activity Selection Problem 一个样本输入： The activities are sorted in monotonically increasing order of finish time: {a3 ; a9 ; a11}: mutually compatible activities. {a1 ; a4 ; a8 ; a11}: a largest subset of mutually compatible activities;
问题2： 这是一个优化问题，动态规划？ Activity Selection问题是否具有“最优 子结构”？ 构想一个最优解的结构！
构想一个最优解的结构！