G家电面

原帖地址:一亩三分地

回馈地里。电面一共两题。第一题是给一组id和表示每个id出现概率的数组,概率之和为1.要求随机生成id,使得随机出的id满足之前的概率数组。
followup:如果id很多,调用这个随机生成方法的次数也很多,怎么优化
第二题大致是背包问题的变形,物品可切分,限制条件是如果放则必须放当前总体积的一半以上,求最后的最大价值。
followup: dp的空间优化

补充内容 (2015-8-22 13:57):
求大米,攒rp