贪心法求解背包问题
最后更新于：2022-04-01 15:56:40
背包问题：
> 背包问题：
已知背包的容量为M和n件物品。第i件物品的重量为wi,价值为pi，将物品i的一部分xi放进背包即可获得价值pi*xi的价值。问题： 怎样装包使所获得的价值最大？
贪心法核心思想：
> 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
求解背包问题的贪心原则可能是以下几个：
1. 每次选价值最大的物品装进背包
1. 每次都选提及最小的物品装进背包
1. 每次选单位价值最大的装.
准则1每次装的价值大，但是同时也可能占据了较大的空间；准则2能装的物品多，总价值未必高，按第三种准则装可以实现背包总价值最大.因此将每个物品按单位价值递减排序，先装单位价值高的，最好空间有剩余，装物品的一部分即可。
C++程序实现：
~~~
include <iostream>
using namespace std;
//数组按pi/wi由大到小不递增排列
int greedypackage(int p[],int w[],int M,double X[],int n){
int i;
int rc=M;//剩余背包容量，初始化为M;
for (i = 0; i < n; ++i)
{
if(w[i]<=rc){
X[i]=1;
rc=rc-w[i];
} else{
break;
}
}
if(i<=n){
X[i]=(double)rc/w[i];
}
for (i = 0; i < n; ++i)
{
cout<<X[i]<<"\t";
}
return 0;
}
int main(){
int p[3]={24,15,25};
int w[3]={15,10,18};//数组w是按wi/pi递减排列的,这一步可以用快速排序实现
int M=20;
double A[3]={0,0,0};
greedypackage(p,w,M,A,3);
return 0;
}
~~~
输出解：
~~~
1 0.5 0
~~~