一道腾讯的编程题。

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 2

100 3

100 2

100 1

输出

1 20006

Answer 1

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