一道面试算法题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道面试算法题

一道面试算法题# JobHunting - 待字闺中

s*n2010-07-20 07:07

1 楼

Write an algorithm, with inputs [D1,D2,...,DN,Y]
D1Given \sum_1_N Xi*Di = Y,where Y is an known integer, and Xi's are non-
negative integers
Output [X1,X2,...XN] which minimize (\sum_1_N Xi)
死在这题上面，对方说可以不efficient，只要给一个algorithm。我说枚举法，找到所
有符合的解，看哪个最小。但是好像对方不喜欢，说了句fair enough，就byebye了。
又fail了一个phone interview, 5555。
请问有没有比较好的复习算法的书，谢谢。

m*h2010-07-20 07:07

2 楼

If all x are non-negative.....
Y=sum(di*xi)<=sum(dn*xi)=dn*sum(xi)
since d1Then min(sum(xi))=Y/dn
which is
0,0,0,...,0,Y/dn
Is this right?

m*h2010-07-20 07:07

3 楼

not complete, not a fair enough answer @[email protected]

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

: If all x are non-negative.....
: Y=sum(di*xi)<=sum(dn*xi)=dn*sum(xi)
: since d1: Then min(sum(xi))=Y/dn
: which is
: 0,0,0,...,0,Y/dn
: Is this right?

h*62010-07-20 07:07

4 楼

不就是背包问题吗，分 Y=DN^2 两种情况处理。
前者复杂度是O(Y)，后者O(N*DN)

p*n2010-07-20 07:07

5 楼

把 D2,...,DN 按从大到小的顺序排序
假设排序后是Di, Di+1, Di+2, ..., Dk

用 Y/Di，商就是Xi，假设余数是Ri，再用Ri/Di+1，以此类推，直到 Rm/Dm为0，剩下
的就用X1
个D1补上，因为D1=1,所以多出来的总能用D1补上。
这题很象经典题 knap-sack的变体题，看看这个link下的DP问题，应该会有启发
http://people.csail.mit.edu/bdean/6.046/dp/

s*n2010-07-20 07:07

6 楼

sorry, forget to mention
Di, Y are positive integers, and Xi are non-negative integers

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

: If all x are non-negative.....
: Y=sum(di*xi)<=sum(dn*xi)=dn*sum(xi)
: since d1: Then min(sum(xi))=Y/dn
: which is
: 0,0,0,...,0,Y/dn
: Is this right?

m*h2010-07-20 07:07

7 楼

Then I think my logic is right, and ponyqian gave the complete solution

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

: sorry, forget to mention
: Di, Y are positive integers, and Xi are non-negative integers

t*a2010-07-20 07:07

8 楼

It can be solved by dynamic programming.
set matrix: m = [row=y, col=len(d)]
set elements in m to undefined
for i in 1:y:
m[i,1] = [i, [0] * (len(d)-1)] # basic solutions when there is only one d
def solve_x(y, n):
if defined m[y, n]:
return m[y, n]
else:
m[y, n] = minimal(sum(solve_x(y-x[n]*i,n-1)))
the complexity is less then y * len(d)

d*22010-07-20 07:07

9 楼

starting from maximizing coefficient for d_n first, d_{n-1} next and so on,
when fail, backtracking.

s*n2010-07-20 07:07

10 楼

that's my first thought, however it doesn't always work
Assume you have D=[15,10,1], and Y=20,
using this method gives you Y=1*15+0*10+5*1, \sum Xi=6
however the solution should be Y=0*15+2*10+0*1, \sum Xi=2

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

: 把 D2,...,DN 按从大到小的顺序排序
: 假设排序后是Di, Di+1, Di+2, ..., Dk
:
: 用 Y/Di，商就是Xi，假设余数是Ri，再用Ri/Di+1，以此类推，直到 Rm/Dm为0，剩下
: 的就用X1
: 个D1补上，因为D1=1,所以多出来的总能用D1补上。
: 这题很象经典题 knap-sack的变体题，看看这个link下的DP问题，应该会有启发
: http://people.csail.mit.edu/bdean/6.046/dp/

s*n2010-07-20 07:07

11 楼

the optimal solution may not have max coef for Dn, see my counter example
above.

,

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

: starting from maximizing coefficient for d_n first, d_{n-1} next and so on,
: when fail, backtracking.

d*22010-07-20 07:07

12 楼

that is where backtracking comes from. should clarify that backtrack by reducing
coefficient for previous larger d_i by 1 and repeat.

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

: the optimal solution may not have max coef for Dn, see my counter example
: above.
:
: ,

s*n2010-07-20 07:07

13 楼

Can you elaborate more?
Let's use D=[1,10,15], Y=20. You get max Xn=1, then?

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

:
: that is where backtracking comes from. should clarify that backtrack by reducing
: coefficient for previous larger d_i by 1 and repeat.

s*n2010-07-20 07:07

14 楼

reducing
Isn't that equal to "Mei Ju Fa"?

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

:
: that is where backtracking comes from. should clarify that backtrack by reducing
: coefficient for previous larger d_i by 1 and repeat.

c*42010-07-20 07:07

15 楼

通俗的描述是：给你N种硬币，每种硬币的面额D[i]也给你。规定每种硬币可以取任意
个（可以是0个），问
最少用几枚硬币可以组成面额Y。这个题目可以用动态规划，设一个数组ans[i][j],表
示用0到i种硬
币，拼出j面额所需要的最小数量。然后递推式为：
ans[i][j] = Min {n + ans[i-1][j-n*D[i]]} (0 <= n <= j/D[i])
意思是：对于第i种硬币，遍历可以取的个数n，然后看剩下的面额j-n*D[i]最少可以用
多少枚0到(i-
1)种硬币拼出来。

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

: Write an algorithm, with inputs [D1,D2,...,DN,Y]
: D1: Given \sum_1_N Xi*Di = Y,where Y is an known integer, and Xi's are non-
: negative integers
: Output [X1,X2,...XN] which minimize (\sum_1_N Xi)
: 死在这题上面，对方说可以不efficient，只要给一个algorithm。我说枚举法，找到所
: 有符合的解，看哪个最小。但是好像对方不喜欢，说了句fair enough，就byebye了。
: 又fail了一个phone interview, 5555。
: 请问有没有比较好的复习算法的书，谢谢。

d*22010-07-20 07:07

16 楼

right. should use dp.
T[i] is minimum number of coins for i value
init T[0] = 0
T[n] = min {if n>=d_i, T[n-d_i]+1, for all i}

【在 c********4 的大作中提到】

: 通俗的描述是：给你N种硬币，每种硬币的面额D[i]也给你。规定每种硬币可以取任意
: 个（可以是0个），问
: 最少用几枚硬币可以组成面额Y。这个题目可以用动态规划，设一个数组ans[i][j],表
: 示用0到i种硬
: 币，拼出j面额所需要的最小数量。然后递推式为：
: ans[i][j] = Min {n + ans[i-1][j-n*D[i]]} (0 <= n <= j/D[i])
: 意思是：对于第i种硬币，遍历可以取的个数n，然后看剩下的面额j-n*D[i]最少可以用
: 多少枚0到(i-
: 1)种硬币拼出来。

s*n2010-07-20 07:07

17 楼

got it, thank you very much

【在 c********4 的大作中提到】