一道腾讯的编程题。

Question

m个任务，第i个任务需要Xi的时间去完成，难度为Yi。有m台机器，第i台机器最长工作时间为Zi，机器等级为Wi。对于一个任务只能交由一台机器完成，任务被完成的条件为：任务所需时间Xi小于机器最长工作时间Zi，任务难度Yi小于等于机器等级Wi。任务被第i台机器完成的收益为200*Xi+3*Yi。一台机器只能分配一个任务。想完成尽可能多的任务，若有多种方案，求收益最大的那个？输入：共m+n+1行第一行：n m接下来n行：Zi Wi接下来m行：Xi Yi输出：任务完成数 收益示例：输入1 2100 3100 2100 1输出1 20006

Answer 1

我感觉，把任务排个序，把箱子排个序，从大到小，然后按照顺序把任务依次放到箱子里。因为一个机器只能装一个任务，所以就不是背包问题了。一个机器只能完成一个任务，当然是选择收益最高的那个任务去完成。把任务收益从大到小排序，依次完成。