其中我们主要学习的内容是算法的设计与分析。

在学习算法的过程中，还需要学习相关的概念：

以上五点会在后面的文章中逐一学习。

实例： 任务集 S = {1, 2, 3, 4, 5}， 加工时间: t1=3, t2=8, t3=5, t4=10, t5=15

算法：按加工时间(3,8,5,10,15) 从小到大安排

解：加工产品的顺序：1, 3, 2, 4, 5 。

总的完成时间为：

t = 3+(3+5)+(3+5+8)+(3+5+8+10)+(3+5+8+10+15) = 3×5 + 5×4 + 8×3 + 10×2 + 15 = 94

（注意规律）

针对上面的加工调度问题，在数学中有一整套建模的流程来求解。

问题建模：

对于上述调度问题的贪心算法，对于所有输入实例都得到最优解，可以给出如下的证明过程：

证明：假设调度f的第i，j项任务相邻且有逆序，即ti > tj ,交换任务i和j得到调度g，

在算法的设计过程中，各种各样的算法设计都需要有严格的证明验证所有实例都可以通过该算法达到最终的解。上面解决调度问题的时候，是凭直觉来使用贪心算法，但是直觉往往不正确。如下面的例子。

反例：

有4 件物品要装入背包, 物品重量和价值如下:

背包重量限制是 6，问如何选择物品，使得不超重的情况下装入背包的物品价值达到最大?

直觉的解法是贪心算法：单位重量价值大的优先，总重量不超过6.

按照 V   i   W   i   \frac{V~i~}{W~i~} W i V i ​ 从大到小排序，1,2,3,4

​ 7 3 \frac{7}{3} 37​ > 9 4 \frac{9}{4} 49​> 9 5 \frac{9}{5} 59​ > 2 2 \frac{2}{2} 22​

所以在进行一个算法的设计时，需要以下几个步骤：

每一个算法的设计，都需要遵循上述四个规则。

实例：5 万元，投资给 4 个项目，效益函数：

首先对这个问题进行数学建模：

目标函数：max ∑ i = 1 n f i ( x ) \sum_{i=1}^n f_i (x) ∑i=1n​fi​(x)

约束条件： ∑ i = 1 n x i = m \sum_{i=1}^n x_i =m ∑i=1n​xi​=m ，xi ∈ \in ∈ n;

上述就是一个数学的建模过程，最终的算法设计就是针对上述数学模型进行求解域优化。

在我们学习算法设计之前，先给出这道题的一个蛮力算法：

对所有满足下述条件的向量

x1+ x2 + … + xn = m ； xi 为非负整数, i = 1, 2 , …, n 。

计算相应的效益：

f1(x1) + f2(x2) + … + fn(xn)

从中确认效益最大的向量。

实例计算：

解： s=, 最大效益： 11+30+20 = 61

以上就是使用蛮力算法得出的额结果，结果肯定是对的，但是效率肯定不高。

方程 x1 + x2 + … + xn = m 的非负整数解 < x1, x2, …, xn > 的个数估计：

可行解表示成 0-1 序列： m 个1,n-1个 0

例如：n=4，m=7。可行解的一个为： ⇔ 序列 1 0 1 1 0 1 1 1 0 1

该解得序列的个数是输入规模的指数函数：

C(m+n-1,m)

= ( m + n − 1 ) ! m ! ( n − 1 ) ! \frac{(m+n-1)!}{m! (n-1)!} m!(n−1)!(m+n−1)!​

= Ω ((1+ε )m+n-1)

指数级是一个很大的数量级！！！有没有更好的算法？ 在后面的学习中，会学习到更好的算法。

问题求解的关键：