分类： 算法

工厂机器安排(贪心)

Today the company has m tasks to complete. The ith task need xi minutes to complete. Meanwhile, this task has a difficulty level yi. The machine whose level below this task’s level yi cannot complete this task. If the company completes this task, they will get (500xi+2yi) dollars.

The company has n machines. Each machine has a maximum working time and a level. If the time for the task is more than the maximum working time of the machine, the machine can not complete this task. Each machine can only complete a task one day. Each task can only be completed by one machine.

The company hopes to maximize the number of the tasks which they can complete today. If there are multiple solutions, they hopes to make the money maximum.

批处理作业调度是要从 n 个作业的所有排列中找出有最小完成时间和的作业调度，所以批处理调度问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始时x = [1, .., n]是所给的 n 个作业，则相应的排列树由所有排列构成。

贪心算法有一道很经典的例题：会场安排问题。即一个会场最多活动与所有活动最少会场问题。

电话号码的数字组合，使用回溯法生成二叉树，得到所有情况。

有n个集装箱要装上2艘载重量分别为C1和C1的轮船。其中集装箱i的重量为Wi，且（W1+W2+….+Wn<=C1+C2）。 装载问题是，是否有一个合理装载方案，可将这n个集装箱都装上这2个轮船，若有，请给出解决方案。

小明经常玩一个矩阵取数游戏：对于一个给定的n x n的矩阵，矩阵中的每个元素aij表示该格子的价值，均为非负整数。游戏规则如下：小明从左上角走到右下角，只能向下向右走，经过某个格子，就能获得格子相应价值的奖励，请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大奖励值。

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于n。你需要让组成和的完全平方数的个数最少。