听说她需要一个更高的椅子，谁负责送？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

听说她需要一个更高的椅子，谁负责送？

听说她需要一个更高的椅子，谁负责送？# Joke - 肚皮舞运动

j*y2012-09-24 07:09

1 楼

Two-Person Traversal of a Sequence of Cities. You are given an ordered
sequence of n cities, and the distances between every pair of cities. You
must partition the cities into two subsequences (not necessarily contiguous)
such that person A visits all cities in the first subsequence (in order),
person B visits all cities in the second subsequence (in order), and such
that the sum of the total distances travelled by A and B is minimized.
Assume that person A and person B start initially at the first city in their
respective subsequences.
多谢。

r*e2012-09-24 07:09

2 楼

l*b2012-09-24 07:09

3 楼

感觉不是Dp，子问题想是tsp...

contiguous)
their

【在 j*****y 的大作中提到】

: Two-Person Traversal of a Sequence of Cities. You are given an ordered
: sequence of n cities, and the distances between every pair of cities. You
: must partition the cities into two subsequences (not necessarily contiguous)
: such that person A visits all cities in the first subsequence (in order),
: person B visits all cities in the second subsequence (in order), and such
: that the sum of the total distances travelled by A and B is minimized.
: Assume that person A and person B start initially at the first city in their
: respective subsequences.
: 多谢。

G*r2012-09-24 07:09

4 楼

先来5把

j*y2012-09-24 07:09

5 楼

这是这里面的一道题。
http://people.csail.mit.edu/bdean/6.046/dp/

【在 l*******b 的大作中提到】

: 感觉不是Dp，子问题想是tsp...
:
: contiguous)
: their

r*e2012-09-24 07:09

6 楼

哈哈,这难不到众多跃跃欲试的wsn

【在 G****r 的大作中提到】

: 先来5把

f*e2012-09-24 07:09

7 楼

只想到了O(N^2)的DP。
就是考虑
i属于一个partition,
i+1属于另一个partition
的最优情况。
记为d[i,i+1]
然后总的最优解就是
min(j) = min{w(j,j-1)+min(j-1), w(j,j-2)+d[j-2,j-1]，
w(j,j-3)+w(j-1,j-2)+d[j-3,j-2],...}

contiguous)
their

【在 j*****y 的大作中提到】

g*n2012-09-24 07:09

8 楼

能有这个牛X吗

l*b2012-09-24 07:09

9 楼

哦。。。是ordered sequence 呀，没看清

【在 f*****e 的大作中提到】

: 只想到了O(N^2)的DP。
: 就是考虑
: i属于一个partition,
: i+1属于另一个partition
: 的最优情况。
: 记为d[i,i+1]
: 然后总的最优解就是
: min(j) = min{w(j,j-1)+min(j-1), w(j,j-2)+d[j-2,j-1]，
: w(j,j-3)+w(j-1,j-2)+d[j-3,j-2],...}
:

h*i2012-09-24 07:09

10 楼

肚子有点大

j*y2012-09-24 07:09

11 楼

然后你的 return 是 min(n) ?

【在 f*****e 的大作中提到】

f*e2012-09-24 07:09

12 楼

是啊，d[i,i+1]也可以用DP算的，总而言之，这个题用DP算了两个量吧，一个量min_j用
到了另一个量d(j-1,j)，有时min_j=d(j-1,j) （当j-1,j在不同partition的时候），最
终的min_j就是所求。

【在 j*****y 的大作中提到】

: 然后你的 return 是 min(n) ?

h*u2012-09-24 07:09

13 楼

Suppose nodes are indexed from 1 to n.
d[i,j] = distance from i to j for 1<=i<=n and 1<=j<=n
d[0,j] = 0 for 0<=j<=n
Then, let C[i, j] denote "minimal cost with one stopping at i and another
stopping at j".
C[i,j] = {
C[i,j-1] + d[j-1,j] (if i < j-1)
min {C[k,i] + d[k,j]} for 0 <= k < i (if i = j-1)
}
Base: C[0,1]=0
Output min{C[k,n]} for 0 <= k <= n

a*m2012-09-24 07:09

14 楼

其实和两个股票那个差不多。

j*y2012-09-24 07:09

15 楼

nice idea.
more precisely, C[i, j] is "the minimal cost with one stopping at i and
another stopping at j when only considering the first j cities" ?

【在 h**u 的大作中提到】

: Suppose nodes are indexed from 1 to n.
: d[i,j] = distance from i to j for 1<=i<=n and 1<=j<=n
: d[0,j] = 0 for 0<=j<=n
: Then, let C[i, j] denote "minimal cost with one stopping at i and another
: stopping at j".
: C[i,j] = {
: C[i,j-1] + d[j-1,j] (if i < j-1)
: min {C[k,i] + d[k,j]} for 0 <= k < i (if i = j-1)
: }
: Base: C[0,1]=0

j*y2012-09-24 07:09

16 楼

两个股票是什么题目阿？

【在 a********m 的大作中提到】

: 其实和两个股票那个差不多。

f*e2012-09-24 07:09

17 楼

leetcode上的股票系列题

【在 j*****y 的大作中提到】

: 两个股票是什么题目阿？

a*m2012-09-24 07:09

18 楼

有两个股票n天的预测价格，限制每天交易（买/卖/不动）一次，最大化第n+1天的收益
。有区别但是思路差不多。

【在 j*****y 的大作中提到】

: 两个股票是什么题目阿？

p*22012-09-24 07:09

19 楼

感觉dp[i][j] 是 A在i城市，B在j城市的情况
最后返回dp[0][0]
如果i+1如果i+1==j的话， dp[i][j]=min(dp[i+2][j]+distance(i,i+2), dp[i][j+1]+
distance(j,j+1))
j

j*y2012-09-24 07:09

20 楼

这道题目 leetcode上没有吧？leetcode 上是只有一只股票的价格预测

【在 a********m 的大作中提到】

: 有两个股票n天的预测价格，限制每天交易（买/卖/不动）一次，最大化第n+1天的收益
: 。有区别但是思路差不多。

a*m2012-09-24 07:09

21 楼

哦。没本质区别，只是状态不太一样。

【在 j*****y 的大作中提到】

: 这道题目 leetcode上没有吧？leetcode 上是只有一只股票的价格预测

h*u2012-09-24 07:09

22 楼

Exactly. Thanks for the correction.

【在 j*****y 的大作中提到】

: nice idea.
: more precisely, C[i, j] is "the minimal cost with one stopping at i and
: another stopping at j when only considering the first j cities" ?

z*e2012-09-24 07:09

23 楼

o(n) solution
suppose we know the solution for first i cities, now we have a new city i+1,
only three options.
1. the new city in A
2. THE new city in B
3. all the first i cities in A, i+1 in B

【在 h**u 的大作中提到】

: Exactly. Thanks for the correction.

j*y2012-09-24 07:09

24 楼

Could you write down the optimal structure ? Thanks.

1,

【在 z*****e 的大作中提到】

: o(n) solution
: suppose we know the solution for first i cities, now we have a new city i+1,
: only three options.
: 1. the new city in A
: 2. THE new city in B
: 3. all the first i cities in A, i+1 in B

b*n2012-09-24 07:09

25 楼

a1, a2, a3近似等边三角形，边长为S，a1a2边略小，solution is A={a1, a2}, B={
a3 }, total = S - epsilon
下面加一个点a4, 让a1a4接近于0，solution should be A={a1, a4}, B={ a2, a3},
total = S + epsilon. 直接加a4到A{a1,a2}，B{a3}，或让a4独立为B都得不到最优解。

1,

【在 z*****e 的大作中提到】

b*n2012-09-24 07:09

26 楼

感觉这是正解

【在 h**u 的大作中提到】

m*n2012-09-24 07:09

27 楼

This problem is called "vehicle routing problem". The general version has a
capacity limit for each person, i.e., each person cannot travel for more
than a certain number of cities in your version.

contiguous)
their

【在 j*****y 的大作中提到】

z*w2012-09-24 07:09

28 楼

//用dp做的一个O(n^3)的解
import java.util.Scanner;
public class StreetTraversal {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] dis = new int[n][n];
for (int i = 0; i < n; i ++) {
dis[i] = new int[n];
for (int j = 0; j < n; j ++) {
dis[i][j] = sc.nextInt();
}
}
int[][] dp = new int[n+1][n+1];
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
dp[i][j] = Integer.MAX_VALUE / 2;

dp[1][1] = 0;
dp[1][2] = dis[0][1];
dp[2][1] = dis[0][1];
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
if (i == j) continue;
if (j == i - 1) {
for (int k = 1; k < j; k ++) {
dp[i][j] = Math.min(dp[i][j], dp[k][j] + dis[k-1][i-
1]);
}
} else if (i == j - 1) {
for (int k = 1; k < i; k ++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dis[k-1][j-
1]);
}
} else if (i > j) {
dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + dis[i-2][i-1]
);
} else {
dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + dis[j-1][j-2]
);
}
}
}
int res = Integer.MAX_VALUE/2;

for (int i = 1; i res = Math.min(res, dp[n][i]);
}
System.out.println(res);
}

}

m*k2012-09-24 07:09

29 楼

你的思路是对的，但忽略了一个细节：i==j-1时，你的k取值为[0, i), 也就是认为位
置j的前一个city不能为i，这显然是不对的。而当j的前一个city为i时，你的转换方程
会出问题，因为C[k,i]=C[i,i] （没有意义）。
另外，k==0也没有意义，因为所有cities必须分为两部分，不能只分成一部分。
综上，转换方程可以这样修改：
when i==j-1:
C[i,j] = min{C[k,i] + min{d[k,j], d[i,j]} }, k取值[1, i)

【在 h**u 的大作中提到】

m*k2012-09-24 07:09

30 楼

你这个应该是错的。
因为i+1==j时，你的转换方程中会同时出现：dp[i+2][i+1]和dp[i][i+2]，也就是对于
dp[a][b], 同时出现了a>b和ab和a。除非特别定义另外一种情况的意义，否则这个方程是不成立的。

【在 p*****2 的大作中提到】
: 感觉dp[i][j] 是 A在i城市，B在j城市的情况
: 最后返回dp[0][0]
: 如果i+1: 如果i+1==j的话， dp[i][j]=min(dp[i+2][j]+distance(i,i+2), dp[i][j+1]+
: distance(j,j+1))
: j

g*u2012-09-24 07:09

31 楼

这个题比VRP简单的地方是限定了ordered sequence.所以问题还是非常不一样的。

a

【在 m***n 的大作中提到】

: This problem is called "vehicle routing problem". The general version has a
: capacity limit for each person, i.e., each person cannot travel for more
: than a certain number of cities in your version.
:
: contiguous)
: their

g*u2012-09-24 07:09

32 楼

我觉得你这个不对的。比如在算 C[2,3]的时候，由于对称性，其实是在算 C[3,2]，它
可以由C[1,2]和C[0,2]两个子问题得出。
C[2,3]=C[3,2]=min(C[1,2]+d[1,3],C[0,2]+d[0,3]);
当然我们只要存C[2,3]就够了,不用存C[3,2].
C[0,2]+d[0,3]这种情况是指一个车从city 1出发，到city 2, 另一个车从city 3出发
，不到任何其他城市。这种情况是valid的。

【在 m***k 的大作中提到】

: 你的思路是对的，但忽略了一个细节：i==j-1时，你的k取值为[0, i), 也就是认为位
: 置j的前一个city不能为i，这显然是不对的。而当j的前一个city为i时，你的转换方程
: 会出问题，因为C[k,i]=C[i,i] （没有意义）。
: 另外，k==0也没有意义，因为所有cities必须分为两部分，不能只分成一部分。
: 综上，转换方程可以这样修改：
: when i==j-1:
: C[i,j] = min{C[k,i] + min{d[k,j], d[i,j]} }, k取值[1, i)

p*22012-09-24 07:09

33 楼

没明白这个时候不就两种情况吗或者a走或者b走

【在 m***k 的大作中提到】

: 你这个应该是错的。
: 因为i+1==j时，你的转换方程中会同时出现：dp[i+2][i+1]和dp[i][i+2]，也就是对于
: dp[a][b], 同时出现了a>b和ab和a: 。除非特别定义另外一种情况的意义，否则这个方程是不成立的。