Facebook电面面经

今天面试遇到了一个奇葩的问题,和大家分享一下。
面试官是个白人妹子,人很好。题目是背包问题的变种。

在普通的背包问题中,背包的容积和物品的重量都可以不是整数,但是物品的价值只能是1或者2。

我感觉用dp没法做,就往贪心算法的方向去想了,觉得应该把物品按价值分两组然后分别排序,最后也没做出来。

如果大家有想法欢迎交流。

看面经啊,谢谢各位了!

请问楼主投的是哪个职位呀

能不能给几个数字 有点没看懂

  1. 物品按照价值分成两组,sort一下
    double[] valueOne,
    double[] valueTwo.
    接下来的步骤两者都从左到右greedy操作
  2. 背包先放满 valueTwo 里面的物品,记录一个 maxValue
  3. 背包拿出一个里面重的valueTwo 物品,再放满valueOne的物品,update maxValue
  4. 重复3,开始的时候总价值会变到,然后会变小
  5. 返回maxValue

2,4有可以优化的地方,不过复杂度应该是不变的。代码量会变大,不划算。

补充内容 (2018-11-6 10:26):
3.背包拿出一个里面【最】重的valueTwo 物品,再放满valueOne的物品,update maxValue
4. 重复3,开始的时候总价值会变【大】,然后会变小

是否可以用整数的近似

应该不行吧,近似的话0.5和1.49就都按1算吗?

看起来应该是对的,可以证明吗?

比如物品1的重量是1.2,价值是1,物品2的重量是2.1,价值是2。背包的重量比如是3.1

算每点价值需要多少重量,然后从小到大往里塞,可能有个2的塞不进就往后找1的

貌似不行,比如有两个物品重量都是4,价值是2。有4个物品重量都是1.5,价值是1。背包重量是6。最优解是装4个价值是1的。

补充内容 (2018-11-7 01:57):
啊这个例子不对。。。我大脑短路了

补充内容 (2018-11-7 02:02):
你这个答案貌似是对的,但是怎么证明呢?