一道面试题——取珠宝 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道面试题——取珠宝

一道面试题——取珠宝# JobHunting - 待字闺中

h*62010-08-25 07:08

1 楼

某公司的电面题，以前没见过，觉得有点意思，就贴在这里。
一些珠宝排成一行，每个珠宝都有一个正整数价值。两人玩一个游戏，每人每回合可以从任意一端取一个珠宝，直到全部珠宝取完，所取得珠宝总价值最大的获胜。已知每个珠宝的价值，假设两人都特别聪明，求先取的人最多能取到多少价值的珠宝？
自定义函数参数和返回值。

d*e2010-08-25 07:08

2 楼

觉得总是取剩下里面最大价值的不就赢了？

以从任意一端取一个珠宝，直到全部珠宝取完，所取得珠宝总价值最大的获胜。已知每
个珠宝的价值，假设两人都特别聪明，求先取的人最多能取到多少价值的珠宝？

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

: 某公司的电面题，以前没见过，觉得有点意思，就贴在这里。
: 一些珠宝排成一行，每个珠宝都有一个正整数价值。两人玩一个游戏，每人每回合可以从任意一端取一个珠宝，直到全部珠宝取完，所取得珠宝总价值最大的获胜。已知每个珠宝的价值，假设两人都特别聪明，求先取的人最多能取到多少价值的珠宝？
: 自定义函数参数和返回值。

z*n2010-08-25 07:08

3 楼

只能从两端取。。。
感觉是个dp题

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

: 觉得总是取剩下里面最大价值的不就赢了？
:
: 以从任意一端取一个珠宝，直到全部珠宝取完，所取得珠宝总价值最大的获胜。已知每
: 个珠宝的价值，假设两人都特别聪明，求先取的人最多能取到多少价值的珠宝？

t*a2010-08-25 07:08

4 楼

O(n^2) DP solution here:
#ifdef HAVE_CONFIG_H
#include
#endif
#include
#include
int a[] = {4,6,1,7,2,10,8,5,3,9};
const int n = 10;
int sum[n][n];
int best[n][n];
int game(int a[], int start, int stop) {
if (start > stop) {
return 0;
} else if (best[start][stop]!=-1) {
return best[start][stop];
} else {
int s1 = sum[start+1][stop] - game(a, start+1, stop) + a[start];
int s2 = sum[start][stop-1] - game(a, start, stop-1) +

y*d2010-08-25 07:08

5 楼

这是 2^n 吧

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

: O(n^2) DP solution here:
: #ifdef HAVE_CONFIG_H
: #include
: #endif
: #include
: #include
: int a[] = {4,6,1,7,2,10,8,5,3,9};
: const int n = 10;
: int sum[n][n];
: int best[n][n];

t*a2010-08-25 07:08

6 楼

O(n^2)
fill best[n][n]

y*d2010-08-25 07:08

7 楼

u r right

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

: O(n^2)
: fill best[n][n]

d*e2010-08-25 07:08

8 楼

可不可以解释一下思路？
我运行出来的结果是37，那每一步是怎么取的呢？
因为每人取五个，我猜37 = 10 + 9 + 8 + 7 + 3，或者类似的。问题是第一个人取了
10，第二个怎么可能不取9?
谢谢。

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

: O(n^2) DP solution here:
: #ifdef HAVE_CONFIG_H
: #include
: #endif
: #include
: #include
: int a[] = {4,6,1,7,2,10,8,5,3,9};
: const int n = 10;
: int sum[n][n];
: int best[n][n];

z*n2010-08-25 07:08

9 楼

best(i,j)=max(a[i]+best(i-2,j), a[i]+best(i-1),(j-1),a[j]+best(i-1)(j-1), a[
j]+best(i, j-2))
初始情况就是如果i==j，return a[i]；如果i>j, return 0。
调用时候调用best(0,n-1)。
思路就是一共就4种取法，你取最左，对手取次左；你取最左，对手取最右；你取最右，
对手取最左；你取最右，对手取次右
这四种情况，你都递归算一下剩余子问题的最优方案，最优的那个就是了

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

: 可不可以解释一下思路？
: 我运行出来的结果是37，那每一步是怎么取的呢？
: 因为每人取五个，我猜37 = 10 + 9 + 8 + 7 + 3，或者类似的。问题是第一个人取了
: 10，第二个怎么可能不取9?
: 谢谢。

h*62010-08-25 07:08

10 楼

to Done:
你没有理解题意，只能从两端开始取，也就是第一轮只能取4或9，不能取10。
to zysxqn:
双方各取一次确实是四种取法，不过并不是在这四种情况中找最优，而是每两种情况
找出最差再找最优。因为对手的最优，是我方的最差。

z*n2010-08-25 07:08

11 楼

感觉题目问的是最多有可能得到多少，这样不是应该理解成如果对手很傻，或者对手配
合的情况下？

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

: to Done:
: 你没有理解题意，只能从两端开始取，也就是第一轮只能取4或9，不能取10。
: to zysxqn:
: 双方各取一次确实是四种取法，不过并不是在这四种情况中找最优，而是每两种情况
: 找出最差再找最优。因为对手的最优，是我方的最差。

f*g2010-08-25 07:08

12 楼

不能保证先取的总赢吧，比如131, 13131，先取得肯定输

z*n2010-08-25 07:08

13 楼

题目只是问先取的最多能得到多少珠宝，没有要求赢，也没说对方什么策略
所以我的理解是，假设对方很傻，完全配合你，根据输入的珠宝排列，最多能得到多少
珠宝

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

: 不能保证先取的总赢吧，比如131, 13131，先取得肯定输

b*a2010-08-25 07:08

14 楼

我覺得這個應該是用剪枝的那種思路把,就是假設對手也總會選擇最優解

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

: 题目只是问先取的最多能得到多少珠宝，没有要求赢，也没说对方什么策略
: 所以我的理解是，假设对方很傻，完全配合你，根据输入的珠宝排列，最多能得到多少
: 珠宝

B*52010-08-25 07:08

15 楼

没说对方的策略，但是说了对方足够聪明，所以我觉得对方总会去他们最优的方法。。。

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

d*e2010-08-25 07:08

16 楼

谢谢。
我的确没看清 -_-!
当时没看到那“一端”两个字.
再仔细研究一下。

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

j*u2010-08-25 07:08

17 楼

珠宝价值 p_1, p_2, ..., p_n
denote:
sum(i ,j) = p_i + p_i+1 + ... + p_n
recursion:
先拿的是最多是总数减去后拿的最多->
best(i, j) = max{ sum(i, j) - best(i+1, j), sum(i, j) - best(i,j-1) }
=sum(i, j) - min{ best(i+1, j), best(i, j-1) }
所以先拿的策略是两种情况中让后拿的拿得最少,下面这些是要算的：
best(1, n)

best(2, n)--best(1, n-1)
best(3, n)--best(2, n-1)--best(1, n-2)
...
best(i, n)--best(i-1, n-1)--best(2, n-(i-2))--best(1, n-(i-1))
...
best(n-1, n)--best(n-2, n-1) ................ best(1, 2)
p_n p_n-1

h*k2010-08-25 07:08

18 楼

不错，我有个另外的思路，不需要计算sum(i,j).
best(i,j) = max( a[i] + min( best(i+2,j), best(i+1,j-1) ),
a[j] + min( best(i+1,j-1), best(i, j-2) ) );
a[i], a[j] 分别指第i个和第j个珠宝的价值。best(i,j)指从第i个到第j个珠宝中选择
的最多的珠宝价值。
选择的含义是，如果选择了a[i]，那么对手只能选择a[i+1]或者a[j]，而且对手肯定会
选择一种方案，让你之后的收益最小，所以选择a[i]的最大收益是a[i]+min( best(i+2
,j), best(i+1,j-1) )；相似的我们可以知道选择a[j]后的最大可能收益。
终止条件是，if( i == j ) best(i,j) = a[i];
if( i+1 == j ） best(i,j) = max(a[i],a[j]);
时间复杂度还是O(n^2)。但是可能会比junwu的算法稍微快一些，因为迭代的时候是步
长是2，而junwu的算法的步长是1。

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

: 珠宝价值 p_1, p_2, ..., p_n
: denote:
: sum(i ,j) = p_i + p_i+1 + ... + p_n
: recursion:
: 先拿的是最多是总数减去后拿的最多->
: best(i, j) = max{ sum(i, j) - best(i+1, j), sum(i, j) - best(i,j-1) }
: =sum(i, j) - min{ best(i+1, j), best(i, j-1) }
: 所以先拿的策略是两种情况中让后拿的拿得最少,下面这些是要算的：
: best(1, n)
: