【3】贪心算法-最优装载问题-加勒比海盗

算法背景
在北美洲东南部，有一片神秘的海域，那里碧海蓝天、阳光
明媚，这正是传说中海盗最活跃的加勒比海（Caribbean Sea）。
有一天，海盗们截获了一艘装满各种各样古董的货船，每一
件古董都价值连城，一旦打碎就失去了它的价值。虽然海盗船足
够大，但载重量为C，每件古董的重量为wi，海盗们该如何把尽
可能多数量的宝贝装上海盗船呢？

问题分析
贪心策略
本题要求物品不可分割，要求装载的物品的数量尽可能多，而船的载重量
是固定的，那么优先把重量小的物品放进去，在载重量固定的情况下，装的物
品最多。
贪心选择策略：重量最小者先装
从局部最优达到全局最优，从而产生最优装载问题的最优解。
算法设计
算法设计：
（1）当载重量为定值c时，wi越小时，可装载的古董数量n越大。只要依次选
择最小重量古董，直到不能再装为止。
（2）把n个古董的重量从小到大（非递减）排序，然后根据贪心策略尽可能多
地选出前i个古董，直到不能继续装为止，此时达到最优。
完美图解

表2-1 古董重量清单

（1）因为贪心策略是每次选择重量最小的古董装入海盗船，因此可以按照古董重
量非递减排序，排序后如表2-2所示。

表2-2 按重量排序后古董清单

（2）按照贪心策略，每次选择重量最小的古董放入（tmp 代表古董的重量，ans
代表已装裁的古董个数）。

算法的伪代码

实战演练

#include
#include
using namespace std;
const int maxn = 1e6 + 10;
int q[maxn];//宝物重量的数组 
int n,max1;//n-宝物的数量；max1-串只所能载的最大重量 
int main(){
	cin>>n>>max1;
	int sum1 = 0;
	int count = 0;//船能装载货物的数量 
	for(int i = 0;i <= n - 1;i ++){
		cin>>q[i];
	}
	sort(q,q+n);
	for(int i = 0;i <= n - 1;i ++){
		sum1 += q[i];
		count ++;
		if(sum1 > max1){
			sum1 -= q[i];
			break;
		}
	
	}
	cout<<sum1<<endl;
	cout<<count - 1<<endl;
	return 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27