Facebook电面面经

jih23 发表于 2018/11/06 10:24:13
1. 物品按照价值分成两组，sort一下
double[] valueOne,
double[] valueTwo.
接下来的步骤两者都从左到右greedy操作
2. 背包先放满 valueT...

在这个基础上这样改进 sort by weight从小到大
每次从v2里面取一个 v1里面取两个
比较重量 放入重量小的
直到剩余重量小于任意物品在v2 以及任意两个物体在v1
继续从v1里面取

原理 每次放入密度最大重量

这个题限制物体只有两个价值感觉其实降低难度

mengkez 发表于 2018-11-7 01:29
应该不行吧，近似的话0.5和1.49就都按1算吗？

Sure not rounding, I meant ceiling.

This is also close to the idea of rough estimate: https://stackoverflow.com/questions/36502507/knapsack-algorithm-using-decimal-values

mengkez 发表于 2018-11-7 01:55
貌似不行，比如有两个物品重量都是4，价值是2。有4个物品重量都是1.5，价值是1。背包重量是6。最优解是装 ...

想了一下这解法不太对的，实际上最优可能有一个价值为2的平均重量大于没拿的价值为1的
正确做法应该是这样：
把物品分成价值1和价值2两个数组，按照重量从小到大排，显然最优方案是这两个数组取靠左边的
先塞满1（或者2）的，然后从重量大的一个个往外拿，每次拿了之后尽量把价值2的从重量小的一个个往里塞，中间出现的最大价值就是最优结果了

swordfeng 发表于 2018-11-8 15:32
想了一下这解法不太对的，实际上最优可能有一个价值为2的平均重量大于没拿的价值为1的
正确做法应该是这 ...

对，我目前也觉得这样是对的。

这道题不是0-1整数规划吗，用分支界定法可以做。
https://blog.csdn.net/ktigerhero3/article/details/50385109

另外一个思路就是，可以记忆化搜素，用hashmap<value, weight>记录value为n的，weight小于背包size的最小重量，
最后结果返回hashmap中的最大key值即可。

swordfeng 发表于 2018-11-8 15:32
想了一下这解法不太对的，实际上最优可能有一个价值为2的平均重量大于没拿的价值为1的
正确做法应该是这 ...

感觉这个做法有问题，
往外拿的时候，从重量大的物品开始往外拿，还要考虑重量大的物品价值高低问题。
比如说，背包size为0.6
有3个物品价值为1， 重量均为0.2
有2个物品价值为2， 重量均为0.3
用1塞满的话，再往里加2，从重量大的开始往外拿，那么价值为2的物品又被拿出来。这样得到的结果是3，而实际结果应该为4.
感觉往外拿的时候，根据单位重量的价值高低往外拿，会好一些，不过又会有个隐藏问题就是计算精度问题。
而且，还有个边界问题就是，先塞满1但是最优解全部由2构成，或者先塞满2，最优解全部由1构成。

漫漫人生路 发表于 2018-11-10 02:19
感觉这个做法有问题，
往外拿的时候，从重量大的物品开始往外拿，还要考虑重量大的物品价值高低问题。
...

用1塞满以后只往外拿1，往里面塞2，不会再把2也拿出来了。

mengkez 发表于 2018-11-16 01:09
用1塞满以后只往外拿1，往里面塞2，不会再把2也拿出来了。

用1塞满放进heap的时候，是按照重量从大到小排序的吧，这样你往外拿的时候才会从最重的开始往外拿。
你往外拿的时候，又只往外拿1，那就要求heap按照价值从小到大排序确保你不会拿出来2，或者你每次遍历一遍heap中所有的值寻找符合条件的1.
这样comparator是得好好设计一下，如果，所有价值为2的比较的时候，都当做重量最小返回，倒是可以。希望follow up不会问，价值可以为任意整数吧。