完全背包问题（贪心）

在 从零开始学动态规划 中我们已经谈过三种最基本的背包问题：零一背包，部分背包，完全背包。很容易证明，背包问题不能使用贪心算法。然而我们考虑这样一种背包问题：在选择物品i装入背包时，可以选择物品的一部分，而不一定要全部装入背包。这时便可以使用贪心算法求解了。计算每种物品的单位重量价值作为贪心选择的依据指标，选择单位重量价值最高的物品，将尽可能多的该物品装入背包，依此策略一直地进行下去，直到背包装满为止。在零一背包问题中贪心选择之所以不能得到最优解原因是贪心选择无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。在程序中已经事先将单位重量价值按照从大到小的顺序排好。

#include<iostream>   
using namespace std;   
const int N=4;  
void knapsack(float M,float v[],float w[],float x[]);  
  
int main()  
{  
    float M=50;
	//背包所能容纳的重量   
    float w[]={0,10,30,20,5};
	//每种物品的重量  
    float v[]={0,200,400,100,10};  
  	//每种物品的价值 
    float x[N+1]={0};  
    //记录结果的数组 
    knapsack(M,v,w,x);  
    cout<<"选择装下的物品比例："<<endl;  
    for(int i=1;i<=N;i++) cout<<"["<<i<<"]:"<<x[i]<<endl;  
}  
  
void knapsack(float M,float v[],float w[],float x[])  
{  
    int i;  
    //物品整件被装下  
    for(i=1;i<=N;i++)
    {  
        if(w[i]>M) break;   
        x[i]=1;  
        M-=w[i];  
    }   
    //物品部分被装下  
    if(i<=N) x[i]=M/w[i];   
}