a**d
发帖数: 85 | 1 有两个矿A，B，有2n个工人，每个工人在A和B中挖矿的效
率不同，由两个数组给出。如果必须要有n个工人在A，n个工人在B里面，问如何使效率
最大。
感觉这个挺有趣的，好像是玩星际让老农去挖矿，然后怎么分配挖的最快。
感觉像是greedy,把效率排序，然后一个接一个分给A,B.
或者先把效率高的前n个分给A，然后挖完了再给B.
这样对吗？就只直觉，怎么用数学证明呢？ |
c***0
发帖数: 449 | 2 感觉只需要把a序列减去b序列，得出差值，根据差值排序，前n个给a后n个给b。不知
道有没有想错 |
m**********g
发帖数: 153 | 3 是不是可以DP?
input: In[2*n][2]
output: O[n]=O[2*(n-1)] +
max( In[2*n-2][0]+ In[2*n-1][1], In[2*n-2][1]+ In[2*n-1][0] );
【在 a**d 的大作中提到】
: 有两个矿A，B，有2n个工人，每个工人在A和B中挖矿的效
: 率不同，由两个数组给出。如果必须要有n个工人在A，n个工人在B里面，问如何使效率
: 最大。
: 感觉这个挺有趣的，好像是玩星际让老农去挖矿，然后怎么分配挖的最快。
: 感觉像是greedy,把效率排序，然后一个接一个分给A,B.
: 或者先把效率高的前n个分给A，然后挖完了再给B.
: 这样对吗？就只直觉，怎么用数学证明呢？
|
n****e
发帖数: 678 | 4 我觉得你的想法是对的。
a序 减去 b序，然后从小到大排序。前n个给a后n个给b。
【在 c***0 的大作中提到】
: 感觉只需要把a序列减去b序列，得出差值，根据差值排序，前n个给a后n个给b。不知
: 道有没有想错
|
c***0
发帖数: 449 | 5 应该是从大到小排序吧。
【在 n****e 的大作中提到】
: 我觉得你的想法是对的。
: a序 减去 b序，然后从小到大排序。前n个给a后n个给b。
|
a**d
发帖数: 85 | 6 请问能否解释一下？没太懂思路。
感觉DP也有道理
【在 c***0 的大作中提到】
: 感觉只需要把a序列减去b序列，得出差值，根据差值排序，前n个给a后n个给b。不知
: 道有没有想错
|
a**d
发帖数: 85 | 7 我觉得有道理，就是把2n排序，然后2个2个的分配给A或B。
可是怎么证明比这种情况好：先挑效率很高的前N个给A，后面的N个给B，然后A完成了
把效率高的前N个再给B
【在 m**********g 的大作中提到】
: 是不是可以DP?
: input: In[2*n][2]
: output: O[n]=O[2*(n-1)] +
: max( In[2*n-2][0]+ In[2*n-1][1], In[2*n-2][1]+ In[2*n-1][0] );
|
n****e
发帖数: 678 | 8 恩，是的。我弄错了。
【在 c***0 的大作中提到】
: 应该是从大到小排序吧。
|
|
D**********d
发帖数: 849 | 9 至少可以用 DP 中的背包问题解决，可以处理更 general 的情况，即两个数组不等。
具体是 计算出 sum/2, f_i(c) 为前 i 个物件里与 c 差的绝对值。
f_{i+1}(c) = min{ f_i(c), f_i(c-c_i), |c_i - c|}
c 从 0 --> sum/2 |
k******4
发帖数: 94 | 10 A = [ai], B = [bi], xi = 1 如果第i个人去A，xi=0如果第i个人去B
目标函数 S = \sum(xi*ai + (1-xi)*bi)
约束条件 \sum(xi) = n;
S = \sum(bi + xi(ai-bi)) = \sum(bi) + \sum(xi*(ai-bi))
为了是S最大，选前大的n个ai-bi，并将他们派去A，其它人去B。 |
|
|
n****e
发帖数: 678 | 11 为啥要用DP来解这道题，直接greedy就行了吧 |
a**d
发帖数: 85 | 12 谢谢，感觉很有道理
【在 k******4 的大作中提到】
: A = [ai], B = [bi], xi = 1 如果第i个人去A，xi=0如果第i个人去B
: 目标函数 S = \sum(xi*ai + (1-xi)*bi)
: 约束条件 \sum(xi) = n;
: S = \sum(bi + xi(ai-bi)) = \sum(bi) + \sum(xi*(ai-bi))
: 为了是S最大，选前大的n个ai-bi，并将他们派去A，其它人去B。
|
m**********g
发帖数: 153 | 13 嗯， 正解
【在 k******4 的大作中提到】
: A = [ai], B = [bi], xi = 1 如果第i个人去A，xi=0如果第i个人去B
: 目标函数 S = \sum(xi*ai + (1-xi)*bi)
: 约束条件 \sum(xi) = n;
: S = \sum(bi + xi(ai-bi)) = \sum(bi) + \sum(xi*(ai-bi))
: 为了是S最大，选前大的n个ai-bi，并将他们派去A，其它人去B。
|
c********e
发帖数: 186 | |
a**d
发帖数: 85 | 15 有两个矿A，B，有2n个工人，每个工人在A和B中挖矿的效
率不同，由两个数组给出。如果必须要有n个工人在A，n个工人在B里面，问如何使效率
最大。
感觉这个挺有趣的，好像是玩星际让老农去挖矿，然后怎么分配挖的最快。
感觉像是greedy,把效率排序，然后一个接一个分给A,B.
或者先把效率高的前n个分给A，然后挖完了再给B.
这样对吗？就只直觉，怎么用数学证明呢？ |
c***0
发帖数: 449 | 16 感觉只需要把a序列减去b序列，得出差值，根据差值排序，前n个给a后n个给b。不知
道有没有想错 |
m**********g
发帖数: 153 | 17 是不是可以DP?
input: In[2*n][2]
output: O[n]=O[2*(n-1)] +
max( In[2*n-2][0]+ In[2*n-1][1], In[2*n-2][1]+ In[2*n-1][0] );
【在 a**d 的大作中提到】
: 有两个矿A，B，有2n个工人，每个工人在A和B中挖矿的效
: 率不同，由两个数组给出。如果必须要有n个工人在A，n个工人在B里面，问如何使效率
: 最大。
: 感觉这个挺有趣的，好像是玩星际让老农去挖矿，然后怎么分配挖的最快。
: 感觉像是greedy,把效率排序，然后一个接一个分给A,B.
: 或者先把效率高的前n个分给A，然后挖完了再给B.
: 这样对吗？就只直觉，怎么用数学证明呢？
|
n****e
发帖数: 678 | 18 我觉得你的想法是对的。
a序 减去 b序，然后从小到大排序。前n个给a后n个给b。
【在 c***0 的大作中提到】
: 感觉只需要把a序列减去b序列，得出差值，根据差值排序，前n个给a后n个给b。不知
: 道有没有想错
|
c***0
发帖数: 449 | 19 应该是从大到小排序吧。
【在 n****e 的大作中提到】
: 我觉得你的想法是对的。
: a序 减去 b序，然后从小到大排序。前n个给a后n个给b。
|
a**d
发帖数: 85 | 20 请问能否解释一下？没太懂思路。
感觉DP也有道理
【在 c***0 的大作中提到】
: 感觉只需要把a序列减去b序列，得出差值，根据差值排序，前n个给a后n个给b。不知
: 道有没有想错
|
|
|
a**d
发帖数: 85 | 21 我觉得有道理，就是把2n排序，然后2个2个的分配给A或B。
可是怎么证明比这种情况好：先挑效率很高的前N个给A，后面的N个给B，然后A完成了
把效率高的前N个再给B
【在 m**********g 的大作中提到】
: 是不是可以DP?
: input: In[2*n][2]
: output: O[n]=O[2*(n-1)] +
: max( In[2*n-2][0]+ In[2*n-1][1], In[2*n-2][1]+ In[2*n-1][0] );
|
n****e
发帖数: 678 | 22 恩，是的。我弄错了。
【在 c***0 的大作中提到】
: 应该是从大到小排序吧。
|
D**********d
发帖数: 849 | 23 至少可以用 DP 中的背包问题解决，可以处理更 general 的情况，即两个数组不等。
具体是 计算出 sum/2, f_i(c) 为前 i 个物件里与 c 差的绝对值。
f_{i+1}(c) = min{ f_i(c), f_i(c-c_i), |c_i - c|}
c 从 0 --> sum/2 |
k******4
发帖数: 94 | 24 A = [ai], B = [bi], xi = 1 如果第i个人去A，xi=0如果第i个人去B
目标函数 S = \sum(xi*ai + (1-xi)*bi)
约束条件 \sum(xi) = n;
S = \sum(bi + xi(ai-bi)) = \sum(bi) + \sum(xi*(ai-bi))
为了是S最大，选前大的n个ai-bi，并将他们派去A，其它人去B。 |
n****e
发帖数: 678 | 25 为啥要用DP来解这道题，直接greedy就行了吧 |
a**d
发帖数: 85 | 26 谢谢，感觉很有道理
【在 k******4 的大作中提到】
: A = [ai], B = [bi], xi = 1 如果第i个人去A，xi=0如果第i个人去B
: 目标函数 S = \sum(xi*ai + (1-xi)*bi)
: 约束条件 \sum(xi) = n;
: S = \sum(bi + xi(ai-bi)) = \sum(bi) + \sum(xi*(ai-bi))
: 为了是S最大，选前大的n个ai-bi，并将他们派去A，其它人去B。
|
m**********g
发帖数: 153 | 27 嗯， 正解
【在 k******4 的大作中提到】
: A = [ai], B = [bi], xi = 1 如果第i个人去A，xi=0如果第i个人去B
: 目标函数 S = \sum(xi*ai + (1-xi)*bi)
: 约束条件 \sum(xi) = n;
: S = \sum(bi + xi(ai-bi)) = \sum(bi) + \sum(xi*(ai-bi))
: 为了是S最大，选前大的n个ai-bi，并将他们派去A，其它人去B。
|
c********e
发帖数: 186 | |
h*****u
发帖数: 109 | 29 上面几位都对。这个题应该属于Generalized Assignment Problem (GAP)的一个特例（
两矿），有polynomial解。
如果稍微改一下：有三个矿A，B，C, 有3n个工人，要求每个矿n个。这个应该是NP-
hard in strong sense. 面试估计需要上greedy algorithm. DP不会有pseudo
polynomial解。在Operations Research里还有多种方法，估计面试用不上。 |
b***e
发帖数: 1419 | 30 这类题都是匈牙利算法的变种。放狗搜一下吧。说实话的面试考这种图论题完全没有意
义。这不是5分钟凭聪明就能想出来的。 |
