Facebook电面面经

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

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

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

家有想法欢迎交流。

求大米看面经啊，谢谢各位了！

尝试写了一下楼主说的解法的核心代码 (偷懒省略了把输入拆分成两个数组和按重量从小到大排序的过程), 如果有错误, 希望大家可以告诉我, 谢谢. 还有哈, 谢谢楼主的分享!
```java
public class Backpack {
    private static int maxValue(double[] valueOne, double[] valueTwo, double maxWeight) {
        double crtWeight = 0.0;
        int crtValue = 0;
        int i = -1;
        while (i + 1 < valueOne.length && crtWeight + valueOne[i + 1] <= maxWeight) {
            i++;
            crtWeight += valueOne[i];
            crtValue += 1;
        }
        int res = crtValue;
        int j = -1;
        while (i >= 0 && j + 1 < valueTwo.length) {
            crtWeight -= valueOne[i--];
            crtValue -= 1;
            while (j + 1 < valueTwo.length && crtWeight + valueTwo[j + 1] <= maxWeight) {
                j++;
                crtWeight += valueTwo[j];
                crtValue += 2;
            }
            res = Math.max(res, crtValue);
        }
        return res;
    }

    public static void main(String[] args) {
        double[] valueOne = {0.2, 0.2, 0.2};
        double[] valueTwo = {0.3, 0.3};
        double maxWeight = 0.6;
        System.out.println(maxValue(valueOne, valueTwo, maxWeight));

        double[] valueOne1 = {1.5, 1.5, 1.5, 1.5};
        double[] valueTwo1 = {4, 4};
        double maxWeight1 = 6;
        System.out.println(maxValue(valueOne1, valueTwo1, maxWeight1));
    }
}
```

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构成。

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

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

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

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

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，开始的时候总价值会变【大】，然后会变小

是否可以用整数的近似

drool 发表于 2018-11-6 10:39
是否可以用整数的近似

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

jih23 发表于 2018-11-6 10:24
1. 物品按照价值分成两组，sort一下
double[] valueOne,
double[] valueTwo.

看起来应该是对的，可以证明吗？

pandami 发表于 2018-11-6 10:06
能不能给几个数字 有点没看懂

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

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

swordfeng 发表于 2018-11-7 01:41
算每点价值需要多少重量，然后从小到大往里塞，可能有个2的塞不进就往后找1的

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

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

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