狗狗家

第四题举个例子， 1号 1小时 10块钱， 2号 3小时12块钱， 3号 3小时12块钱。

这样选一个人就选1号 总共花费10块
选两个人选2号和3号，一共24块钱， 如果选1号和2号就是10 *（3 + 1） = 40

这个并不满足局部最优解啊，怎么用DP？

martin5678 发表于 2018-6-19 16:35
第四题举个例子， 1号 1小时 10块钱， 2号 3小时12块钱， 3号 3小时12块钱。

这样选一个人就选1号 总共 ...

同问。只想到了一个nlogn的解法....

martin5678 发表于 2018-6-19 16:35
第四题举个例子， 1号 1小时 10块钱， 2号 3小时12块钱， 3号 3小时12块钱。

这样选一个人就选1号 总共 ...

我刚用DP推了一下你这个例子，没什么问题。
本来想回答你的，但有个人问他问题跟问空气一样，不想让他看，回头私信你吧。

FTD2014 发表于 2018-6-20 00:34
我刚用DP推了一下你这个例子，没什么问题。
本来想回答你的，但有个人问他问题跟问空气一样，不想让他看 ...

不好意思~我早上有点忙，回了一条就有急事出去了。~~~我刚才又想了想，觉得DP的n并不能直接从n-1推演（当然也有可能是我的DP状态错了）。比如A工作10小时，每小时rate $1, B工作也是10小时，每小时rate 也是$1，C工作 5小时，每小时rate $3，D工作3小时，每小时rate $4。那么选两个人应该选A和B，但是选三个人应该是A，C，D或者B，C，D。三个人的解并不等于两个人的最优解加额外一个人。（当然，再说一遍，我的DP公式可能是错的）。

补充内容 (2018-6-20 01:19):
另外，我也在论坛上问很多问题，但是我自己是从来不觉得别人obligated to回答我的问题，尤其别人是没有义务第一时间内去回答我的问题。论坛上有很多好心的大牛，我都从他们身上受益良多，比如tinylic, Ramily

补充内容 (2018-6-20 01:24):
还有其他人，我就不一一列举了。我自己的看法: 在这里别人帮你解惑，我很感激。但是对方没有义务去帮我，我也问很多问题得不到回答，但我从来不会想要去指责别人。Nobody gets paid to help you.

hankok 发表于 2018-6-19 08:34
感觉可以先把所有人按时薪高低排序用一个priorityqueue存起来，遍历所有情况（dfs, k就是dfs的深度），从选 ...

错了是 n*k^n

补充内容 (2018-6-20 02:09):
想不出怎么用DP.. 感觉和利口八二六比较像,用排序+2pointer，一会研究一下它的greedy解法

idatascience 发表于 2018-6-19 21:07
同问。只想到了一个nlogn的解法....

nlogn是怎么做的啊

请问楼主在哪里面的？

nibuxing 发表于 2018-6-20 09:46
nlogn是怎么做的啊

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

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

补充内容 (2018-6-20 10:06):
手抖了，把积分打错了....汗，感觉自己真的跟这个积分很耦合:) 这里发下，我的解法也是先排序再遍历。跟DFS层主不同的是，做的遍历的过程中没有指数的复杂度~只是nlogk，所以总体上是nlogn

idatascience 发表于 2018-6-20 09:53
**** 本内容被作者隐藏 ****

补充内容 (2018-6-20 10:06):

粗略过了一下 楼上没错 是nlogn级别的

按pay排序(nlogn)：
rate=[3, 4, 5, 6]
time=[9, 6, 5, 7]

e.g. 如果选k=3个人，就先分别算出rate最大为rate[n-1], rate[n-2] ... rate[3] 情况(n-2种)下的pay
rate=6, pay=rate*time=[54, 36, 30, 42]   (找出最小的k个之和sum1，用priority queue o(logn) )
rate=5, pay=rate*time=[45, 30, 25, INT_MAX]     (找出最小的k个之和sum2，用priority queue o(logn) )
sum=min(sumX)

总的复杂度 o(  nlogn + nlogn )  = o(nlogn)

补充内容 (2018-6-20 11:06):
按rate排序

补充内容 (2018-6-20 14:22):
建priorityqueue - nlogk
总的复杂度 o(  nlogn + (n-k)nlogk )

idatascience 发表于 2018-6-20 09:53
**** 本内容被作者隐藏 ****

补充内容 (2018-6-20 10:06):

我是dfs层主 才疏学浅，当时看着像DFS 现在发现没用到 你用的dp公式？求赐教