算法设计题目(3)

之间连线数，1≤i

结果输出：将计算出的最小布线费用以及相应的最佳布线方案输出到文件output.txt。 输入文件示例 input.txt 3 2 3

3

输出文件示例 output.txt

10

1 3 2

第六章

1、0-1背包问题的栈式分支限界法

栈式分支限界法将活结点表以后进先出(LIFO)的方式存储于一个栈中。试设计一个解0-1背包问题的栈式分支限界法，并说明栈式分支限界法与回溯法的区别。 2、及时删除不用的结点

解装载问题的分支限界算法中，由EnQueue产生的结点可以在算法结束前一次性删除。然而那些没有活儿子结点或没有叶结点的扩展结点可以立即被删除。试设计一个在算法中及时删除不用结点的方案，并讨论其时间与空间之间的折中。 3、释放结点空间的优先队列式分支限界法

试修改解装载问题和解0-1背包问题的优先队列式分支限界法，使得算法在运行结束时释放所有类型为bbnode和HeapNode的结点所占用的空间。

4、电路板排列问题的队列分支限界法

试设计解电路板排列问题的队列式分支限界法，并使算法在运行结束是输出最优解和最优值。 5、最小重量机器设计问题

问题描述：设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。高wij是从供应商j处购得的部件i的重量，cij是相应的价格。

试设计一个优先队列式分支限界法，给出总价格不超过d的最小重量机器设计。

编程任务：对于给定的机器部件重量和机器部件价格，编程计算总价格不超过d的最小重量机器设计。

数据输入：由文件input.txt给出输入数据。第一行有3个正整数n，m和d。接正业的2n行，每行n个数。前n行是c，后n行是w。 结果输出：将计算出的最小重量，以及每个部件的供应商输出到文件output.txt。 输入文件示例 input.txt 3 3 4 1 2 3

3 2 1

2 2 2

输出文件示例 output.txt

4

1 3 1