15-算法设计

2.3.2　算法设计

（1）数据结构及初始化。将n种宝物的重量和价值存储在结构体three（包含重量、价值、性价比3个成员）中，同时求出每种宝物的性价比也存储在对应的结构体three中，将其按照性价比从高到低排序。采用sum来存储毛驴能够运走的最大价值，初始化为0。

（2）根据贪心策略，按照性价比从大到小选取宝物，直到达到毛驴的运载能力。每次选择性价比高的物品，判断是否小于m（毛驴运载能力），如果小于m，则放入，sum（已放入物品的价值）加上当前宝物的价值，m减去放入宝物的重量；如果不小于m，则取该宝物的一部分m * p[i]，m=0，程序结束。m减少到0，则sum得到最大值。