讨论/技术交流/USC渣渣-动态规划算法作业-求教/
USC渣渣-动态规划算法作业-求教

有𝑛 个城市,对于每组 𝑖<𝑗 ,都有一条从城市𝑖到城市𝑗 的道路,需要𝑇_{𝑖,𝑗} 的时间。两个旅行者Marco和Polo想在最短的时间内通过所有的城市。换句话说,我们想把城市分成两组,把一组分配给Marco,另一组分配给Polo,使他们的旅行时间之和最小。你可以假设他们从他们所在城市集合中 选择下标最小的城市开始旅行,并且他们按照下标的升序(从最小的下标到最大的下标)旅行城市。你的算法的时间复杂度应该是 𝑂(𝑛^2) 。证明你的算法是最优的。

WeChat Screenshot_20210302001622.png

这道题是在教授讲完分治法和动态规划发布的,所以,解决方法不是分治法就是DP。 [目测DP, 但是找不到子问题,大佬们,救救孩子吧!]

共 6 个回复

时间T是怎么给出的呢,原题看起来是有向带权最短路径问题,不过我没理解路径上的权重怎么给出,如果全都假设为一样的话,直接就是把数组n分为两组上升序列了

不一定对:
cost[i][j]表示从城市i到j的时间;
prefix[i]表示cost[0][1]+cost[1][2]+...cost[i-1][i];
dp[0][i][j]表示遍历城市i,i+1,...j的最优解并且j城市由Macro遍历;
dp[1][i][j]表示遍历城市i,i+1,...j的最优解并且j城市由Polo遍历;
有:
dp[0][i][j] = min(dp[0][i][k] + prefix[i] - prefix[k], dp[1][i][k] + cost[A[k]][k+1] + prefix[i]- prefix[k+1]);
A[k]表示当取得dp[0][i][k]时Polo所在城市, A[k] < k;
dp[1][i][j] = min(dp[1][i][k] + prefix[i] - prefix[k], dp[0][i][k] + cost[B[k]][k+1] + prefix[i]- prefix[k+1]);
B[k]表示当取得dp[0][i][k]时Macro所在城市,B[k] < k;

。。。又刷到了你的帖子,是缘分吗。。讲道理我又没有体会到这道题的dp或者分治思想,不太好意思写回答。。不过既然是作业提供一个解题思路先完成了先吧

理解下题目,可以认为道路都是单向的,只能由序号低的城市到高的城市。既然这样,如果可以把所有的情况全部遍历出来然后求最优解就可以了,复杂度也是O(n²)

遍历方法:假设分配给Marco的城市数量从0个开始增加,对于每次规定的数量遍历所有可能,由于题目要求“单向型”,所以不会出现重复。比如你分配给Marco第1 3 7 8号城市,那么剩下的就按照顺序分配给Polo,然后计算总和。最后求最优解。

优化:假设有n个城市,当你分配给Marco 2个城市,自然就有n-2个城市分配给Polo。当你有n-2个城市分配给Marco,自然就剩下2个分配给Polo。所以不需要从0~n全部遍历,只需要遍历0~n/2。不过复杂度总体依然是O(n²)。

希望能帮到你吧,不过作业还是尽量自己想想动手比较好,这个方法不一定符合老师的要求。

之前那道题如果老师有公布答案还请评论区告知一哈,一起学习了😊

你过分了

分治吧。

这是第几次问作业了。。。