贪心法求解背包问题

背包问题：

背包问题：
已知背包的容量为M和n件物品。第i件物品的重量为wi,价值为pi，将物品i的一部分xi放进背包即可获得价值pi*xi的价值。问题： 怎样装包使所获得的价值最大？

贪心法核心思想：

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

求解背包问题的贪心原则可能是以下几个：

1. 每次选价值最大的物品装进背包
2. 每次都选提及最小的物品装进背包
3. 每次选单位价值最大的装.

准则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