今天开始快速过一遍贪心贪心要比动态规划简单许多但是我们也要理解其中的证明过程

 贪心算法采用自顶向下以迭代的方法做出相继的贪心选择每做一次贪心选择就将所求问题简化为一个规模更小的子问题通过每一步贪心选择可得到问题的一个最优解虽然每一步上都要保证能获得局部最优解但由此产生的全局解有时不一定是最优的所以贪婪法不要回溯。能够用贪心算法求解的问题一般具有两个重要特性贪心选择性质和最优子结构性质。

一共只有6个粒子都是很经典的粒子

顾名思义贪心总是做出在当前看来最好的选择贪心不会从整体上考虑最优知识在某种意义上的局部最优。

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合是可以用贪心算法有效求解的很好例子。

问题描述

不同活动使用一个资源什么是相容的活动

设有n个活动的集合E={1,2,…,n}其中每个活动都要求使用同一资源如演讲会场等而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交则称活动i与活动j是相容的。也就是说当si≥fj或sj≥fi时活动i与活动j相容。

问题分析

  若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi则不选择活动i否则选择活动i加入集合A中。贪心算法并不总能求得问题的整体最优解。但对于活动安排问题贪心算法greedySelector却总能求得的整体最优解即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。

证明如下设E=｛012…n-1｝为所给的活动集合。

由于E中活动安排安结束时间的非减序排列所以活动0具有最早完成时间。

首先证明活动安排问题有一个最优解以贪心选择开始即该最优解中包含活动0.

设a是所给的活动安排问题的一个最优解且a中活动也按结束时间非减序排列a中的第一个活动是活动k。

如k=0则a就是一个以贪心选择开始的最优解。

若k>0则我们设b=a-｛k｝∪｛0｝。

由于end[0] ≤end[k],且a中活动是互为相容的故b中的活动也是互为相容的。

又由于b中的活动个数与a中活动个数相同且a是最优的故b也是最优的。

也就是说b是一个以贪心选择活动0开始的最优活动安排。

因此证明了总存在一个以贪心选择开始的最优活动安排方案也就是算法具有贪心选择性质。

 该算法的贪心选择意义是 使得剩余可以安排的时间最大化

这个贪心算法每次都有 最早 的完成时间 的相容活动加入到答案集合中当然他的效率是非常高的只需要On的时间就可以安排最多的相容活动使用同一个资源如果需要排序那至少需要Onlogn的时间重排。

代码

//4d1 活动安排问题 贪心算法
#include <iostream> 
using namespace std; 
 
template<class Type>
void GreedySelector(int n, Type s[], Type f[], bool A[]);
 
const int N = 11;
 
int main()
{
	//下标从1开始,存储活动开始时间
	int s[] = {0,1,3,0,5,3,5,6,8,8,2,12};
 
	//下标从1开始,存储活动结束时间
	int f[] = {0,4,5,6,7,8,9,10,11,12,13,14};
 
	bool A[N+1];
 
	cout<<"各活动的开始时间,结束时间分别为"<<endl;
	for(int i=1;i<=N;i++)
	{
		cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
	}
	GreedySelector(N,s,f,A);
	cout<<"最大相容活动子集为"<<endl;
	for(int i=1;i<=N;i++)
	{
		if(A[i]){
			cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
		}
	}
 
	return 0;
}
 
template<class Type>
void GreedySelector(int n, Type s[], Type f[], bool A[])
{
	A[1]=true;
	int j=1;//记录最近一次加入A中的活动
 
	for (int i=2;i<=n;i++)//依次检查活动i是否与当前已选择的活动相容
	{
		if (s[i]>=f[j])
		{ 
			A[i]=true;
			j=i;
		}
		else
		{
			A[i]=false;
		}
	}
}

写在后面

 1)贪心选择性质

     所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行以迭代的方式作出相继的贪心选择每作一次贪心选择就将所求问题简化为规模更小的子问题。

     对于一个具体问题要确定它是否具有贪心选择性质必须证明每一步所作的贪心选择最终导致问题的整体最优解。

证明的大致过程为

首先考察问题的一个整体最优解并证明可修改这个最优解使其以贪心选择开始。

做了贪心选择后原问题简化为规模更小的类似子问题。

然后用数学归纳法证明通过每一步做贪心选择最终可得到问题的整体最优解。

其中证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。

2)最优子结构性质

      当一个问题的最优解包含其子问题的最优解时称此问题具有最优子结构性质。

(3)贪心算法与动态规划算法的差异

     动态规划和贪心算法都是一种递推算法均有最优子结构性质通过局部最优解来推导全局最优解。两者之间的区别在于贪心算法中作出的每步贪心决策都无法改变因为贪心策略是由上一步的最优解推导下一步的最优解而上一部之前的最优解则不作保留贪心算法每一步的最优解一定包含上一步的最优解。动态规划算法中全局最优解中一定包含某个局部最优解但不一定包含前一个局部最优解因此需要记录之前的所有最优解。
举例子

 

 十分简单的一个贪心也要搞清楚为什么这个可以用贪心。

 用动态规划怎么写呢

c[i][j]表示从活动i到活动j的最大兼容子集中的活动数下标从1开始

递推方程

c[i][j] = c[i][k] + c[k][j] + 1 ;

条件 f[i] <= s[k] && f[k] <= s[j]ak与aiaj相容c[i][j] < c[i][k] + c[k][j] + 1 k有j-i种选择

初始化为 c[i][j]=0

设c[i][j]为Sij中最大兼容子集中的活动数目当Sij为空集时c[i][j]=0当Sij非空时若ak在Sij的最大兼容子集中被使用则则问题Sik和Skj的最大兼容子集也被使用故可得到c[i][j] = c[i][k]+c[k][j]+1。

当i≥j时Sij必定为空集否则Sij则需要根据上面提供的公式进行计算如果找到一个ak则Sij非空此时满足fi≤sk且fk≤sj找不到这样的ak则Sij为空集。

 

#include <bits/stdc++.h>
#define max_size 10010
int s[max_size];
int f[max_size];
int c[max_size][max_size];
int ret[max_size][max_size];

using namespace std;

void DP_SELECTOF(int *s,int *f,int n,int c[][max_size],int ret[][max_size])
{
    int i,j,k;
    int temp;
    for(j=2;j<=n;j++)
        for(i=1;i<j;i++)
        {
            for(k=i+1;k<j;k++)
            {
                if(s[k]>=f[i]&&f[k]<=s[j])
                {
                    temp=c[i][k]+c[k][j]+1;
                    if(c[i][j]<temp)
                    {
                        c[i][j]=temp;
                        ret[i][j]=k;
                    }
                }
            }
        }
}

int main()
{
    int n;
    printf("输入活动个数 n: ");
    while(~scanf("%d",&n))
    {
        memset(c,0,sizeof(0));
        memset(ret,0,sizeof(ret));
        printf("\n输入活动开始以及结束时间\n");
        int i,j;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&s[i],&f[i]);
        }
        DP_SELECTOF(s,f,n,c,ret);
        printf("最大子集的个数=%d\n",c[1][n]+2);
    return 0;
}