2015年微软实习生招聘机试题,求大神给解答


2015年微软实习生招聘笔试题。求大神给解答。
2.jpg 1.jpg
已邀请:

cpcs - 诚实努力

赞同来自: July syddesk Rubywiwi


动态规划
dp[n][x][y][z] 表示前n个人雇佣x个男 y个女的 花费为z的时候 的最大总能力。
初值 dp[0][0][0][0] = 0
对第n个人 如果他的能力是v并且要的工资是s
则有
递推式

如果第n个人是男的
dp[n][x][y][z] = max(dp[n - 1][x - 1][y][z - v] + s, dp[n - 1][x][y][z])
如果第n个人是女的
dp[n][x][y][z] = max(dp[n - 1][x][y - 1][z - v] + s, dp[n - 1][x][y][z])

注意 如果z - v是负数 定义值为负无穷。
最后的解 总能力值是dp[N][X][Y][Z] N, X, Y都是题目输入的 , Z是使得这个值非负无穷的最小的值,即Z是总的花费(总工资)。
也就是说 输出第一行就是Z和dp[N][X][Y][Z]。
那么如何找到选了谁没选谁?
其实只要看一下dp[n][x][y][z]是由dp[n - 1][x][y][z]推出来 还是由dp[n - 1][x - 1][y][z - v] + s或者dp[n - 1][x][y - 1][z - v] + s推出来就可以了,就知道选不在选择第n个人。注意按题目意思 那个max符号 如果相等的时候是不选择第n个人的,因为字典顺序要尽可能小。

时间复杂度空间复杂度显然是 N * X * Y * Z 最大10^9 略大。
但是注意到X + Y <= N 之类的 还是有一些常熟上的优化的。

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~