计算机算法设计与分析第1章 王晓东 (第三版)第4章
4.2 贪心算法的基本要素
void Knapsack(int n,float M,float v[],float w[],float x[]) {
Sort(n,v,w);int i; for (i=1;i<=n;i++) x[i]=0; float c=M;
for (i=1;i<=n;i++) {if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; }
算法knapsack的 主要计算时间在于将 各种物品依其单位重 量的价值从大到小排 序。因此，算法的计 算时间上界为 O(nlogn)。 为了证明算法的正确 性，还必须证明背包 问题具有贪心选择性 质。
