计算机算法设计与分析第1章 王晓东 (第三版)第4章(18)

计算机算法设计与分析第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)。 为了证明算法的正确 性，还必须证明背包 问题具有贪心选择性 质。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库计算机算法设计与分析第1章 王晓东 (第三版)第4章(18)在线全文阅读。