姓名： 学号：
实验六
实验目的：通过对例题分析、设计、调试，体会和掌握贪心法在程序设计中的应用，并进行
贪心优化的相应练习。
实验要求：综述应用贪心法求解问题的特点，并从贪心对象的选择、程序结构与参数设置的
改进等方面对贪心设计进行优化。
实验内容：
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
装包：装入重量为 的物品
装入重量为的物品
装入重量为的物品百分之所得最大效益为： 。