问题描述:吉祥号货轮最大载重量为M吨,有N件货物供选择装船,每件货物的重量和价值是不同的。设计程序使得总重量不超过M,且装的货物总价值最大。
//************************* //* 任务介绍:贪心算法之 * // 装船问题 * //* 作者: 何香 * //* 完成时间:2013.10.18 * //************************* #include <iostream> using namespace std; int M;//船的最大载重量 int N;//货物的件数 const int max_N=500; //用结构体描述货物的结构(重量、价值) struct goods { float w;//weight float p;//price float pw;//价重比,p/w }g[max_N];//用结构体数组,调用p,w,pw;(max_N必须为常整数) int main() { int i,j; cout<<"输入最大载重量和货物的件数"<<endl; cin>>M>>N; cout<<"输入各货物的重量和价值"<<endl; for(i=0;i<N;++i)//输入重量和价值,并计算价重比 { cin>>g[i].w>>g[i].p; g[i].pw=(g[i].p)/(g[i].w); } goods temp; for(i=0;i<N-1;++i)//用冒泡排序对价重比进行由大到小排序 for(j=i+1;j<N;++j) { if(g[i].pw<g[j].pw) { temp=g[i]; g[i]=g[j]; g[j]=temp; } } float sum_w=0;//记录装入船的总重量 float sum_p=0;//记录装入船的货物的总价值 int r=0;//记录装入船的货物的件数 while(sum_w+g[r].w<=M&&r<N) { sum_w+=g[r].w; sum_p+=g[r].p; r++; } cout<<sum_p<<endl;//输出装入船的货物的最大价值 return 0; }