算法实验2《贪心算法实验》

1. 编写一个简单的程序，实现单源最短路径问题。

      #include<iostream>
      #include<iomanip>
      using namespace std;
      void init(int **list)
      {
     	for (int i = 0; i < 5; i++)
      	{
      		list[i] = new int[5];
     		for (int j = 0; j < 5; j++)
      		{
      			list[i][j] = INT_MAX;
      		}
      	}
      	list[0][1] = 10;
      	list[0][3] = 30;
      	list[0][4] = 100;
      	list[1][2] = 50;
      	list[2][4] = 10;
      	list[3][2] = 20;
      	list[3][4] = 60;
     	for (int i = 0; i < 5; i++)
      	{
      		cout << endl << i  << " ";
     		for (int j = 0; j < 5; j++)
      		{
      			cout << setw(10) << list[i][j] << " ";
      		}
      	}
      }
      void dijkstra(int n, int v, int dist[], int **c)
      {
     	bool s[5];
     	for (int i = 0; i < n; i++)
      	{
      		dist[i] = c[v][i];
      		s[i] = false;
      	}
      	dist[v] = 0;
      	s[v] = true;
     	for (int i = 0; i < n; i++)
      	{
     		int temp = INT_MAX;
     		int u = v;
     		for (int j = 0; j < n; j++)
     		if (!s[j] && (dist[j] < temp))
      		{
      			u = j;
      			temp = dist[j];
      		}
      		s[u] = true;
     		for (int j = 0; j < n; j++)
      		{
     			if (!s[j] && (c[u][j] < INT_MAX))
      			{
     				int newdist = dist[u] + c[u][j];
     				if (newdist < dist[j])	dist[j] = newdist;
      			}
      		}
      	}
      }
      int main()
      {
     	int n = 5;
     	int **list;
      	list = new int *[5];
     	init(list);
      	cout << "\n输入源";
     	int v;
      	cin >> v;
     	int dist[5];
     	dijkstra(n, v, dist, list);
     	for (int i = 0; i < 5; i++)cout << dist[i]<< " ";
     	system("pause>nul");
     	return 0;
      }
  
 

有25分，10分，5分，1分的，那么1分的肯定有n%5个，问题归结为5分，2分，1分的问题。

2个1分不如1个2分，所以1分最多1个， 3个2分不如1个5分和1个1分，所以2分最多2个。

只有6种情况，除掉1个1分2个2分的情况有5种情况，按照n%5直接对应就是唯一的最优解。

      #include<iostream>
      using namespace std;
      int main()
      {
     	int n ;
      	cout << "请输入多少分\n";
      	cin >> n;
     	if (n > 0)		//25,10,5,1
      	{
      		cout << "1分的要" << n % 5 << "个";
      		n = n / 5;		//5,2,1
     		int m = n % 5;
     		int a1=0, a2=0;
     		if (m == 1)a1 = 1;
     		if (m == 2)a2 = 0;
     		if (m == 3)a1 = a2 = 1;
     		if (m == 4)a2 = 2;
      		cout << "\n5分的要" << a1 << "个\n1角的要"<<a2<<"个\n2角5分的要"<<n/5<<"个";
      	}
     	system("pause>nul");
     	return 0;
      }
  
 

      #include<iostream>
      using namespace std;
      int par(int a[], int p, int r)
      {
     	int i = p, j = r + 1;
     	int x = a[p];
     	while (1)
      	{
     		while (a[++i]<x && i<r);
     		while (a[--j]>x);
     		if (i >= j)break;
     		int te = a[i];
      		a[i] = a[j];
      		a[j] = te;
      	}
      	a[p] = a[j];
      	a[j] = x;
     	return j;
      }
      void qSort(int list[], int p, int r)
      {
     	if (p<r)
      	{
     		int q = par(list, p, r);
     		qSort(list, p, q - 1);
     		qSort(list, q + 1, r);
      	}
      }
      int getMinIndex(int *p,int m)
      {
     	int index = 0;
     	int min = p[0];
     	for (int i = 1; i < m; i++)
      	{
     		if (min>p[i])
      		{
      			min = p[i];
      			index = i;
      		}
      	}
     	return index;
      }
      int main()
      {
     	int n, m;
      	cout << "输入n,m,n个时间\n";
      	cin >> n>>m;
     	int *list = new int[n];
     	for (int i = 0; i<n; i++)
      	{
      		cin >> list[i];
      	}
     	qSort(list, 0, n-1);
     	int *p = new int[m];		//m上的进程时间和
     	int **result = new int*[m];
     	int *num = new int[m];		//m上的进程数
     	for (int i = 0; i < m; i++)
      	{
      		p[i] = 0;
      		result[i] = new int[n];
      		num[i] = 0;
      	}
     	for (int i = n-1; i >=0; i--)
      	{
     		int index = getMinIndex(p, m);
      		result[index][num[index]] = list[i];
      		num[index]++;
      		p[index] += list[i];
      	}
     	for (int i = 0; i < m; i++)
      	{
      		cout << endl;
     		for (int j = 0; j < num[i]; j++)
      		{
      			cout << result[i][j]<<" ";
      		}
      	}
     	system("pause>nul");
     	return 0;
      }
  
 

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/78867260