牛骨文教育服务平台(让学习变的简单)

背包问题:

背包问题:
已知背包的容量为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]<<"	";
      }
    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