17-伪代码详解

2.3.4　伪代码详解

（1）数据结构定义

根据算法设计中的数据结构，我们首先定义一个结构体three：

struct three{
     double w; //每种宝物的重量
     double v; //每种宝物的价值
     double p; //每种宝物的性价比（价值/重量）
     ｝

（2）性价比排序

我们可以利用C++中的排序函数sort（见附录B），对宝物的性价比从大到小（非递增）排序。要使用此函数需引入头文件：

#include <algorithm>

语法描述为：

sort(begin, end)// 参数begin和end表示一个范围，分别为待排序数组的首地址和尾地址

在本例中我们采用结构体形式存储，按结构体中的一个字段，即按性价比排序。如果不使用自定义比较函数，那么sort函数排序时不知道按哪一项的值排序，因此采用自定义比较函数的办法实现宝物性价比的降序排序：

bool cmp(three a,three b)//比较函数按照宝物性价比降序排列
{
    return a.p > b.p; //指明按照宝物性价比降序排列
}
sort(s, s+n, cmp); //前两个参数分别为待排序数组的首地址和尾地址
                   //最后一个参数compare表示比较的类型

（3）贪心算法求解

在性价比排序的基础上，进行贪心算法运算。如果剩余容量比当前宝物的重量大，则可以放入，剩余容量减去当前宝物的重量，已放入物品的价值加上当前宝物的价值。如果剩余容量比当前宝物的重量小，表示不可以全部放入，可以切割下来一部分（正好是剩余容量），然后令剩余容量乘以当前物品的单位重量价值，已放入物品的价值加上该价值，即为能放入宝物的最大价值。

for(int i = 0;i < n;i++)//按照排好的顺序，执行贪心策略
  {
     if( m > s[i].w )//如果宝物的重量小于毛驴剩下的运载能力，即剩余容量
     {
        m -= s[i].w;
        sum += s[i].v;
      }
     else  //如果宝物的重量大于毛驴剩下的承载能力
      {
         sum += m乘以s[i].p;  //进行宝物切割，切割一部分(m重量)，正好达到驴子承重
         break;
      }
  }