源程序：
1．使用贪心算法解决最小生成树问题。
(1)Prim算法
#include <iostream>
#include <cmath>
using namespace std;
#define MAX 100010
#define LEN 105
double dist[LEN];
double map[LEN][LEN];
bool isvisited[LEN];
//点的结构体
typedef struct Point{
int x;
int y;
double z;
}Point;
//初始化
void init(){
int i,j;
for(i=0;i<LEN;i++){
for(j=0;j<LEN;j++){
if(i==j) map[i][j]=0; //对a[][]进行初始化，一般都要；
map[i][j]=MAX;
}
}
}
//prim算法
double prim(int n){
int i,j,min,pos;
double sum=0;
//初始化
for(i=1;i<=n;i++){
dist[i]=map[1][i];
}
//从1开始
isvisited[1]=true;
dist[1]=MAX;
//找到权值最小点并记录下位置
for(i=1;i<n;i++){
min=MAX;
//pos=-1;
for(j=1;j<=n;j++){
if(!isvisited[j] && dist[j]<min){
min=dist[j];
pos=j;
}
}
if(min==MAX){
return -1;
}
sum+=dist[pos];//加上权值
isvisited[pos]=true;
//更新权值
for(j=1;j<=n;j++){
if(!isvisited[j] && dist[j]>map[pos][j]){
dist[j]=map[pos][j];
}
}
}
return sum;
}
int main(){
Point p[105];
int i,j,n,nCase;
cin>>nCase;
double result;//总价
while(nCase--){
cin>>n;
init(); //初始化
for(i=1;i<=n;i++){
scanf("%d%d%lf",&p[i].x,&p[i].y,&p[i].z);
map[p[i].x][p[i].y]=map[p[i].y][p[i].x]=p[i].z;
}
result=prim(n);
if(result==-1){
cout<<"oh!"<<endl;
}
else{
printf("%.1lf\n",result);
}
}
return 0;
}(2)Kruskal算法
#include <iostream>
#include <>
#include <>
#include <algorithm>
#include <>
using namespace std;
const int N=10000+10;
int t,n,m,pre[N];
struct node{
int x,y,z;
node(){};
node(int a, int b,int c){
x=a;
y=b;
z=c;
}
}point[N];
struct Edge{
int f,t;
double l;
Edge(){};
Edge(int a, int b,double c){
f=a;
t=b;
l=c;
}
bool operator <(const Edge &S)const{
return l<;
}
}e[N];
int find(int x){
int r=x;
while(pre[r]!=r)
r=pre[r];
return r;
}
void join(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy)
pre[fx]=fy;
}
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int a,b,c;
int cnt=0;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a,&b,&c);
e[++cnt]=Edge(a,b,c);
}
sort(e+1,e+cnt+1);
for(int i=1;i<=n;i++){
pre[i]=i;
}
double ans=0;
for(int i=1;i<=cnt;i++)
if(find(e[i].f)!=find(e[i].t)){
join(e[i].f,e[i].t);
ans+=e[i].l;
}
int cn=0;
for(int i=1;i<=n;i++)
if(pre[i]==i)
cn++;
if(cn-1==0)
printf("%.1lf\n",ans);
else
cout << "oh!" << endl;
}
//cout << "Hello world!" << endl;
return 0;
}2．使用回溯法解决0-1背包问题。
#include <iostream>
#include <>
#include <algorithm>
using namespace std;
#define N 100010
int n;
double c;
double cw = 0.0;
double cp = 0.0;
double bestp = 0.0;
int put[100];
struct Edge{
int order;
double v;
double w;
double perp;
Edge(){};
Edge(double a, int b,double c,double d){
perp=a;
order=b;
v=c;
w=d;
}
bool operator <(const Edge &S)const{
return perp>;
}
}e[N];
void knapsack()
{
int i,j;
for(i=1;i<=n;i++)
e[i].perp=e[i].v/e[i].w;
sort(e+1,e+n);
}
void backtrack(int i)
{
double bound(int i);
if(i>n)
{
bestp = cp;
return;
}
if(cw+e[i].w<=c)
{
cw+=e[i].w;
cp+=e[i].v;
put[i]=1;
backtrack(i+1);
cw-=e[i].w;
cp-=e[i].v;
}
if(bound(i+1)>bestp)
backtrack(i+1);
}
double bound(int i)
{
double leftw= c-cw;
double b = cp;
while(i<=n && e[i].w<=leftw)
{
leftw-=e[i].w;
b+=e[i].v;
i++;
}
if(i<=n)
b+=e[i].v/e[i].w*leftw;
return b;
}
int main()
{
int i;
printf("请输入物品的数量和背包的容量：");
scanf("%d %lf",&n,&c);
printf("请依次输入%d个物品的重量:\n",n);
for(i=1;i<=n;i++){
scanf("%lf",&e[i].w);
e[i].order=i;
}
printf("请依次输入%d个物品的价值:\n",n);
for(i=1;i<=n;i++){
scanf("%lf",&e[i].v);
}
knapsack();
backtrack(1);
printf("最优价值为：%lf\n",bestp);
printf("需要装入的物品编号是：");
for(i=1;i<=n;i++)
{
if(put[i]==1)
printf("%d ",e[i].order);
}
return 0;
}