C/C++语言100题练习计划 83——背包问题（贪心算法实现）

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

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

一、问题呈现

1.问题描述

Problem Description
假设山洞中有n种宝物，每种宝物有一定重量w和相应的价值v，毛驴运载能力有限，只能运走m重量的宝物，一种宝物只能拿一样，宝物可以分割。那么怎么才能使毛驴运走宝物的价值最大呢？

2.输入输出

Input

第一行：宝物数量n，以及毛驴的承载重量m
n行：每个宝物的重量w和相应的价值v

Output

装入总的宝物的最大价值

3.测试样例

Sample Input 1

6 19
2 8
6 1
7 9
4 3
10 2
3 4

Sample Output 1

24.6

Sample Input 2

5 12
2 3
4 2
1 4
5 5
4 6

Sample Output 2

18

二、源码实现

#include 
#include 
using namespace std;
const int Maxn=1e6+5;

//宝物结构体
struct treasure {
	double w;  //每个宝物的重量
	double v;  //每个宝物的价值
	double p;  //每个宝物的性价比
}t[Maxn];

//排序比较函数
bool cmp(treasure a, treasure b)
{
	return a.p > b.p;  //根据宝物的单位价值从大到小排序(降序排序)
}

//主函数
int main()
{
	//n 表示有n个宝物
	int n;  
	//m 表示毛驴的承载能力
	double m;  
	
	//输入宝物数量n及毛驴的承载能力m
	cin>>n>>m;

	//输入每个宝物的重量及价值
	for(int i=0; i<n; i++)
	{
		cin>>t[i].w>>t[i].v;
		t[i].p=t[i].v/t[i].w;  //每个宝物单位价值=其价值/其重量
	}
	
	//降序排序
	sort(t,t+n,cmp);
	
	//sum 表示贪心记录运走宝物的价值之和
	double sum = 0.0;  
	
	//按照排好的顺序，循环执行贪心策略
	for(int i=0; i<n; i++)  
	{
		//如果宝物的重量小于毛驴的运载能力
		if( m > t[i].w)  
		{
			m -= t[i].w;
			sum += t[i].v;
		}
		//如果宝物的总量大于毛驴的承载能力
		else 
		{
			//进行宝物切割，切割一部分（m重量），正好达到毛驴称重
			sum += m * t[i].p;  
			break;
		}
	}
	
	//输出装入总的宝物的最大价值
	cout<<sum<<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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

★关于本题思路及贪心算法（+补充）：

1️⃣本题思路简述
本题大概的思路就是，首先为了使m重量里的所有物品的价值最大，可以借助贪心思想，每次取剩下物品里面性价比最高的物品，这样可以使得在相同重量条件下比选其他物品所得到的价值更大，因此采用贪心策略能得到最优解。（物品可分割的装载问题称为背包问题，物品不可分割的装载问题称为0-1背包问题）。

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

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

b.最优子结构
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
// 如果满足这两个性质就可以考虑使用贪心算法了。（这两个性质划重点）

★补充：
③贪心算法优缺点
优点：简单，高效，省去了为了找最优解可能需要穷举操作，通常作为其它算法的辅助算法来使用；
缺点：不从总体上考虑其它可能情况，每次选取局部最优解，不再进行回溯处理，所以很少情况下得到最优解。

其实如果你看到了这里，还要注意一点：物品可分割的装载问题称为背包问题，物品不可分割的装载问题称为0-1背包问题。背包问题和0-1背包问题是不一样的。本题你可以判断出，它是一个背包问题，可分割。

三、测试结果

6 19
2 8
6 1
7 9
4 3
10 2
3 4
24.6

--------------------------------
Process exited after 1.588 seconds with return value 0
请按任意键继续. . .

1
2
3
4
5
6
7
8
9
10
11
12
13

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