考试网 >> IT认证 >> 水平 >> 软件指导 >> 程序员数据结构笔记(三)

发布时间：2006-06-28 04:46     点击：

贪婪法:

　　不求最优解,速度快(以精确度换速度)

　　例:哈夫曼树,最小生成树

　　装箱问题:

　　有n个物品,重量分别为w[n]，要把这n个物品装入载重为TW的集装箱内,需要几个集装箱?

　　思想1:对n个物品排序

　　拿出第1个集装箱，从大到小判断能不能放。

　　2 …

　　3 …

　　. …

　　. …

　　思想2: 对n个物品排序

　　用物品的重量去判断是否需要一只新箱子，如果物品重量小于本箱子所剩的载重量,则装进去,反之则取一只新箱子。

程序:

　　count=1;qw[0]=TW;

　　for(i=0;i<n;i++)

　　{

　　　k=0;

　　　while(k<count)&&(w[i]>qw[k])

　　　　k++;

　　　　if(w[i]<=qw[k])

　　　　　qw[k]=qw[k]-w[i];

　　　　　code[i]=k; //第i个物品放在第k个箱子内

　　　　else

　　　　　{count++; //取一个新箱子

　　　　　　qw[count-1]=TW-w[i];

　　　　　　code[i]=count-1;

　　　　}

　　}

　　用贪婪法解背包问题:

　　n个物品，重量:w[n] 价值v[i]

　　背包限重TW，设计一个取法使得总价值最大.

　　方法:

　　　0　　1　　2　　3　…　n-1

　　　w0　 w1 　w2 　w3　…　wn-1

　　　v0　 v1 　v2 　v3　…　vn-1

　　　v0/w0　 …　　　　　v(n-1)/w(n-1) 求出各个物品的"性价比"

　　先按性价比从高到低进行排序

　　已知:w[n],v[n],TW

　　程序:

　　…

　　for(I=1;I<n;I++)

　　　d[i]=v[i]/w[i]; //求性价比

　　　for(I=0;I<n;I++)

　　　{ max=-1;

　　　　for(j=0;j<n;j++)

　　　　{ if(d[j]>max)

　　　　　{ max=d[j];x=j; }

　　　　}　

　　　　e[i]=x;

　　　　d[x]=0;

　　　}

　　　temp_w=0;temp_v=0;

　　for(i=0;i<n;i++)

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。