软软校园招聘面经

eason0218 发表于 2019-9-13 23:29
😂这就是贪心啊；这不是DP因为没有限制条件，除非LZ没说

比如说array是11， 9， 2，2...2(此处有20个2)正确的做法是把9，11放在一个processor里处理，但是用贪心一定会把 11和9 分到不同的processor处理

爱树上的兔子 发表于 2019-9-14 02:10
比如说array是11， 9， 2，2...2(此处有20个2)正确的做法是把9，11放在一个processor里处理，但是用贪心 ...

那最好的情况是平均值？前两个processor尽量装到平均值，然后第三个processor看剩下多少？那我也不会了。。有啥思路吗

jolyon129 发表于 2019-9-13 22:40
终于搞懂了. 原来是 DP knapsack的变形 问题,  https://www.geeksforgeeks.org/partition-a-set-into-two-s ...

https://www.geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum/
跟楼上说的一样 DP是一样的 最后找分割点的时候因为要找2个(divide two 3 parts) 最后一步稍微改一下就可以做了
Min{sum - j*2  : dp[n][j]  == 1 }
=>
Min{abs(sum/3- (sum-j))+abs(sum/3- (j-i) )+ abs(sum/3- i)  : dp[n][j]  == 1 }  O(sum^2+n*sum)
knapsack DP www.geeksforgeeks.org 用的是 DP[# of items][weight]  这个题如果要和knapsack套关系的话要用 DP[# of items][value sum]的解法
楼上帮忙看看对不对
加米不扣米顺便求加米

您好，我问一下在哪里能找到campus interview的地点，我在网上找了半天都没找到，谢谢！

一一作宇 发表于 2019-9-20 01:21
您好，我问一下在哪里能找到campus interview的地点，我在网上找了半天都没找到，谢谢！

confirmation 邮件里就有

John0773 发表于 2019-9-16 01:47
https://www.geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset- ...

感觉不太对劲啊，分成两个的时候这个做法可行的原因是因为选了dp[n][j]以后剩下的集合一定可以和dp[n][j]代表的集合互斥，但是分成三个就不行了。
举一个反例，有一个5和四个1，这样的话最好的结果就是5单独一组，但是用dp的话所有的dp[n][j]都是true…估计会得出“可以分成三组每组和为3”的结论。

提个思路，可不可以用二分来做，lo 是sum/3，hi是sum,然后调用check函数找可行的最大值，不过check怎么写。。。

marrrrrkkkkkk 关注一下解法

我的想法是最朴实的DP。。。用一个hashset记录valuearr的不同情况，比如234,342,324这都是同一种情况，然后每次都循环这个set来穷举。。。因为有三个感觉要用数据记录的话，空间开销不是一般的大。。。。