s****n
发帖数: 1237 | 1 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。
请问有没有比较好的复习算法的书，谢谢。 | m******h
发帖数: 1059 | 2 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******h
发帖数: 1059 | 3 not complete, not a fair enough answer @_@
【在 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**6
发帖数: 4160 | 4 不就是背包问题吗，分 Y=DN^2 两种情况处理。
前者复杂度是O(Y)，后者O(N*DN) | p******n
发帖数: 32 | 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****n
发帖数: 1237 | 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******h
发帖数: 1059 | 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****a
发帖数: 1212 | 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****2
发帖数: 6250 | 9 starting from maximizing coefficient for d_n first, d_{n-1} next and so on,
when fail, backtracking. | s****n
发帖数: 1237 | 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****n
发帖数: 1237 | 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****2
发帖数: 6250 | 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****n
发帖数: 1237 | 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****n
发帖数: 1237 | 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********4
发帖数: 18 | 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****2
发帖数: 6250 | 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****n
发帖数: 1237 | 17 got it, thank you very much
【在 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)种硬币拼出来。
| i***1
发帖数: 95 | 18 O(Y)是DP，比较好理解。
O(N*DN）是怎么出来的？
【在 h**6 的大作中提到】
: 不就是背包问题吗，分 Y=DN^2 两种情况处理。
: 前者复杂度是O(Y)，后者O(N*DN)
| l*******g
发帖数: 4894 | 19 这个link不错。
【在 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/
| P********l
发帖数: 452 | | t****a
发帖数: 1212 | 21 PuTTYshell:
are u kidding?
x must be non-negative INTEGER!!! |
|
