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

发布时间：2006-06-28 02:19     点击：

　　　　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++)

　　　{ if(temp_w+w[e[i]]<=TW)

　　　　　temp_v=temp_v+v[e[v]];

　　}

分治法:

　　思想:把规模为n的问题进行分解,分解成几个小规模的问题.然后在得到小规模问题的解的基础上,通过某种方法组合成该问题的解.

　　例:数轴上有n个点x[n],求距离最小的两个点.

　　分:任取一点,可以把x[i]这n个点分成两个部分

　　小的部分 分点 大的部分

　　　　|_._.__.__.____._|__._._.__._.__._______._.__._._.__.___._____._|

　　治:解=min{小的部分的距离最小值;

　　　大的部分的距离最小值;

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

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