精华内容
下载资源
问答
  • 活动选择问题
    千次阅读
    2016-11-12 15:00:15

    贪心算法与活动选择问题 C++实现

    贪心算法原理

    在之前的文章里,作者讲过动态规划,然而贪心算法和动态规划是有区别的:贪心算法并不是首先寻找子问题的最优解,然后再其中进行选择,而是首先做出一次“贪心”选择----在当时(局部)看来是最优的选择----然后求解选出的子问题,从而不必费心求解所有可能相关的子问题。

    贪心算法需要两个关键的要素----贪心选择性质与最优子结构。

    贪心选择性质

    我们可以通过做出局部最优选择来构造全局最优解。在动态规划中,每一步骤都要进行一次选择,但选择通常依赖于子问题的解。因此,我们通常以一种自底向上方法求解动态规划问题,先求解较小的子问题,然后是较大的问题(我们也可以带备忘的自顶向下法来求解。当然,即便使算法自顶向下进行计算,我们仍然需要先求解子问题再进行选择)。贪心算法在第一次选择之前不求解任何问题。一个动态规划问题通常是自底向上的,而贪心则是自顶向下的,进行一次又一次选择,讲个定的实例变的更小。

    最优子结构

    如果一个问题的最优解包含其子问题的最优解,则称此问题具有最优子结构性质。

    活动选择问题

    活动选择问题是用来求解一个最大的互相兼容的活动集合。假定有一个 n n n个活动的集合 S = { a 1 , a 2 , … , a n } S=\{a_1,a_2,\dots,a_n\} S={a1,a2,,an},这些活动使用同一个资源(例如一个阶梯教室),而这个资源在某一时刻只能共一个活动使用。每个活动 a i a_i ai都有一个开始时间,和一个结束时间 f i f_i fi,其中 0 ≤ s i ≤ f i < ∞ 0\leq s_i\leq f_i<\infty 0sifi<。如果被选中,任务 a i a_i ai发生在半开时间区间 [ s i , f i ) [s_i,f_i) [si,fi)期间。如果两个活动 a i a_i ai s j s_j sj满足 [ s i , f i ) [s_i,f_i) [si,fi) [ s j , f j ) [s_j,f_j) [sj,fj)不重叠,则称他们是兼容的。也就是说,若 s i ≥ f i s_i\geq f_i sifi s j ≥ f i s_j\geq f_i sjfi,则 a i a_i ai a j a_j aj是兼容的。在活动选择问题中,我们希望选出一个最大兼容活动集。

    源代码

    假定活动已经按时间结束的单调递增顺序排序:

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    //Data.
    vector<int> temp_VecS = { 0,1,3,0,5,3,5,6,8,8,2,12 }, temp_VecF = { 0,4,5,6,7,9,9,10,11,12,14,16 };
    
    //Greedy.
    vector<int> Greedy_Activity_Selector(vector<int> const &temp_VecS, vector<int> const &temp_VecF) {
    	auto temp_n = temp_VecS.size() - 1;
    	vector<int> temp_VecA = { 1 };
    	auto temp_k = 1;
    
    	for(auto temp_m = 1; temp_m <= temp_n; ++temp_m) {
    		if(temp_VecS[temp_m] >= temp_VecF[temp_k]) {
    			temp_VecA.push_back(temp_m);
    			temp_k = temp_m;
    		}
    	}
    
    	return temp_VecA;
    }
    
    int main() {
    	auto temp_Vec = Greedy_Activity_Selector(temp_VecS, temp_VecF);
    
    	for(auto &i : temp_Vec) {
    		cout << "a" << i << " ";
    	}
    
    	return 0;
    }
    
    更多相关内容
  • 活动选择问题_贪心算法

    千次阅读 2018-10-19 12:07:36
    对于许多最优化问题,使用动态规划算法来求最优解有些杀鸡用牛刀了,可以使用更加简单、更加高效的算法。贪心算法就是这样的算法,它在每一步做出当时看起来最佳的选择。也就是说它总是做出局部最优的选择,从而得到...

    贪心算法

    对于许多最优化问题,使用动态规划算法来求最优解有些杀鸡用牛刀了,可以使用更加简单、更加高效的算法。贪心算法就是这样的算法,它在每一步做出当时看起来最佳的选择。也就是说它总是做出局部最优的选择,从而得到全局最优解。

     

    对于某些问题并不保证得到最优解,但对很多问题确实可以求得最优解。

     

    思想

    贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行,根据某个优化测度,每一步都要确保能获得局部最优解。每一步只考虑一个数据,他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加算法停止 [3]  。

    过程

    1. 建立数学模型来描述问题;

    2. 把求解的问题分成若干个子问题;

    3. 对每一子问题求解,得到子问题的局部最优解;

    4. 把子问题的解局部最优解合成原来解问题的一个解。

     

    活动选择问题

    有n个需要在同一天使用同一个教室的活动a1,a2,…,an,教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后,活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠,ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行(最大兼容活动子集)。例如下图所示的活动集合S,其中各项活动按照结束时间单调递增排序。

     

    {a3,a9,a11}是一个兼容的活动子集,但它不是最大子集,因为子集{a1,a4,a8,a11}更大,实际上它是我们这个问题的最大兼容子集,但它不是唯一的一个{a2a4a9a11}

    贪心算法

      想要使用贪心算法的话,得先找到适合贪心算法的规律(局部最优选择)

      对于任何非空的活动集合S,假如amS中结束时间最早的活动,则am一定在S的某个最大兼容活动子集中。

    (如何证明上面的结论?反证法)

     

      递归解决

      迭代解决

     

        static void Main(string[] args)
            {
                int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
                int[] f = { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
    
                List<int> list = ActivitySelection(1, 11, 0, 24, s, f);
                foreach (int item in list)
                {
                    Console.Write(item + " ");
                }
            }
    
    static List<int> ActivitySelection(int startNum, int endNum, int startTime, int endTime, int[] s,int [] f)
            {
                if (startNum>endNum||startTime>=endTime)
                {
                    return new List<int>();
                }
    
                int tempNum=0;
                //从第一个开始找
                for (int number = startNum; number <=endNum; number++)
                {
                    if (s[number]>=startTime&&f[number]<=endTime ) //在开始和 结束的 活动时间 区间内
                    {
                        //找到了
                        tempNum = number;
                        break;
                    }
                }
                // 找 剩余的
                 List<int> Activitylist= ActivitySelection(tempNum + 1, endNum, f[tempNum], endTime,s, f);
    
                 Activitylist.Add(tempNum);
                return Activitylist;
            }

      迭代解决

     static void Main(string[] args)
            {
                int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 24 };
                int[] f = { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24 };
    
                int startTime = 0;
                int endTime = 24;
                List<int> list = new List<int>();
                for (int number = 1; number <=11; number++)
                { 
                   //说明 活动
                    if (s[number]<=startTime&&f[number]<=endTime)
                    {
                        list.Add(number);
                        startTime = f[number];//下次判断的时候就是从下次的
                        //结束时间判断
                    }
                }
                foreach (int i in list)
                {
                    Console.WriteLine(i);
                }
            }

     

    展开全文
  • 【算法导论】贪心算法之活动选择问题

    万次阅读 多人点赞 2015-01-27 20:43:22
    贪心算法解决活动选择问题

            动态规划总是在追求全局最优的解,但是有时候,这样有点费时。贪心算法,在求解过程中,并不追求全局最优解,而是追求每一步的最优,所以贪心算法也不保证一定能够获得全局最优解,但是贪心算法在很多问题却额可以求得最优解。


     一、问题概述


            活动选择问题:


            假定一个有n个活动(activity)的集合S={a1,a2,....,an},这些活动使用同一个资源(例如同一个阶梯教室),而这个资源在某个时刻只能供一个活动使用。每个活动ai都有一个开始时间si和一个结束时间fi,其中0<=si<fi<正无穷。如果被选中国,任务ai发生在半开时间区间[si,fi)期间。如果两个活动ai和aj满足[si,fi)和[sj,fj)不重叠,则称它们是兼容的。也就说,若si>=fj或sj>=fi,则ai和aj是兼容的。在活动选择问题中,我们希望选出一个最大兼容活动集。假定活动已按结束时间fi的单调递增顺序排序:


                                                                                            f1<=f2<=f3<=f4<=...<=fn-1<=fn

            例如,考虑下面的活动集合:


            


            可以看到,{a3,a9,a11}是由相互兼容的活动组成。但它不是一个最大集,{a1,a4,a8,a11}更大,是一个最大集,最大集可以有多个不同的。


            假设:Sij表示在ai结束之后,在aj开始之前的活动的集合。Aij表示Sij的一个最大相互兼容的活动子集。那么只要Sij非空,则Aij至少会包含一个活动,假设为ak。那么可以将Aij分解为:Aij = Aik+ak+Akj。假设Cij为Aij的大小,那么有Cij=cik+ckj+1。

            

            但是我们并不知道具体是k等于多少的时候,可以让ak一定位于Aij中,所以我们采用动态规划的方式,遍历所有可能的k值,来取得。于是有:


            


            接下来,如果按照动态规划的方式,就可以采用自底向上的递归来求解最优的解。


    二、贪心算法


            但是贪心算法却要简单许多,贪心算法直接在每一步选择当前看来最好的选择。比如在一开始的时候,我们要选择在Aij中的第一个活动,我们选择活动结束时间最早的那个活动,这样能够给其他活动尽可能的腾出多余的时间。而后每一步都在剩下的活动中选取,也遵循类似的原则。由于获取已经按照fi排序好,所以这里第一个选择的活动就是a1。但是问题来了,我们能否确定a1一定在Aij中呢,在这个问题中,答案是肯定的,可以给出简单的证明:


            假设Aij是Sij的某个最大兼容活动集,假设Aij中,最早结束的活动是an,分两种情况:


            ①如果an=a1,则得证


            ②如果an不等于a1,则an的结束时间一定会晚于a1的结束时间,我们用a1去替换Aij中的an,于是得到A`,由于a1比an结束的早,而Aij中的其他活动都比an的结束时间开始 的要晚,所以A`中的其他活动 都与a1不想交,所以A`中的所有活动是兼容的,所以A`也是Sij的一个最大兼容活动集。


            于是证明了命题。


    根据上面的结论,我们可以给出贪心算法在解决这个问题的两种方式:递归和迭代方式,两种算法都是按照自顶向下来求解问题的。


    递归方式:


    /*
     * 递归版本
     */
    void Recursive_Activity_Selector(vector<int>* A, int* s, int* f, int k, int n) {
    
    	int m = k + 1;
    	while (m <= n && s[m] < f[k]) {
    		m++;
    	}
    
    	if (m <= n) {
    		A->push_back(m);
    		Recursive_Activity_Selector(A, s, f, m, n);
    	}
    }



    迭代方式:


    /*
     * 迭代版本
     */
    vector<int>* Greedy_Activity_Selector(int*s, int*f, int n) {
    	vector<int>* A = new vector<int>;
    
    	int k = 1;
    	A->push_back(k);
    
    	for (int m = 2; m <= n; m++) {
    		if (s[m] >= f[k]) {
    			A->push_back(m);
    			k = m;
    		}
    	}
    
    	return A;
    }



    三、算法复杂度分析:


            假设实现活动已经按照fi的升序排列好了的话,会发现实际上贪心算法在处理这个问题的时候只做了一次遍历,所以算法复杂度为O(n)。


    完整代码:


    /*
     * 活动选择问题:
     *
     * 调度竞争共享资源的多个活动的问题,目标是选出一个最大的互相兼容的活动集合。假定有一个n个活动的集合S={a1,a2,a3...,an},
     * 这些活动使用同一个资源(例如同一个阶梯教室),而这个资源在某个时刻只能供一个活动使用。每个互动ai都有一个开始时间s和一个结束时间fi,
     * 其中)<=si<fi<无穷。如果被选中,任务ai发生在半开时间区[si,fi)期间。如果两个活动ai和aj满足[si,fi)和[sj,fj)不重叠,则称它们是兼容的。
     * 也就是说,若si>=fj,或sj>=fi,则ai和j是兼容的。在活动选择问题中,我们希望选出一个最大兼容活动集。假定活动已按照结束时间的单调递增
     * 排序
     *
     * 原本的思路:按照动态规划的方法来求,先求子问题:将Sij的一个最大兼容活动集合设为Aij,于是Aij至少包含一个活动ak,则:
     * 可以将Aij划分为子问题:Aij=Aik+ak+Akj
     *
     * 但是我们一开始不能知道哪一个k能够使得ak一定在最大兼容活动集Aij中,于是一般的需要从i~j便利所有的k的可能取值,来找这个ak。
     *
     * 上面是动态规划的思路;但是对于贪心算法而言,这里ak不去 遍历,而只是去寻找第一个结束的活动,也就是a1。这里可以证明,a1一定是在
     * Sij的某一个最大兼容活动集Aij中。证明方法:
     *
     * 假设Aij是Sij的某个最大兼容活动集,假设Aij中,最早结束的活动是an,分两种情况:
     *
     * ①如果an=a1,则得证
     * ②如果an不等于a1,则an的结束时间一定会晚于a1的结束时间,我们用a1去替换Aij中的an,于是得到A`,由于a1比an结束的早,而Aij中的其他活动
     * 都比an的结束时间开始 的要晚,所以A`中的其他活动 都与a1不想交,所以A`中的所有活动是兼容的,所以A`也是Sij的一个最大兼容活动集。
     *
     * 得证
     *
     * 于是我们下面使用贪心算法来做,分别用递归和迭代两个版本。
     *
     */
    
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    void swap(int* a, int* b) {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int Adjust_Arr(int* a, int* b, int start, int end) {
    
    	int p = start;
    	int q = end;
    	int i = p - 1;
    	int j = p;
    
    	int key = a[q];
    
    	while (j < q) {
    		if (a[j] >= key) {
    			j++;
    			continue;
    		} else {
    			i++;
    			swap(a + i, a + j);
    			swap(b + i, b + j);
    			j++;
    		}
    	}
    
    	i++;
    	swap(a + i, a + q);
    	swap(b + i, b + q);
    	return i;
    }
    
    void Quick_Sort(int* a, int* b, int start, int end) {
    	if (start < end) {
    		int mid = Adjust_Arr(a, b, start, end);
    		Quick_Sort(a, b, start, mid - 1);
    		Quick_Sort(a, b, mid + 1, end);
    	}
    }
    
    void Print_Arr(int* a, int len) {
    	for (int i = 0; i < len; i++) {
    		cout << a[i] << ' ';
    	}
    	cout << endl;
    }
    
    /*
     * 递归版本
     */
    void Recursive_Activity_Selector(vector<int>* A, int* s, int* f, int k, int n) {
    
    	int m = k + 1;
    	while (m <= n && s[m] < f[k]) {
    		m++;
    	}
    
    	if (m <= n) {
    		A->push_back(m);
    		Recursive_Activity_Selector(A, s, f, m, n);
    	}
    }
    
    /*
     * 迭代版本
     */
    vector<int>* Greedy_Activity_Selector(int*s, int*f, int n) {
    	vector<int>* A = new vector<int>;
    
    	int k = 1;
    	A->push_back(k);
    
    	for (int m = 2; m <= n; m++) {
    		if (s[m] >= f[k]) {
    			A->push_back(m);
    			k = m;
    		}
    	}
    
    	return A;
    }
    
    int main() {
    
    	int s[12] = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12 };
    
    	int f[12] = { 0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16 };
    
    	//先将f按从小到大排序,s的位置随f而动
    	Quick_Sort(f, s, 0, 12 - 1);
    
    //	vector<int>* A = new vector<int>;
    //	Recursive_Activity_Selector(A, s, f, 0, 12 - 1); //这里实际上下标只能取到11
    
    	vector<int>* A = Greedy_Activity_Selector(s, f, 12 - 1);
    
    	cout << "===========" << endl;
    	vector<int>::iterator iter;
    
    	for (iter = A->begin(); iter != A->end(); iter++) {
    		cout << *iter << ' ';
    	}
    	cout << endl << "===========" << endl;
    
    	delete A;
    
    	return 0;
    }
    



    展开全文
  • 贪心算法之活动选择问题

    千次阅读 2019-04-17 17:05:09
    活动选择问题:假定有一个n个活动的集合,这些活动使用同一个资源,而这个资源在某个时刻只能供一个活动使用。每个活动都有一个开始时间和一个结束时间,其中.如果被选中,任务发生在半开时间区间期间。如果两个活动...

    活动选择问题:假定有一个n个活动的集合S=\left \{ a_{1},a_{2},...,a_{n} \right \},这些活动使用同一个资源,而这个资源在某个时刻只能供一个活动使用。每个活动a_{i}都有一个开始时间s_{i}和一个结束时间f_{i},其中0\leqslant s_{i}< f_{i}< \infty.如果被选中,任务a_{i}发生在半开时间区间[s_{i},f_{i})期间。如果两个活动a_{i}a_{j}满足[s_{i},f_{i})[s_{j},f_{j})不重叠,则称它们是兼容的。也就是说,若s_{i}\geqslant f_{j}s_{j}\geqslant f_{i},则a_{i}a_{j}是兼容的。在活动选择问题中,我们希望选出一个最大兼容活动集。假定活动已按结束时间的单调递增顺序排序:

    f_{1}\leqslant f_{2}\leqslant f_{3}\leqslant ...\leqslant f_{n-1}\leqslant f_{n}

    考虑下面的活动集合S:

    i1234567891011
    s_{i}130535688212
    f_{i}4567891011121314

    其最大兼容活动子集是\left \{ a_{1},a_{4},a_{8},a_{11} \right \}\left \{ a_{2},a_{4},a_{9},a_{11} \right \}

    如图所示:

    最优子结构:S_{ij}表示在a_{i}结束之后开始,且在a_{j}开始之前结束的那些活动的集合。假定我们希望求S_{ij}的一个最大的相互兼容的活动子集,进一步假定A_{ij}就是这样一个子集,包含活动a_{k}.由于最优解包含活动a_{k},我们得到两个子问题:寻找S_{ik}中的兼容活动(在a_{i}结束之后开始且a_{k}开始之前结束的那些活动)以及寻找S_{kj}中的兼容活动(在a_{k}结束之后开始且a_{j}开始之前结束的那些活动)。

    这样刻画活动选择问题的最优子结构,意味着我们可以用动态规划方法求解活动选择问题。如果用c\left [ i,j \right ]表示集合S_{ij}的最优解的大小,则可得递归式c\left [ i,j \right ]=c\left [ i,k \right ]+c\left [ k,j \right ]+1

    当然,如果不知道S_{ij}的最优解包含活动a_{k},就需要考察S_{ij}中所有活动,寻找哪个活动可获得最优解,于是

    c\left [ i,j \right ]=\left\{\begin{matrix} 0\;\; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \;\; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; ,\; if\; S_{ij}= \varnothing \\ max_{i< k< j}\left \{ c\left [ i,j \right ]+c\left [ k,j \right ]+1 \right \},\; if\; S_{ij}\neq \varnothing \end{matrix}\right.

    贪心选择:直观上,我们应该选择这样一个活动,选出它后剩下的资源应能被尽量多的其他任务所用。现在考虑可选的活动,其中必然有一个最先结束。因此,直觉告诉我们,应该选择S中最早结束的活动,因为它剩下的资源可供它之后尽量多的活动使用。

    定理16.1:考虑任意非空子问题S_{k},令a_{m}S_{k}中结束时间最早的活动,则a_{m}S_{k}的某个最大兼容活动子集中。

    贪心算法通常都是自顶向下的设计:做出一个选择,然后求解剩下的那个子问题,而不是自底向上地求解出很多子问题,然后再做出选择。

    递归贪心算法:输入为两个数组s和f,表示活动的开始和结束时间,下标k指出要求解的子问题S_{k},以及问题规模n。返回S_{k}的一个最大兼容活动集。假定输入的n个活动已经按结束时间的单调递增顺序排列好。

    def RecursiveActivitySelector(s, f, k, n, A):
        m = k + 1
        while m <= n and s[m] < f[k]:
            m += 1
        if m <= n:
            A.append(m)
            return RecursiveActivitySelector(s, f, m, n, A)
        else:
            return A

    其运行时间是\Theta (n)

    迭代贪心算法:将选出的活动存入集合A中,并将A返回调用者。

    def GreedyActivitySelector(s, f):
        n = len(s)
        A = [1]
        k = 1
        for m in range(2, n):
            if s[m] >= f[k]:
                A.append(m)
                k = m
        return A

    其运行时间是\Theta (n)

    使用两个版本的贪心算法各自查找S中的最大兼容活动集:

    from RecursiveActivitySelector import RecursiveActivitySelector
    from GreedyActivitySelector import GreedyActivitySelector
    
    A = []
    s = [0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12]
    f = [0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16]
    n = 11
    
    print(RecursiveActivitySelector(s, f, 0, n, A))
    print(GreedyActivitySelector(s, f))

    输出结果为:

    [1, 4, 8, 11]
    [1, 4, 8, 11]
    

    结果正确

     

    展开全文
  • 问题描述 i为任务id,s是开始时间,f是结束时间 问题求解
  • 活动选择问题(贪心算法vs动态规划)

    万次阅读 多人点赞 2015-05-01 16:25:46
    活动选择问题贪心算法vs动态规划 基础知识 1-1动态规划 1-2贪心算法 1-3贪心算法vs动态规划 活动选择问题描述 活动选择问题最优子结构 活动选择问题算法设计4-1贪心算法之选择最早结束活动 4-1-1递归贪心算法 4-1-2...
  • 书中先从活动选择问题来引入贪心算法,分别采用动态规划方法和贪心算法进行分析。本篇笔记给出活动选择问题的详细分析过程,并给出详细的实现代码进行测试验证。关于贪心算法的详细分析过程,下次在讨论。 1、...
  • 贪心法——活动选择问题和背包问题

    千次阅读 热门讨论 2014-10-23 20:19:32
    今天上午听了米老师讲的算法,感觉收获很多,对于算法更加有信心了...分治法是这三种算法里面都有的思想,动态规划和贪心都是将问题分解成子问题求解,但动态规划里面的子问题都带有联系,而贪心算法里面的子问题都...
  • 【算法导论】用动态规划解活动选择问题

    千次阅读 多人点赞 2015-01-28 22:19:11
    上一篇讲了贪心算法来解活动选择问题(【算法导论】贪心算法之活动选择问题),发现后面有一道练习16.1-1是要用动态规划来解活动选择问题。其实跟之前的矩阵链乘法有些相似,也是考虑分割的活动是哪一个,并用二维数据...
  • 活动选择问题 有一个教室,而当天有多个活动,活动时间表如下:找出最大兼容活动集!活动已按结束时间升序排序. 动态规划 采用动态规划需要满足两个条件:1.最优子结构2.子问题重叠 令SijS_{ij}表示在aia_i...
  • 问题描述:  有一个需要使用每个资源的n个活动组成的集合S= {a1,a2,···,an },资源每次只能由一个活动使用。每个活动a都有一个开始时间和结束时间,且 0 动态规划: 一、  定义子集合Sij = { ak S...
  • 活动选择问题的最优子结构: Sij={ak∈S : fi Sij是S中活动的子集,其中每个活动都在a_i结束之后开始,且在a_j开始之前结束。 设活动按结束时间的单调递增顺序排序f0 断言,当i>=j时,Sij=∅。 最优...
  • // 活动选择问题(活动安排问题)(最大数目活动选择问题).cpp : Defines the entry point for the console application. //贪心算法 #include "stdafx.h" #include #define N 100 using namespace std; struct ...
  • 今天偶然在解决活动选择问题时遇到了一些麻烦,经过查资料和仔细分析后,总结如下,如果哪些地方有错,请指正,谢谢!1. 动态规划算法(Dynamic Programming Algorithm)动态规划其实和分治策略是类似的,也是将一...
  • 贪心算法之活动安排问题C语言代码

    千次阅读 2021-11-20 18:17:07
    贪心算法之活动安排问题C语言 问题描述 该问题要求高效地安排一系列争用某一公共资源的活动。 n:活动的个数,其中每个活动都要求使用同一资源,如演讲会场等。而且在同一时间内只有一个活动能使用这一资源。 i:...
  • 活动选择问题是《算法导论》里面关于贪心算法的第一个问题。这个问题是这样的。我们有一组活动,每个活动都有一个开始时间Si和结束时间Fi。如下图:每个活动都共享同一个公共的资源(比如教室等)所以同一时间只能有...
  • 问题描述和分析:《算法导论》p222——16.1活动选择问题.这里给出了动态规划和贪心算法两种算法的代码:动态规划解法:#include using namespace std;const int N = 11;int s[N+2];int f[N+2];int trace[N+2][N+2];/...
  • Greedy——活动选择问题

    千次阅读 2012-02-03 22:18:59
    活动选择问题:就是给定一组活动的开始时间和结束时间,然后他们都需要使用到一个资源,这个资源每次只有一个活动可以用,要求求出一个最大的相互兼容的活动子集。 首先定义了一个集合Sij = {ak∈ S :fi ≤ sk ...
  • 活动选择问题变形一:活动全选择问题
  • 有一个由n个活动组成的集合S = {a1, ..., an}  1. 这些活动使用同一个资源,而这个资源在某一时刻只供一个活动使用  2. 每个活动都有一个开始和结束... 活动选择问题,希望选出一个最大兼容活动集  假设活动已
  • (Java实现) 活动选择

    千次阅读 2019-06-02 08:34:00
    活动选择的类似问题都可以这么写 import java.util.ArrayList; public class huodo...
  • 题目活动选择问题解决代码及点评// 活动选择问题.cpp : 定义控制台应用程序的入口点。 // #include #define N 100 using namespace std; struct Activity { int number; //活动编号 int begin; //活动开始...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 450,291
精华内容 180,116
关键字:

活动选择问题

友情链接: highlight.zip