动态规划-轮船问题

1、动态规划-轮船问题题目描述某国家被一条河划分为南北两部分，在南岸和北岸总共有N对城市，每一城 市在对岸都有唯一的友好城市，任何两个城市都没有相同的友好城市。每一对友 好城市都希望有一条航线来往，于是他们向政府提出了申请。由于河终年有雾。 政府决定允许开通的航线就互不交叉（如果两条航线交叉，将有很大机会撞船）。你的任务是编写一个程序来帮政府官员决定他们应拨款兴建哪些航线以使 在安全条件下有最多航线可以被开通。输入数据输入文件（ship.in）包括了若干组数据，每组数据格式如下：第一行两个由空格分隔的整数x，y，10=x=6000，10二y=100。x 表示河的长度而y表示宽。第二行是一个整数N（

2、1=N=5000），表示分布在河两 岸的城市对数。接下来的N行每行有两个由空格分隔的正数C，D（C、D=x）， 描述每一对友好城市沿着河岸与西边境线的距离，C表示北岸城市的距离而D表 示南岸城市的距离。在河的同一边，任何两个城市的位置都是不同的。整个输入 文件以由空格分隔的两个0结束。输出数据输出文件（ship.ou）要在连续的若干行里给出每一组数据在安全条件下能够 开通的最大航线数目。示例Ship.in30 4722 42 610 315 129 817 174 20 0Ship.out4问题分析对这道题的最一般想法是进行回溯，但是回溯对于数据规模达到5000的情 况是不可行的。于是我们改变

3、一下思路，将每对友好城市看成一条线段，则这道题的描述 化为：有N条线段，问最少去掉多少条线，可以使剩下的线段互不交叉？顺理成章，删掉的线应该是和其它线交叉最多的，其交叉数最大。所谓 交叉数是指某线与其它线的交叉情况，初始值为0，若和其它线交叉则加1所 得的值。按交叉数从大到小删除线，直到所有线都不交叉为止。此时，我们要 解决的问题有：1、如何计算交叉数？ 2、怎么删线？对第一个问题，以北岸为线的起点而南岸为线的终点；先将所有的线按照 起点坐标值从小到大排序，按照每条线的终点坐标计算交叉数：求线I的交叉数 JI，则检查所有1.I-1条线，若线J( 1 = J I)的终点值大于线I的 终点值，则线

4、I与线J相交。JI与JJ同时加1。整个搜索量最大为5000 X 5000。对第二个问题，将J数组从大到小排序，每删除一条线，则将与之相交的 线的J值减1，重复这个过程，直到所有J值都为0。此时剩下的线则全不交叉。如上数据，则可得下面结果：编号南岸北岸交叉数11312242331244515422此时，2、3、5航线的交叉数都一样，如果删去的是5、3线，则剩下的1、 2、5线互不相交，最多航线数为3；但如果删去的是2、3,则还要删去第5线才符合要求，此时的最多 航线数为2,不是最优解。于是，我们从上面的分析中再深入，将航线按起点坐标排好序后，如上所 述，在本题中，只要线J的起点小于线I的起点，同时它的终点也小于线I的终 点，则线J和线I不相交。因此，求所有线中最多能有多少条线不相交，实际上 是从终点坐标值数列中求一个最长不下降序列。这就把题目转化为一个非常典型 的动态规划题目了。求最长不下降序列的规划方程如下：L(Si)=max(L(Sj)+1； 1 = j i且 Sj Si。Si 为航线的终点坐标值。如上数据可以得下解：编号南岸北岸L值和前趋1131，02242，13311，04453，25422，3非常明显，可以得出解为3,航线为4, 2, 1。从以上分析过