背包問題：
> 背包問題：
已知背包的容量為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
~~~
