在微软亚洲研究院上班,大家早上来第一件事是做什么呢?查看邮件?不,是去水房拿饮料:绿茶、王老吉、星巴克咖啡、可口可乐……(当然,还是有很多同事把拿饮料当作第二件事)。
阿姨们每天都会准备很多的饮料给大家,为了提高服务质量,同时也会统计大家对每种饮料满意度。一段时间后,阿姨们已经有了大批的数据。她们希望能从这些数据中挖掘出一些有用的信息,以使大家的满意度和值最大。某天早上,当实习生小飞第一个冲进水房并一次拿了五个酸奶、四个王老吉、三个鲜橙多时,阿姨们逮住了他,要他解决满意度最大化的问题。
从阿姨们统计的数据中,小飞可以知道大家对每一种饮料的满意度。阿姨们还告诉小飞, STC(Smart Tea Corp.)负责给研究院供应饮料,每天总量为V。STC很神奇,他们的每种饮料的单个容量都是2的方幂,比如王老吉,都是2^3=8升的,可乐都是2^5=32升的。当然STC的存货也是有限的,这会是每种饮料的购买量上限。统计数据中用(饮料名字,容量,数量,满意度)描述每一种饮料。
那么,小飞如何完成这个任务,求出保证最大满意度的购买量呢?
相关资源:
《编程之美》编辑部 | 《编程之美》豆瓣 | 《编程之美》互动网购买 | 作者Blog