C/C++语言100题练习计划 82——加勒比海盗船（贪心算法实现）

名人说：故立志者，为学之心也；为学者，立志之事也。—— 王阳明
进度：C/C++语言100题练习计划专栏，目前82/100

🥇C/C++语言100题练习专栏计划：目的：巩固练习C/C++语言，增强上机、动手实践能力，交流学习！

一、问题呈现

1.问题描述

Problem Description
在北美洲东南部，有一片神秘的海域，那里碧海蓝天、阳光明媚，这正是传说中海盗最活跃的加勒比海。17 世纪时，这里更是欧洲大陆的商旅舰队到达美洲的必经之地，所以当时的海盗活动非常猖獗，海盗不仅攻击过往商人，甚至攻击英国皇家舰…… 有一天，海盗们截获了一艘装满各种各样古董的货船，每一件古董都价值连城，一旦打碎就失去了它的价值。虽然海盗船足够大，但载重量为C，每件古董的重量为 wi，海盗们该如何把尽可能多数量的宝贝装上海盗船呢？

2.输入输出

Input

第一行：载重量c和宝贝数目n
第二行：每个宝贝的重量，以空格分隔

Output

可装载的最大数量

3.测试样例

Sample Input 1

30 5
3 6 5 2 7

Sample Output 1

5

Sample Input 2

20 4
10 8 5 7

Sample Output 2

3

Sample Input 3

30 8
4 10 7 11 3 5 14 2

Sample Output 3

5

二、源码实现

#include 
#include 
const int N = 1e6+5;
using namespace std;
double w[N];  //古董的重量数组

int main()
{
	double c;
	int n;
	//输入载重量c及古董个数n
	cin>>c>>n;
	//循环输入每个物品重量
	for(int i=0; i<n; i++)
	{
		cin>>w[i];  
	}
	
	//按古董重量升序排序
	sort(w,w+n);
	
	//weight 代表装载到船上的古董的重量，flag 记录已经装载的古董个数
	double weight = 0.0;
	int flag = 0;
	
	for(int i=0; i<n; i++)
	{
		weight+=w[i];//对要装载船上的古董重量进行求和
		
		if(weight<=c)//如果总重量小于等于载重量，说明该古董可以继续装载
		{
			flag++;//古董记录数量加1
		}
			
		else
		{
			break;
		}
	}
	
	//输出能装入的古董最大数量
	cout<<flag<<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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

★关于本题思路及贪心算法：

1️⃣本题思路简述

本题大概的思路就是，使用贪心算法进行选择，就是每次都选取当前所剩古董中重量最小的古董，直至再选取一个就会超过载重量，此时的数目就是我们所要求的最大数量。
具体到代码实现来说，先将古董按重量从小到大排序，for循环遍历，如果加上当前古董不会超重就增加数量，增加总重量，如果超重就退出循环，最后输出所求数量。

2️⃣贪心算法

①思想解释
在《算法导论》书籍中，有这样一句话：“一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择从而得到全局最优的解决方案。”
这句话，怎么理解呢？个人来看，其实就好比，我们走路会遇到很多的十字路口，这个时候我们就面临选择，那么哪个对于当前是最优的，我们要考虑到交通路况、目的地等多种因素，综合来看，当前最好的选择是哪一个，就走哪条路，下一个十字路口也是这样，直至到达目的地。

②使用贪心算法求解的两个重要特性
a.贪心选择
所谓贪心选择性质是指原问题的整体最优解可以通过一系列局部最优的选择得到。应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前最佳的选择。这种选择依赖于已作出的选择，但不依赖于未做出的选择。

b.最优子结构
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

如果满足这两个性质就可以考虑使用贪心算法了。（这两个性质划重点）
其实如果你看到了这里，再向上回顾这道题，会发现，是符合的。因此使用起来就很有效。

三、测试结果

30 5
3 6 5 2 7
5

--------------------------------
Process exited after 5.947 seconds with return value 0
请按任意键继续. . .
1
2
3
4
5
6
7

Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）
如果对大家有帮助的话，希望大家能多多点赞+关注！这样我动力会更足哦！ ღ( ´･ᴗ･` )比心