吴文虎 程序设计基础 第2版 PPT第14.ppt

9 贪 心 法 教学目标 贪心法解题的一般步骤 贪心法的相关理论 贪心法解题的注意事项 内容要点 贪心法的应用 贪心法解题的一般步骤 贪心法的相关理论 贪心法解题的注意事项 9.0 贪心法解题的一般步骤 9.0.1 装船问题 【任务 9.0】王小二毕业后从事船运规划工作，吉祥号货轮的最大载重量为M吨，有N件货物供选择装船，每件货物的重量和价值是不同的。王小二的任务是从N件货物中挑选若干件上船，在满足货物总重量小于等于M的前提下，运走的货物的总价值最大。 王小二很聪明，他选择了贪心策略，专挑价钱高重量轻的货物往船上搬。具体方法是：对每件货物，计算其价值与重量之比，姑且称之为 “ 价重比”，价重比高的货物优先装船，每装一件累计其重量，控制总重量不超过货轮的载重量M。由此，他荣幸地获得一个绰号：“贪心的王小二”。 这类问题称为 0-1 背包问题。 算法如下 1 . 定义一个描述货物的结构 goods struct goods { float w; float p; float pw; int No; } g [N]; 说明：goods 结构含4个成员，分别是货物重量w ,货物价值p ,货物的价重比pw 和货物的编号No 。g[N] 是结构数组，有N个数组元素，下标为0,1…N-1. 每个数组元素的数据类型都是 goods 结构类型，用来描述每件货物。 2. 使用 for 循环输入N件货物的数据 for(int i=0;iN;i++) //循环 { // for i coutg[i].p=; //提示信息 cing[i].p; //键盘输入第i件货物的价值 cout g[i].w=; //提示信息 cing [i].w; //键盘输入第i件货物的重量 g[i].pw = ( g[i].p ) / ( g[i].w ); //计算第i件货物的单位重量的价值 g[i].No = i; //键盘输入第i件货物的编号 } // for i 4 使用 while 循环，贪心地搬货，将价值重量比高的优先抬上船，控制总重量不超过船的载重量M。 int sumw=0; // 定义装上船的货物的总重量，初始化为零 int sump=0; // 定义装上船的货物的总价值，初始化为零 int r = 0; // 定义变量r, 初始化为零 while ( (sumw+ g [r].w)=M rN ) // 当上船货物（件数受限）总重量小于M, { //while sumw = sumw + g [r].w; // 记录货物总重 sump = sump + g [r].p; // 记录货物总价值 r = r+1; // 试下一件货物 } //while cout装货总重量 w= sumwendl; // 输出装货总重量 cout装货总价值 p= sumpendl; // 输出装货总价值 3 对N件货物的价值重量比进行从大到小的排序 goods temp; //定义具有goods结构的中间变量 for(int j=0;jN-1;j++) //冒泡排序，将单位重量价值 高的货物往前排 { //for j for(int k=0;kN-1-j;k++) { //for k if( g [k].pw g [k+1].pw) { //if temp = g [k]; g [k] = g [k+1]; g [k+1] = temp; } //if } //for k } //for j