问题描述：

• 有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
• 物品：A    B    C    D    E    F    G
• 重量：35  30   60  50   40  10  25
• 价值：10  40   30  50   35  40  30

  算法描述：

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

      贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

  问题分析：

  1.目标函数： ∑pi最大，使得装入背包中的所有物品pi的价值加起来最大。

  2.约束条件：装入的物品总重量不超过背包容量：∑wi<=M( M=150)

  3.贪心策略： 选择单位重量价值最大的物品

  算法设计：

  1. 计算出每个物品单位重量的价值
  2. 按单位价值从大到小将物品排序
  3. 根据背包当前所剩容量选取物品
  4. 如果背包的容量大于当前物品的重量，那么就将当前物品装进去。否则，那么就将当前物品分割再装进去，然后跳出循环结束。

  代码实现：

  #include
  using namespace std;
  const int maxn = 1000;
  float z[maxn];
   
  void Sort(int n,float w[],float v[]){
  	for(int i=0;ipimax)	break;
  		x[i] = 1;	//x[]数组用来记录此次是否选择物品，1代表全部拿走，0代表不拿，小数代表部分拿 
  		pimax -= w[i];
  	}
  	if(i<=n-1)  x[i] = pimax/w[i]; 
  } 
   
   
  int main(){
  	int n;
  	float pi=0; 
  	float pimax,v[maxn],w[maxn],x[maxn];//w[],每个物品的重量,v[]代表每个物品的价值,pimax代表最大容量 
  	memset(x,0,sizeof(x));
  	cout<<"请输入最大容量：";
  	cin>>pimax;
  	cout<<"请输入物品(物品可以任意分割)数量：";
  	cin>>n;
  	cout<<"请输入每个物品的重量和价值："<>w[i]>>v[i];
  	}
  	fire(n,w,v,x,pimax);
  	for(int i=0;i 
  运行结果：