算法设计实验报告六

姓名： 学号：

实验六

实验目的：通过对例题分析、设计、调试，体会和掌握贪心法在程序设计中的应用，并进行

贪心优化的相应练习。

实验要求：综述应用贪心法求解问题的特点，并从贪心对象的选择、程序结构与参数设置的

改进等方面对贪心设计进行优化。

实验内容：

1、/* 贪心删数字 */

#include<stdio.h>

void main()

{ int i,j,k,m,n,t,x,a[200];

char b[200];

printf("请输入整数：");

scanf("%s",b);

for(n=0,i=0;b[i]!='\0';i++)

{n++;a[i]=b[i] -48;}

printf("删除数字个数: ");scanf("%d",&k);

printf("以上%d位整数中删除%d个数字分别为: ",n,k);

i=0;m=0;x=0;

while(k>x && m==0)

{i=i+1;

if(a[i-1]<a[i]) /* 出现递增,删除递增的首数字 */

{printf("%d ",a[i-1]);

for(j=i-1;j<=n-x-2;j++)

a[j]=a[j+1];

x=x+1; /* x统计删除数字的个数 */

i=0; /* 从头开始查递增区间 */

}

if(i==n-x-1) /* 已无递增区间,m=1脱离循环 */

m=1; }

printf("\n删除后所得最大数: ");

for(i=1;i<=n-k;i++) /* 打印剩下的左边n-k个数字 */

printf("%d",a[i-1]);

}

实验数据：输入762091754639820463

删除数字个数：6

以上删除6个数字分别为： 删除后所得最大数：

2、/* 可拆背包问题 */

#include <stdio.h>

#define N 50

void main()

{float p[N],w[N],x[N],c,cw,s,h;

int i,j,n;

printf("\n input n:"); scanf("%d",&n); /* 输入已知条件 */

printf("input c:"); scanf("%f",&c);

for(i=1;i<=n;i++)

{printf("input w%d,p%d:",i,i);

scanf("%f,%f",&w[i],&p[i]);

}

for(i=1;i<=n-1;i++) /* 对n件物品按单位重量的效益从大到小排序 */ for(j=i+1;j<=n;j++)

if(p[i]/w[i]<p[j]/w[j])

{ h=p[i];p[i]=p[j]; p[j]=h;

h=w[i];w[i]=w[j]; w[j]=h;

}

cw=c;s=0; /* cw为背包还可装的重量 */

for(i=1;i<=n;i++)

{if(w[i]>cw) break;

x[i]=1.0; /* 若w(i)<=cw,整体装入*/

cw=cw-w[i];

s=s+p[i];

}

x[i]=(float)(cw/w[i]); /* 若w(i)>cw,装入一部分x(i) */

s=s+p[i]*x[i];

printf("装包："); /* 输出装包结果 */

for(i=1;i<=n;i++)

if(x[i]<1) break;

else

printf("\n 装入重量为%5.1f的物品.",w[i]);

if(x[i]>0 && x[i]<1)

printf("\n 装入重量为%5.1f的物品百分之%5.1f.",w[i],x[i]*100);

printf("\n 所得最大效益为：%7.1f ",s);

}

运行程序，

Input n：5

Input c：90.0

Input w1,p1:32.5,56.2

Input w2,p2:25.3,40.5

Input w3,p3:37.4,70.8

Input w4,p4:41.3,78.4

Input w5,p5:28.2,40.2

装包：装入重量为 的物品

装入重量为的物品

装入重量为的物品百分之所得最大效益为： 。

本文来源：https://www.bwwdw.com/article/e7im.html