Facebook电面面经

pandami

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

drool

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

Sure not rounding, I meant ceiling.

drool

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

swordfeng

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

mengkez

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

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

T大农民伯伯

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

漫漫人生路

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

漫漫人生路 · 2018-11-10 02:19:15

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

mengkez · 2018-11-16 01:09:21

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

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

漫漫人生路 · 2018-11-16 02:26:44

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