Greedy(A,n)
{
    //A[0:n-1]包含n个输入，即A是问题的输入集合
    将解集合solution初始化为空;
    for(i=0;i<n;i++)                        //原问题分解为n个阶段
    {
        x=select(A);                        //依据贪心策略做贪心选择，求得局部最优解
        if(x可以包含在solution)              //判断解集合solution在加入x后是否满足约束条件
            solution=union(solution,x);    //部分局部最优解进行合并
    }
    return (解向量solution);                //n个阶段完成后，得到原问题的最优解
}

#include <iostream>
using namespace std;
void Select(int n, int A[],int B[], bool C[])
{
	int i, j;
	C[1] = true;
	j = 1, i = 2;
	while (i <= n)
	{
		if (A[i] > B[j]) {
			C[i] = true;
			j = i;
		}
		else {
			C[i] = false;
		}
		i++;
	}
};
int main()
{
	int A[11] = { 0,1,3,2,5,3,5,6,8,8,2 },
		B[11] = { 0,4,5,6,7,8,9,10,11,12,13 };
	bool C[11];
	Select(11, A, B, C);
	cout << "活动安排如下：" << endl;
	for (int k = 1; k <= 11; k++)
	{
		while (C[k])
		{
			cout << A[k]<<"  "<<B[k] << endl;
			break;
		}
	}
	return 0;
}

#include "TanXin2.h"
#include<iostream>
using namespace std;
#define Max 10
typedef struct {
	int *elem;
	int length;
}SqList;

int InitList(SqList &L)//构造并初始化
{
	L.elem = new int[Max];
	if (!L.elem) return 0;
	L.length = 0;
	return 1;
}

void InputList(SqList &L,SqList &LB, int n)
{
	L.length = 0;
	if (n<0 || n>Max) return;
	cout << "请输入顺序表" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> L.elem[i];
		L.length++;
	}
	for (int j = 0; j < n; j++)
	{
		LB.elem[j] = L.elem[j];
		LB.length++;
	}
}

void OutputList(SqList L)
{
	for (int i = 0; i < L.length; i++)
	{
		cout << L.elem[i] << " ";

	}
}

void Compare(SqList &L)//冒泡排序
{
	int i, j, e;
	for (i = 1; i <= L.length; i++)
	{
		for (j = 0; j < L.length - i; j++)
		{
			if (L.elem[j] > L.elem[j + 1])
			{
				e = L.elem[j];
				L.elem[j] = L.elem[j + 1];
				L.elem[j + 1] = e;
			}
		}
	}
}

int LocateElem(SqList L, int e)//查找数据是否在顺序表内
{
	for (int i = 0; i < L.length; i++)
	{
		if (L.elem[i] == e) return i + 1;//查找成功，返回序号i+1
	}
	return 0;//查找失败，返回0
}

void Select(SqList &L,SqList &LB,int m)
{
	int sum = 0;
	for (int i = 0; i < L.length; i++)
	{
		if ((sum + L.elem[i]) < m)
		{
			sum += L.elem[i];
			cout<< LocateElem(LB, L.elem[i]) <<"  "<< L.elem[i] << endl;
		}
		else {
			break;
		}
	}
}

int main()
{
	int n = 5,m=12;
	SqList LA,LB;
	InitList(LA);
	InitList(LB);
	InputList(LA,LB,n);
	Compare(LA);
	cout << "所选择的为：" << endl;
	Select(LA,LB,m);

}

#include<iostream>
#include<string>
using namespace std;
const int inf = INT_MAX;

void Dijkstra(int n, int source, int *dist, int *prev, int c[8][8])
{
	//表示点是否在s集合里
	bool *s=new bool[n];
	for (int i = 0; i < n; i++)
	{
		dist[i] = c[source][i];
		//初始化时，除了source外所有结点都不在s集合
		s[i] = i == source ? true : false;
		//结点可达，前驱结点记作源点
		//结点不可达，前驱结点记作-1
		prev[i] = dist[i] == inf ? -1 : source;

	}
	for ( i = 1; i < n; i++)//找n-1个点
	{
		int mindist = inf;
		int newnode;//记录距离source最近的点
		for (int j = 0; j < n; j++)
		{
			//j点不在s集合中,且到soutce的距离小于上一个点到source的距离
			if (!s[j] && dist[j] < mindist)
			{
				newnode = j;
				mindist = dist[newnode];
			}
		}
		s[newnode] = true;
		for ( j = 0;j < n; j++)//当s集合加入新结点时，需要更新dist和prev
		{
			if (!s[j] && c[newnode][j] < inf)
			{
				//点不在s中，且与新节点相邻
				int newdist = dist[newnode]+c[newnode][j];//新结点到source的距离+新结点到j点的距离
				if (newdist < dist[j])
				{
					dist[j] = newdist;
					prev[j] = newnode;//新结点成了前驱结点
				}
			}

		}

	}
}

int main()
{
	int c[8][8] = { 
		{0,2,inf,1,inf,3,inf,inf},
	    {inf,0,6,inf,5,inf,inf,inf},
		{inf,inf,0,inf,inf,inf,inf,6},
		{inf,10,inf,0,inf,inf,2,inf},
		{inf,inf,9,inf,0,inf,inf,4},
		{inf,inf,inf,5,inf,0,4,inf},
		{inf,7,inf,inf,3,inf,0,8},
		{inf,inf,inf,inf,inf,inf,inf,0}
	};
	int n = 8;
	int dist[8];
	int prev[8];
	int source = 0;
	Dijkstra(8, source, dist, prev, c);
	cout << "源点到各点的最短路径为:";
	for (int i = 0; i < n; i++)
	{
		cout << dist[i] << " ";
	}
	return 0;
}