经典算法问题

背包问题

01背包问题：有数件物品，每样物品均有不同的价值和重量，先给定一个背包容量大小，求背包能装下的最大价值。

分数背包问题：在01背包问题的基础上，每样物品可以只拿一部分。

完全背包问题：在01背包问题的基础上，每样物品有无限个（即可重复装包），求背包能装下的最大价值。

分组背包问题：在01背包问题的基础上，把数样物品改为数组物品，每组物品中只能选择一件，求背包能装下的最大价值。

dp或贪心算法来解决，贪心算法有时不一定能求出最优解，分数背包问题用贪心算法一定能高效求出最优解，其他背包问题用dp最稳妥。

字符串序列问题

与字符串序列有关的问题：

最大连续子串和：

最长公共子序列：

序列编辑问题：

最长递增子序列：

整数拆分问题：

序列问题用dp解决最好，定义好合适的dp数组，列出转移方程就如喝水般容易了，最重要的还是dp数组的设计。

流水线作业调度问题

有一批作业，都需要分别在A机器上处理，然后再到B机器上处理，如作业处理顺序安排不当，则容易出现作业总是要等待上一个作业在B机器上处理完毕的情况，因此合理的调度很重要。请求出最佳调度方案，使得处理完所有作业花费时间最短。

通过贪心johnson算法，分支限界算法，回溯法来完成。

任务分配问题

有一组任务，一组人员，不同人员处理不同的任务有不同费用，请合理安排任务分配方案，使得总花费最少。

通过蛮力法，回溯法，分支限界法来解决。

多机调度问题

有一组机器，一组作业，每个作业都有对应的执行时长，如何调度作业才能使得最短时间内完成所有作业。

贪心法完成

Huffman编码

求一组数据的Huffman编码

贪心法完成

资源分配问题

有一组资源，将不同的资源分配给不同的使用者有不同的收益，求最大收益，和任务分配问题反过来有点像，但资源分配问题本身就是个抽象概括，根据问题的不同，资源的数量和种类都可以是多个或单个。

采用dp最好

活动安排问题

有一组活动，每个活动都有起始时间，如何安排活动，才能在一天内完成最多的活动？

回溯和贪心法来解决，贪心法真的高效！

N皇后问题

这里进一步讨论N皇后问题 并加以优化

回溯法或Las Vegas算法当乐子看看，不过思想还是挺巧妙的

汉诺塔问题

递归的话简直秒杀，这里讨论一下非递归的情况。

棋盘覆盖问题

分治秒了，但是因为这问题之前恶心过我，有必要报仇雪恨，在这里再码一遍他！

排序问题

排序问题及其衍生问题：以快排的第K大/小数为主。

深度分析快排和归并排序在边界上的处理细节。