今天面试遇到了一个奇葩的问题，和大家分享一下。
面试官是个白人妹子，人很好。题目是背包问题的变种。
在普通的背包问题中，背包的容积和物品的重量都可以不是整数，但是物品的价值只能是1或者2。
我感觉用dp没法做，就往贪心算法的方向去想了，觉得应该把物品按价值分两组然后分别排序，最后也没做出来。
如果大家有想法欢迎交流。
请问楼主投的是哪个职位呀
能不能给几个数字 有点没看懂
- 物品按照价值分成两组，sort一下
double[] valueOne,
double[] valueTwo.
接下来的步骤两者都从左到右greedy操作 - 背包先放满 valueTwo 里面的物品，记录一个 maxValue
- 背包拿出一个里面重的valueTwo 物品，再放满valueOne的物品，update maxValue
- 重复3，开始的时候总价值会变到，然后会变小
- 返回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):
你这个答案貌似是对的，但是怎么证明呢？