Facebook电面面经

漫漫人生路 发表于 2018-11-16 02:26
用1塞满放进heap的时候，是按照重量从大到小排序的吧，这样你往外拿的时候才会从最重的开始往外拿。
你 ...

直接用FOR循环用1塞满，然后再用WHILE循环把1一个一个往外拿，每次拿一个就试着把2放满去打擂台，开始的时候总的value会上升，直到总的value下降了，之前那个峰值就是最优解。

mengkez 发表于 2018-11-16 02:33
直接用FOR循环用1塞满，然后再用WHILE循环把1一个一个往外拿，每次拿一个就试着把2放满去打擂台，开始的 ...

你往外拿的时候不用heap sort从最重的开始往外拿么？


补充内容 (2018-11-16 05:20):
同学，我这里想讨论的是heap comparator的设计。正如我之前所说的，你如果比较单位重量的价值往外拿，也可以。单纯比较重量或是价值，往外拿的时候都会有问题。

漫漫人生路 发表于 2018-11-16 05:12
你往外拿的时候不用heap sort从最重的开始往外拿么？

不用啊，先把所有的按value分两堆，然后每一堆按重量排序，然后按重量从小到大的顺序往包里放，往外拿的时候就从后往前拿。

mengkez 发表于 2018-11-16 05:15
不用啊，先把所有的按value分两堆，然后每一堆按重量排序，然后按重量从小到大的顺序往包里放，往外拿的 ...

那么问题来了，后面的item价值有1，有2， 重量也不同，你从后面是想拿价值为1的最重的对吧？你怎么保证，塞2进去之后，后面的一定是价值为1的最重的？

有两个array分别是按重量从小到大排好序的价值为1和2物品。
首先先从array1的index0开始往里放东西，直到放满，记录下此时的index和总重量，然后外拿出来一个，index--。
这时再从array2的index0开始往里放东西，直到放满，比较重量。
然后再重复上面两个步骤就可以啦

mengkez 发表于 2018-11-16 05:33
有两个array分别是按重量从小到大排好序的价值为1和2物品。
首先先从array1的index0开始往里放东西，直到 ...

这样也可以。不过，一旦物品价值为任意整数，就不能用这种方法了

array1 sort价值是1的物品，长度m
array2 sort价值是2的物品，长度n
如果optimal solution取i-th物品in array1，那么必定也取i-1th物品，因为i-1比i轻，推广可知必须取[0, i]所有物品
array2 同理
因此外循环计算从array1取[0,i]的价值，内循环计算从array2取[0,j]的价值，相加得到总价值
复杂度O(m*n)

尝试写了一下楼主说的解法的核心代码 (偷懒省略了把输入拆分成两个数组和按重量从小到大排序的过程), 如果有错误, 希望大家可以告诉我, 谢谢. 还有哈, 谢谢楼主的分享!
```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));
    }
}
```

upup感谢楼主啊分享～

mengkez 发表于 2018-11-7 01:31
看起来应该是对的，可以证明吗？

物品的放法一共就是从全是value 2 的物品， 然后value 2 和 value 1 物品的混合，再到全是value 1 物品，这个算法就是考虑了在这么多种放法里，每一种能够取得放法的最大value，再从最大的value里取最大的。