关于贪心算法，我在这篇博客中已经做了简单的介绍。初识贪心算法
下面来介绍一下贪心算法中的一个经典的问题——背包问题
一天，阿里巴巴赶着一头毛驴上山砍柴，无意间在远处发现了一群盗贼，他们把偷窃强盗来的宝物全部藏在一个山洞里，山洞前有一个洞门，只见盗贼首领说了一句“芝麻开门”，顷刻间，洞门大开，里面漏出了阿里巴巴这辈子都没有见过的稀世珍宝。阿里巴巴心想：这些盗贼真的可恨，囤积了这么多盗来的宝物藏匿于此，等他们走掉后，不如偷偷把一部风宝物偷出来分给村里的穷人们，让他们开开眼界，他打算一种宝物只拿一个，如果太重就用锤子锤开分解装走一部分，但是毛驴的运载能力有限，怎样才能用自己的驴子运走最大价值的财宝分给那些穷人们呢？
简而言之，假设山洞中一共有n种宝物，每一种宝物都有一定的重量w与价值v，毛驴的最大运载能力为m，一种宝物只能拿走一样，且宝物可以分割带走。那么怎样才能使毛驴运走的宝物价值最大呢？
这是一个典型的贪心问题，我们可以尝试一下三种贪心策略：
（1）每次挑选价值最大的宝物装入背包
（2）每次挑选重量最小的宝物装入背包
（3）每次挑选性价比最大的宝物装入背包
我们思考发现：如果选择价值最大的宝物优先装，但是它的重量可能很大；如果选择重量最小的宝物优先装，但是它的价值又不一定大。所以，第一种和第二种贪心策略显然不是好的策略，舍弃。第三章贪心策略从性价比的角度出发，即每一件宝物都有各自的性价比，即：单位价值p=w/v 我们采取性价比最大的宝物优先装载，最终装不下的宝物进行分割，等于最后剩余的装载量乘以该宝物的单位价值，最终合成，那么最终的价值一定是最大的，即最优解。
代码中有涉及到C++sort排序函数降序排列的方法，不太了解的小伙伴可以去看看我另一篇文章
背包问题的完整代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1000005;
typedef struct treasure{
double w;
double v;
double p;
}treasure;
//自定义比较函数cmp
bool cmp(treasure t1,treasure t2){
return t2.p<t1.p;
}
treasure s[N];
int main(){
int n,m;
cout<<"请输入宝物的种类个数n和驴子的最大承载重量m"<<endl;
cin>>n>>m;
cout<<"请分别输入这"<<n<<"种宝物所对应的重量与价值"<<endl;
for(int i=0;i<n;i++){
cin>>s[i].w>>s[i].v;
s[i].p=s[i].v/s[i].w;
}
sort(s,s+n,cmp);//对宝物以性价比进行降序排列
double sum=0.0;
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;//分解宝物，部分装入
break;
}
}
cout<<"能够装入宝物的最大价值为："<<sum<<"亿元"<<endl;
return 0;
}
（1）区别
背包问题与0-1背包问题的区别在哪？ 区别就在于剩余物品是否可以进行分割
物品可以进行分割的装载问题称为背包问题，物品不可以分割的装载问题称为0-1背包问题。
（2）原因
在物品不可分割的情况下，即0-1背包问题，其已经不具备贪心选择性质，即原问题的最优解无法通过一系列的局部最优解而得到，因此这类问题最终得到的有可能只是近似解。例如上面的背包问题，如果要求物品不可分割，那么最后剩余的装载空间将永远无法填满，永远闲置，故最终可能无法得到一个最优解，而是最优解的近似解。
（3）代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1000005;
typedef struct treasure{
double w;
double v;
double p;
}treasure;
//自定义比较函数cmp
bool cmp(treasure t1,treasure t2){
return t2.p<t1.p;
}
treasure s[N];
int main(){
int n,m;
cout<<"请输入宝物的种类个数n和驴子的最大承载重量m"<<endl;
cin>>n>>m;
cout<<"请分别输入这"<<n<<"种宝物所对应的重量与价值"<<endl;
for(int i=0;i<n;i++){
cin>>s[i].w>>s[i].v;
s[i].p=s[i].v/s[i].w;
}
sort(s,s+n,cmp);//对宝物以性价比进行降序排列
double sum=0.0;
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;//分解宝物，部分装入
break;
}
}
cout<<"能够装入宝物的最大价值为："<<sum<<"亿元"<<endl;
return 0;
}最终价值与背包问题相比少了0.6，这一点就是物品不可分割所造成的。
最后留一个小问题供大家思考：
为什么在加勒比海盗船——最优装载问题中，船在没有装满还留有剩余空间的情况下，最终所得到的仍然是最优解。而在0-1背包问题中，在没有装满的情况下，最终得到的有可能只是最优解的近似解？
一键三连，动力不竭！
