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

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

　　　　　　push(s,s.data[s.top]+1);

　　　　　}

　　背包问题: TW=20 , w[5]={6,10,7,5,8} 

　　解的条件:1) 该解答树的叶子结点

　　2) 重量最大

　　解答树如下：　　　ROOT

　　　　　　　/ | | | \

　　　　　　　　　 6 10　　 7　　　5　 8

　　　　　　　　/ | | \　 / | \　 / \　| 

　　　　　　　 10 7 5　8 7　5　8 5　 8 8

　　　　　　　　　| |　　　　　　| 

　　　　　　　　　5 8　　　　　　8

　程序:

　　temp_w 表示栈中重量和

　　…

　　init(s); //初始化栈

　　i=0;

　　While(w[i]>TW)

　　　i++;

　　　If(i==n) Return -1; //无解

　　　Else {

　　　　Push(s,i);

　　　　Temp_w=w[i];

　　　　i++;

　　　　while(i<n)&&(temp_w+w[i]<=TW)

　　　　　{ push(s,i);

　　　　　　temp_w+=w[i];

　　　　　　i++;

　　　　}

　　　　max_w=0;

　　　　while(!empty(s))

　　　　　{ if(max_w<temp_w)

　　　　　　　max_w=temp_w;

　　　　　　　x=pop(s);

　　　　　　　temp_w-=w[x];

　　　　　　　x++;

　　　　　　　while(x<n)&&(temp_w+w[x]>TW)

　　　　　　　　x++;

　　　　　　　while(x<n)

　　　　　　　{ push(s,x);

　　　　　　　　temp_w=temp_w+w[x];

　　　　　　　　x++;

　　　　　　　　while(x<n)&&(temp_w+w[x]>TW)

　　　　　　　　x++;

　　　　　　　}

　　　　　}

　　请大家思考:四色地图问题,比如给中国地图涂色,有四种颜色,每个省选一种颜色,相邻的省不能取同样的颜色.不许偷懒，不能选人口不多于xxxxＷ的"大国"哦!如果真的有一天台湾独立了，下场就是这样了，一种颜色就打发了，不过台湾的程序员们赚到了，省事！呵呵。

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

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