锐客网

  1. 首页 > it技术 > >

贪心算法作业

桂 林 理 工 大 学
实验报告
班级软件工程16-1班学号3162052051116姓名张识虔同组实验者
实验名称贪心算法日期 2018年 11 月1 日
一、实验目的：
理解贪心算法的思想，并能对给定的问题能设计出分治算法予以解决。

二、实验环境：

三、实验内容：

1. 背包问题
给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? （说明，以下算法与教材147页给出的算法思想是一样的，教材上的算法事先对物品信息进行了排序）


#include
using namespace std;
void Sort(int n,float v[],float w[])
{
int i;
int j;
float t;
for(i=1; i<=n-1; i++){
for(j=i; j<=n; j++){
if(v[i]/w[i] t=v[i];
v[i]=v[j];
v[j]=t;
t=w[i];
w[i]=w[j];
w[j]=t;
}
}
}

}

void Knapsack(int n,float M,float v[],float w[],float x[])
{
Sort(n,v,w);
int i;
int j;
float max;
for (i=1; i<=n; i++){
x[i]=0;
}
float c=M;
for(i=1; i<=n; i++){
if(w[i]>c)
break;
x[i]=1;
c-=w[i];
}
if (i<=n) x[i]=c/w[i]; //最后一个物品选择部分装入
cout<<"选择依次装入背包的物品属性为： "< for(i=1; i<=n; i++){
if(x[i]!=0.0){
cout<<"w="< max=max+v[i]*x[i];
if(x[i]!=1.0){
cout<<"最后装入的物品选择装入物品的"< }
}
}
cout< cout<<"最大价值MaxValue="https://www.it610.com/article/< }

int main()
{
int n,c,i;
float v[20],w[20],x[20];
cout<<"输入 物品的数量 和 背包的容量： "< cin>>n>>c;
cout<<"输入物品的重量和价值："< for(i=1; i<=n; i++){
cout<<"物品"< cin>>w[i]>>v[i];
}
cout< Knapsack(n,c,v,w,x);
return 0;
}

贪心算法作业
文章图片















2. 教材170页第18题。删除数字求最小值
给定一个n位正整数a, 去掉其中k个数字后按原左右次序将组成一个新的正整数。对给定的a, k寻找一种方案,使得剩下的数字组成的新数最小。
提示：应用贪心算法设计求解
操作对象为n位正整数，有可能超过整数的范围，存储在数组a中，数组中每一个数组元素对应整数的一位数字。
在整数的位数固定的前提下，让高位的数字尽量小，整数的值就小。这就是所要选取的贪心策略。
每次删除一个数字，选择一个使剩下的数最小的数字作为删除对象。
当k=1时，对于n位数构成的数删除哪一位，使得剩下的数据最小。删除满足如下条件的a[i]：它是第一个a[i]>a[i+1]的数，如果不存在则删除a[n]。
当k>1（当然小于n），按上述操作一个一个删除。每删除一个数字后，后面的数字向前移位。删除一个达到最小后，再从头即从串首开始，删除第2个，依此分解为k次完成。
若删除不到k个后已无左边大于右边的降序或相等，则停止删除操作，打印剩下串的左边n?k个数字即可（相当于删除了若干个最右边的数字）。
#include
#include
#define N 100
using namespace std;
bool cmp(int a,int b)
{
if(a>b)
return true;
return false;
}
int main()
{
int a[N],b[N],c[N];
int n,i,k,j,x=1;
int flag=1;
cout<<"输入多少位数:"< cin>>n;
cout<<"输入的数值:";
for(i=1; i<=n; i++){
cin>>a[i];
b[i]=a[i];
}
for(i=1; i<=n; i++){
if(a[i]==a[n-i])
flag=0;
}
cout<<"需要删除几个数字:";
cin>>k;
sort(a+1,a+n+1,cmp);
for(i=1; i<=n; i++){
for(j=k+1; j<=n; j++){
if(b[i]==a[j]){
c[x]=b[i];
x++;
}
}
}
cout<<"删除后的数值为";
if(flag){
for(i=1; i<=x-1; i++){
cout< }
}
else{
for(i=1; i<=n-k; i++){
cout< }
}
return 0;
}
数字都不相同时
贪心算法作业
文章图片







数字都相同时
贪心算法作业
文章图片

3.设有n个顾客同时等待一项服务。顾客i需要等待的服务时间为ti（1<=i<=n）。共有s处可以提供此服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。

#include

void sort(int a[],int n)
{
int i;
int j;
int t;
for(i=0; i for(j=i; j if(a[i]>a[j]){
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
}

void greedy(int n,int s,int time[])
{
int i;
int sum;
int *p=new int[s];
sum=0;
for(i=0; i p[i]=0;
}
for(i=0; i p[i%s]+=time[i];
sum=sum+p[i%s];
}
printf("%.3lf\n",sum/(n*1.0));
}

int main()
{
int n;
int s;
int i;
int time[50];
printf("请输入顾客数量 服务处数量\n");
scanf("%d %d",&n,&s);
printf("输入各个顾客的服务时间\n");
for(i=0; i scanf("%d",&time[i]);
}
sort(time,n);
printf("平均等待时间:");
greedy(n,s,time);
return 0;
}
贪心算法作业
文章图片

贪心算法作业
文章图片


四、心得体会：



【贪心算法作业】

    推荐阅读


    上一篇：Linux Centos7开放及查看端口

    下一篇：kafka的组件介绍