Google电面，求大米~

蛮有趣的题。设置了比较低的分数限制，方便地里的同胞们看到。求大米，给大米自己不扣米~

【hide=80】
基本就是个

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

- 1

然后求车上能够容下的人的最大的幸福分数是多少。用DP解法。

knight0clk 发表于 2019-7-26 01:04
如果固定坐n人，不是取前n个能产生幸福分数和最大的那几个人？

整个string是由逗号分开来的多个group。每个group不可以拆分。。。例如WMC是一家，必须一起

mgnhjkl 发表于 2019-7-25 21:33
这个为什么不是greedy每次取幸福指数最大的人？

这是一个knapsack的变形：考虑每群人的人数是weight，每群人的总幸福指数是value

cyx32524 发表于 2019-7-29 13:33
也是要155个积分才能看到，不算低了

我记得只设了80的门槛。。。hide=80

楼主这个是full time还是intern的？

钢铁侠吉米 发表于 2019-7-25 12:04
楼主这个是full time还是intern的？

Full time

这个为什么不是greedy每次取幸福指数最大的人？

是的。这是个典型的0/1 knapsack问题。求大米。

如果固定坐n人，不是取前n个能产生幸福分数和最大的那几个人？

想了个follow up
比如 最多坐20个人 然后男最多10个 女最多10个 老最多5个 少最多5个这种
求最大幸福度

moron 发表于 2019/07/25 22:46:22


这是一个knapsack的变形：考虑每群人的人数是weight，每群人的总幸福指数是value

多谢，我以为是一个string一个人，只不过有WS这样的属性。。