算法实验2《贪心算法实验》
【摘要】
1. 编写一个简单的程序，实现单源最短路径问题。
#include<iostream>#include<iomanip>using namespace std; void init(int **list){ for (int i = 0; i < 5; i++) { list[i] = new int...
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
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）