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分钟凭聪明就能想出来的。 |