说明
本文我先写在我的CSDN上后再转到该博客系统的，有些链接会跳转我的CSDN上
动态规划基本思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题- 但是,分解得到的子问题往往
不是互相独立的。不同子问题的数目常常只有多项式量级。 - 在用分治法求解时，有些
子问题被重复计算了许多次。 - 如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，
从而得到多项式时间算法。 - 可以
用一个表来纪录所有已解决的子问题的答案，以后需要时，只需查询此表即可。
基本步骤
- 找出
最优解的性质，并刻画其结构特征。 - 递归地
定义最优值。 - 以自底向上的方式
计算最优值。 - 根据计算最优值时得到的信息，
构造最优解。
动态规划算法常用于求解具有某种最优性质的问题
可能有许多可行解, 希望找到具有最优值的那个解.
动态规划算法的基本要素
两个基本要素(重要性质): 最优子结构性质和子问题重叠性质.
最优子结构性质
例如矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
分析方法： 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
重叠子问题
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
矩阵连乘问题
问题描述
给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定，即连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算矩阵连乘积.
例如，给定三个连乘矩阵{A1，A2，A3}的维数分别是10*100，100*5和5*50，采用(（A1A2）A3)，乘法次数为10*100*5+10*5*50=7500次，而采用（A1（A2A3）)，乘法次数为100*5 *50+10*100*50 = 75000次乘法，显然，最好的次序是(（A1A2)A3)，乘法次数为7500次。
问题分析
矩阵链乘法问题描述：
给定由n个矩阵构成的序列｛A1，A2，…，An}，对乘积A1A2…An，找到最小化乘法次数的加括号方法。
1）寻找最优子结构
此问题最难的地方在于找到最优子结构。对乘积A1A2…An的任意加括号方法都会将序列在某个地方分成两部分，也就是最后一次乘法计算的地方，我们将这个位置记为k，也就是说首先计算 A1...Ak和Ak+1...An，然后再将这两部分的结果相乘。
最优子结构如下：假设A1A2…An的一个最优加括号把乘积在Ak和Ak+1间分开，则前缀子链A1…Ak的加括号方式必定为A1…Ak的一个最优加括号，后缀子链同理。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
一开始并不知道k的确切位置，需要遍历所有位置以保证找到合适的k来分割乘积。
2）构造递归解
设m[i,j]为矩阵链Ai…Aj的最优解的代价。A[i:j]表示 $A_i$$A_{i+1}$…$A_j$
- 设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数为
m[i,j]，则原问题的最优值为m[1,n] - 当
i = j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n - 当
i < j时，若A[i:j]的最优次序在Ak和Ak+1间断开，则
可以递归地定义m[i,j]为：
3）构建辅助表，解决重叠子问题
从第二步的递归式可以发现解的过程中会有很多重叠子问题，可以用一个nXn维的辅助表m[n][n] 和 s[n][n]，分别表示最优乘积代价及其分割位置k 。
辅助表s[n][n]可以由2种方法构造：
- 一种是
自底向上填表构建，该方法要求按照递增的方式逐步填写子问题的解，也就是先计算长度为2的所有矩阵链的解，然后计算长度3的矩阵链，直到长度n； - 另一种是
自顶向下填表的备忘录法，该方法将表的每个元素初始化为某特殊值(本问题中可以将最优乘积代价设置为一极大值)，以表示待计算，在递归的过程中逐个填入遇到的子问题的解。
对于一组矩阵:A1(30x35),A2(35x15),A3(15x5),A4(5x10),A5(10x20),A6(20x25) 个数N为6
那么p数组保存它们的行数和列数：p={30,35,15,5,10,20,25}共有N+1即7个元素
p[0],p[1]代表第一个矩阵的行数和列数，p[1],p[2]代表第二个矩阵的行数和列数……p[5],p[6]代表第六个矩阵的行数和列数
计算顺序为：
辅助表m: m[i][j]代表从矩阵Ai，Ai+1，Ai+2……直到矩阵Aj最小的相乘次数，比如m[2][5]代表A2A3A4A5最小的相乘次数，即最优的乘积代价。
我们看上图，从矩阵A2到A5有三种断链方式：A2{A3A4A5}、{A2A3}{A4A5}、{A2A3A4}A5，这三种断链方式会影响最终矩阵相乘的计算次数，我们分别算出来，然后选一个最小的，就是m[2][5]的值,同时保留断开的位置k在s数组中。
复杂度分析
算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n^3^)。因此算法的计算时间上界为O(n^3^)。算法所占用的空间显然为O(n^2^)
核心代码（自底向上的方式）
代码（自底向上的方式）
#include<iostream>
using namespace std;
const int N=7;
//p为矩阵链，p[0],p[1]代表第一个矩阵的行数和列数，p[1],p[2]代表第二个矩阵的行数和列数......length为p的长度
//所以如果有六个矩阵，length=7，m为存储最优结果的二维矩阵，s为存储选择最优结果路线的
//二维矩阵
void MatrixChainOrder(int *p,int m[N][N],int s[N][N],int length)
{
int n=length-1;
int l,i,j,k,q=0;
//m[i][i]只有一个矩阵，所以相乘次数为0，即m[i][i]=0;
for(i=1;i<length;i++)
{
m[i][i]=0;
}
//l表示矩阵链的长度
// l=2时，计算 m[i,i+1],i=1,2,...,n-1 (长度l=2的链的最小代价)
for(l=2;l<=n;l++)
{
for(i=1;i<=n-l+1;i++)
{
j=i+l-1; //以i为起始位置，j为长度为l的链的末位，
m[i][j]=0x7fffffff;
//k从i到j-1,以k为位置划分
for(k=i;k<=j-1;k++)
{
q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(q<m[i][j])
{
m[i][j]=q;
s[i][j]=k;
}
}
}
}
cout << m[1][N-1] << endl;
}
void PrintAnswer(int s[N][N],int i,int j)
{
if(i==j)
{
cout<<"A"<<i;
}
else
{
cout<<"(";
PrintAnswer(s,i,s[i][j]);
PrintAnswer(s,s[i][j]+1,j);
cout<<")";
}
}
int main()
{
int p[N]={30,35,15,5,10,20,25};
int m[N][N],s[N][N];
MatrixChainOrder(p,m,s,N);
PrintAnswer(s,1,N-1);
return 0;
}动态规划算法的基本要素
两个基本要素(重要性质): 最优子结构性质和子问题重叠性质.
最优子结构性质
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
分析方法： 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
重叠子问题
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
产生重叠子问题(递归算法)
int LookupChain(int i, int j){
if(i == j)
return 0;
m[i][j] = LookupChain(i,i) + LookupChain(i+1,j)+p[i-1]*p[i]*p[j];
s[i][j] = i;
for(int k=i+1; k<j;k++){
int t = LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];
if(t<m[i][j]){
m[i][j]=t;
s[i][j]=k;
}
}
return m[i][j];
}复杂度分析
递归算法计算时间：$\Omega$(2^n^)
动态规划算法计算时间：O(n^3^)
备忘录方法(自顶向下)
基本概念
核心算法
备忘记录项m[i][j]个数: O(n^2^)
每个记录项m[i][j]填入时间: O(n)
算法时间复杂度: O(n^3^)
算法
#include<iostream>
using namespace std;
#define N 7 //N为7，实际表示有6个矩阵
int p[N]={30,35,15,5,10,20,25};
int m[N][N],s[N][N];
int LookupChain(int i, int j){
if(m[i][j]>0)
return m[i][j];
if(i == j)
return 0;
m[i][j] = LookupChain(i,i) + LookupChain(i+1,j)+p[i-1]*p[i]*p[j];
s[i][j] = i;
for(int k=i+1; k<j;k++){
int t = LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];
if(t<m[i][j]){
m[i][j]=t;
s[i][j]=k;
}
}
return m[i][j];
}
int MemorizedMatrixChain(int n, int m[][N], int s[][N]){
for(int i=1;i<=n;i++){ //初始化默认都是0
for(int j=1;j<=n;j++)
m[i][j] = 0;
}
return LookupChain(1,n);
}
/*
*追踪函数：根据输入的i,j限定需要获取的矩阵链的始末位置，s存储断链点
*/
void Traceback(int i,int j, int s[][N]){
if(i==j) //回归条件
{
cout<<"A"<<i;
}
else //按照最佳断点一分为二，接着继续递归
{
cout<<"(";
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<")";
}
}
int main(){
MemorizedMatrixChain(N-1,m,s);//N-1因为只有六个矩阵
Traceback(1,6,s);
return 0;
}动态规划与备忘录方法对比总结
最长公共子序列
定义描述
若给定序列X={$x_1$,$x_2$,…,$x_m$}，则另一序列Z={$z_1$,$z_2$,…,$z_k$} 是X的子序列，是指存在一个严格递增下标序列{$i_1$,$i_2$,…,$i_k$}使得对于所有j=1,2,…,k有：$z_j$ = $x_{i_j}$ 。
例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
最长公共子序列：例如，序列X={A，B，C，B，D，A，B}，Y={B，D，C，A，B，A} ，{B，C，A}是X与Y的公共子序列，但不是最长公共子序列；{B，C，B，A}也是X与Y的公共子序列，但它是X与Y的最长公共子序列，因为X与Y没有长度大于4的公共子序列。
问题描述
给定2个序列X={$x_1$,$x_2$,…,$x_m$}和 Y={$y_1$,$y_2$,…,$y_n$}，找出X和Y的最长公共子序列。
分析最优解的结构
设序列X={$x_1$,$x_2$,…,$x_m$}和Y={$y_1$,$y_2$,…,$y_n$}的最长公共子序列为Z={$z_1$,$z_2$,…,$z_{k-1}$,$z_k$} ，则：
2个序列的最长公共子序列包含了它们前缀的最长公共子序列。- 最长公共子序列问题具有
最优子结构性质。
最优子结构性质：问题最优解，是否包含了子问题的最优解。
(1)当$x_m$=$y_n$
子问题变为Xm-1 ={$x_1$,$x_2$,…,$x_{m-1}$}和Yn-1 ={$y_1$,$y_2$,…,$y_{n-1}$}的最长公共子序列。
为了验证整个问题最优解Z是否包含子问题Xm-1和Yn-1最优解，就要验证$Z_{k-1}$={$z_1$,$z_2$,,…,$z_{k-1}$}是否是子问题Xm-1和Yn-1的最长公共子序列（即： 验证Zk-1是否是Xm-1和Yn-1长度为k-1的公共子序列）。
证明：若Xm-1和Yn-1有长度大于k-1的公共子序列W，则将xm加在W尾部产生X和Y的长度大于k的公共子序列，与题干中X和Y的最长公共子序列长度为k矛盾，故Zk-1是Xm-1和Yn-1的最长公共子序列
(2)当$x_m$≠$y_n$,且$z_k$≠$x_m$
子问题变为Xm-1 ={$x_1$,$x_2$,…,$x_{m-1}$}和Y ={$y_1$,$y_2$,…,$y_{n}$}的最长公共子序列。
为了验证整个问题最优解Z是否包含子问题Xm-1和Y最优解，就要验证$Z_{k}$={$z_1$,$z_2$,,…,$z_{k}$是否是子问题Xm-1和Y的最长公共子序列（即： 验证Z是否是Xm-1和Y长度为k的公共子序列）。
证明：若Xm-1和Y有长度大于k的公共子序列W，则W也是X和Y的长度大于k的公共子序列，这与Z是X和Y的最长公共子序列矛盾。
(3)当$x_m$≠$y_n$,且$z_k$≠$y_n$
子问题变为X ={$x_1$,$x_2$,…,$x_{m}$}和$Y_{n-1}$ ={$y_1$,$y_2$,…,$y_{n-1}$}的最长公共子序列。
就要验证$Z_{k}$={$z_1$,$z_2$,,…,$z_{k}$是否是子问题X和Yn-1的最长公共子序列
证明过程与（2）相似。
2个序列的最长公共子序列包含了它们前缀的最长公共子序列最长公共子序列问题具有最优子结构性质
子问题的递归结构
找序列X={$x_1$,$x_2$,…,$x_m$}和Y={$y_1$,$y_2$,…,$y_n$}的最长公共子序列为Z={$z_1$,$z_2$,…,$z_{k-1}$,$z_k$} ，递归执行如下：
(1)若$x_m$=$y_n$
(2)若$x_m$≠$y_n$
a）和 b）这两个公共子序列中较长者即为X和Y的最长公共子序列。
递归结构
由最优子结构性质建立子问题最优值的递归关系
用c[i][j]记录序列$X_i$和$Y_j$的最长公共子序列的长度，其中， $X_i$={$x_1$,$x_2$,…,$x_i$}； $Y_j$={$y_1$,$y_2$,…,$yj$}
当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故C[i][j]=0。
由最优子结构性质可建立递归关系如下：
子问题重叠性质
最长公共子序列问题具有子问题重叠性质；
例如，若xm≠yn，找X和Y的最长公共子序列，要计算Xm-1和Y以及X和Yn-1的最长公共子序列，而这两个都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。
计算最优值
- 子问题空间中，共有θ(mn)个不同的子问题.
- 用动态规划算法自底向上地计算最优值能提高算法的效率。
- 用
c[i][j]记录序列$X_i$和$Y_j$的最长公共子序列的长度，其中， $X_i$={$x_1$,$x_2$,…,$x_i$}； $Y_j$={$y_1$,$y_2$,…,$yj$} b[i][j]记录c[i][j]由哪一个子问题得到。
核心算法
- 用
c[i][j]记录序列$X_i$和$Y_j$的最长公共子序列的长度，其中， $X_i$={$x_1$,$x_2$,…,$x_i$}； $Y_j$={$y_1$,$y_2$,…,$yj$} b[i][j]记录c[i][j]由哪一个子问题得到。
三种情况下b[i][j]的取值
构造最长公共子序列
LCSLength只是计算出最优值，并未给出最优解，然而数组b可用于快速构造两个序列的最长公共子序列：
b[i][j]=1时表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列加上xi所得到；b[i][j]=2时表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同；b[i][j]=3时表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。
根据b的内容打印出最长公共子序列
核心算法
例子
给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略。求出其最长公共子序列，要求给出过程。
算法的改进
算法lcsLength和lcs中，可进一步将数组b省去。
- 事实上，数组元素c[i][j]的值
仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。 - 对于给定的数组元素c[i][j]，可仅借助于c本身确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。
给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公共子序列，要求给出过程。
参照算法分析：
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++) {
if (x[i]==y[j]) {
c[i][j]=c[i-1][j-1]+1; b[i][j]=1;}
else if (c[i-1][j]>=c[i][j-1]) {
c[i][j]=c[i-1][j]; b[i][j]=2;}
else {
c[i][j]=c[i][j-1]; b[i][j]=3;}
}
}- [4,4]开始，此时为2。比较[4,3]和[3,4]，与[4,4]的值相同，说明没有新增公共字符。又[3,4]=[4,3]，从算法中可以看出此时下一步应该是[i-1,j],即[3,4]
- [3,4]开始,此时为2。比较[3,3]和[2,4]，与[3,4]的值相同，说明没有新增公共字符。又[3,3]=[2,4]，从算法中可以看出此时下一步应该是[i-1,j],即[2,4]
- [2,4]开始,此时为2。比较[2,3]和[1,4]，有一个与[2,4]相同，说明没有新增公共字符。又[2,3]>[1,4]，从算法中可以看出此时下一步应该是[i,j-1],即[2,3]
- [2,3]开始,此时为2。比较[2,2]和[1,3]，都与[2,3]不同，说明此时新增了公共字符。从算法中可以看出此时下一步应该是[i-1,j-1],即[1,2]
- [1,2]开始,此时为2。比较[1,1]和[0,2]，都与[1,2]不同，说明此时新增了公共字符。从算法中可以看出此时下一步应该是[i-1,j-1],即[0,1]
- 此时x=0,算法结束.
最长公共子序列：｛ＢＣ｝
扩展
如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。
- 事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。
- 用2行的数组空间就可以计算出最长公共子序列的长度。
- 进一步的分析还可将空间需求减至O(min(m,n))。
完整算法
#include<bits/stdc++.h>
using namespace std;
char x[1020], y[1020], z[1020];
int c[1020][1020], b[1020][1020];
int m, n;
void LCSLength()
{
memset(c, 0, sizeof(c));
memset(b, 0, sizeof(b));
for(int i = 1; i <= m; ++i)
{
for(int j = 1; j <= n; ++j)
{
if(x[i] == y[j])
{
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;
}
else if(c[i - 1][j] >= c[i][j - 1])
{
c[i][j] = c[i - 1][j];
b[i][j] = 2;
}
else
{
c[i][j] = c[i][j - 1];
b[i][j] = 3;
}
}
}
}
void LCS(int i, int j)
{
if(i == 0 || j == 0)
return ;
if(b[i][j] == 1)
{
LCS(i - 1, j - 1);
cout << x[i];
}
else if(b[i][j] == 2)
{
LCS(i - 1, j);
}
else
{
LCS(i, j - 1);
}
}
void Input()
{
cout<<"请输入第一个序列(字母中间不要空格)：";
gets(x);
cout<<"请输入第二个序列(字母中间不要空格)：";
gets(y);
m = strlen(x);
n = strlen(y);
strcpy(x + 1, x);//为了方便，0号位置不放元素
strcpy(y + 1, y);
}
int main()
{
Input();
LCSLength();
LCS(m, n);
}
测试用例
输入
请输入第一个序列(字母中间不要空格)：BCDA
请输入第二个序列(字母中间不要空格)：ABCB
输出
BC
流水线作业调度问题
问题描述
- n个作业{1，2，…，n},要在由机器M1和M2组成的流水线上完成加工。
- 每个作业加工的顺序都是先在M1上加工，然后在M2上加工。
- M1和M2加工作业i所需的时间分别为ai和bi。
要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。
问题分析
直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。
在一般情况下，机器M2上会有
机器空闲和作业积压两种情况设全部作业的集合为N={1，2，…，n}。S $\subseteq$ N是N的作业子集。
通常，机器M1开始加工S中作业时，机器M2还在加工其它作业，
要等时间t后才可利用。将这种情况下完成S中作业所需的
最短时间记为T(S, t)。流水作业调度问题的最优值为T(N, 0)。
最优子结构性质
最优子结构性质：问题最优解，是否包含了子问题的最优解。
调度问题最优子结构性质：设π是所给n个流水作业（N={1，2，…，n}）的一个最优调度，最优调度序列是π(1) ，π(2)， π(3)，…，π(n) ，π是否是调度π(2)， π(3)，…， π(n)的一个最优调度？若是，最优子结构性质成立。证明如下：
- 把π调度n个作业所需的加工时间分成两部分： $a_{π(1)}$(1) 和T’。 其中，T’是机器M1和M2加工作业{π(2)，…，π(n)}所需的时间。因此，π调度n个流水作业需要的总时间为$a_{π(1)}$(1) 和T’
- 令作业子集S=N - {π(1)} ，即：S={π(2)， π(3)，…，π(n)}。
- 假设π
不是实现加工作业子集S所需时间最短（最优）的调度，设π’是M1和M2加工作业子集S所需时间最短的一个最优调度, 则按π’加工作业子集S的最短时间为 T(S,$b_{π(1)}$ )
- 因此π(1)， π’(2)，…， π’(n)是完成N ={1，2，…，n}作业 的一个调度，且该调度完成n个作业所需的时间 aπ(1)+T(S,bπ(1))
- 由于 π’是加工π(2)，…，π(n)的最优调度，则T(S,bπ(1))是最短 时间，则T(S,$b_{π(1)}$)≤ T’，因此， $a_{π(1)}$+T(S,$b_{π(1)}$) ≤ $a_{π(1)}$+T’.
- 由此，按照π(1)， π’(2)，…， π’(n)调度顺序完成n个作业所需的时间，
小于按照π(1)， π(2) ，…， π(n) 调度完成n个作业所需时间aπ(1)+T’，这与π是N的最优调度矛盾， - 因此，
π’是完成π(2)，…，π(n)的最优调度假设不成立，因此，π是完成π(2)，…，π(n)作业的最优调度。即：作业调度问题最优子结构性质成立。
递归计算最优值
由流水作业调度问题的最优子结构性质可知:
一般情况下：
流水作业调度的Johnson法则
对于流水作业调度问题，必存在最优调度π ，使得作业π(i)和π(i+1)满足Johnson不等式, 此时称π为满足Johnson法则的调度。
min{$b_{π(i)}$,$a_{π(i+1)}$}≥min{$b_{π(i+1)}$,$a_{π(i)}$} , 1≤i ≤n-1
所有满足Johnson法则的调度均为最优调度,且具有相同的加工时间。从而，将流水作业调度问题转化为求满足Johnson法则的调度问题。
分析问题
- 当min{ $a_1$, $a_2$,┅, $a_n$ , $b_1$, $b_2$,┅, $b_n$ }=$a_k$时，则对任何i≠k，都有min{$b_k$, $a_i$} ≥ min{$b_i$,$a_k$}成立，故此时应将作业k安排在最前面，作为最优调度的第一个执行的作业；
- 当min{ $a_1$, $a_2$,┅, $a_n$ , $b_1$, $b_2$,┅, $b_n$ }=$b_k$时，则对任何i≠k，也都有min{$b_i$, $a_k$} ≥ min{$b_k$,$a_i$}成立，故此时应将作业k安排在最后面，作为最优调度的最后一个执行的作业。
- n个作业中首先开工（或最后开工）的作业确定之后，对剩下的n-1个作业采用相同方法可再确定其中的一个作业,应作为n-1个作业中最先或最后执行的作业；反复使用这个方法直到最后只剩一个作业为止，最优调度就确定了 。
计算作业加工顺序的步骤
- 将{ $a_1$, $a_2$,┅, $a_n$ , $b_1$, $b_2$,┅, $b_n$ }排成非递减序列；
- 依次从序列中抽出最小元素m，如果m ＝ $a_j$且作业j还没有排入调度表，则把作业 j 安排在调度表可达的最左边一项空位上（设n个作业的调度表有n项，开始全部为空）。
- 如果m = bj且作业j还没有排入调度表，则把作业j安排在调度表可达的最右边一项空位上。
- 如果作业j已排在调度表中，则取序列的下一个最小元素m，继续按上述方法调度，直到元素取完为止。
- 最后得到的调度表中的作业的顺序就是各作业的加工顺序。
例子
设 n ＝ 4，
（$a_1$, $a_2$，$a_3$, $a_4$）＝（3，4，8，10）
（$b_1$, $b_2$，$b_3$, $b_4$）＝（6，2，9，15）
解:
经排序后为
（$b_2$，$a_1$，$a_2$，$b_1$，$a_3$，$b_3$，$a_4$，$b_4$）＝（2，3，4，6，8，9，10，15）
设σ1，σ2，σ3，σ4是最优调度。
因为最小数是b2，故置σ4= 2。下一个次小的数是a1，置σ1= 1。接下去是a2，作业2已经被调度。再其次是b1作业1也已经被调度。下一个是a3，置σ2= 3，依次置σ3= 4。
流水作业调度问题的Johnson算法
- 令 $N_1$ = { i | $a_i$ < $b_i$}，$N_2$ = { i | $a_i$ ＞ $b_i$}
- 将$N_1$中作业依ai的非减序排序；将$N_2$中作业依$b_i$的非增序排序；
- $N_1$中作业接$N_2$中作业构成满足Johnson法则的最优调度π。
红线左侧满足 $a_{π(i)}$ ≤ $b_{π(i)}$ 和 $a_{π(i)}$ ≤ $a_{π(i+1)}$ ，符合johnson不等式: min{$b_{π(i)}$,$a_{π(i+1)}$}≥min{$b_{π(i+1)}$,$a_{π(i)}$} ，N1中作业调度顺序最优；红线右侧满足$b_{π(i+1)}$ ≤ $a_{π(i+1)}$ 和 $b_{π(i+1)}$ ≤ $b_{π(i)}$，符合johnson不等式: min{$b_{π(i)}$,$a_{π(i+1)}$}≥min{$b_{π(i+1)}$,$a_{π(i)}$} ，N2中作业调度顺序最优；中间过渡部分横向比较，左侧 $a_{π(i)}$ ≤ $b_{π(i)}$,右侧$b_{π(i+1)}$ ≤ $a_{π(i+1)}$，符合johnson不等式: min{$b_{π(i)}$,$a_{π(i+1)}$}≥min{$b_{π(i+1)}$,$a_{π(i)}$} ，其作业调度顺序最优；
若$a_{π(i)}$ ≤ $b_{π(i+1)}$ , 则$a_{π(i)}$ ≤ $b_{π(i+1)}$ ≤ $a_{π(i+1)}$ ，又$a_{π(i)}$ ≤ $b_{π(i)}$ ， 成立。
若$a_{π(i)}$ ≥ $b_{π(i+1)}$ , 则$b_{π(i+1)}$ ≤ $a_{π(i)}$ ≤ $b_{π(i)}$ ，又$b_{π(i+1)}$ ≤ $a_{π(i+1)}$ ， 成立。
算法复杂度分析
算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为O(nlogn)。所需的空间为O(n)。
作业调度的最短时间计算
两个作业调度
三个作业调度
核心代码
:point_right: 参照上面的计算步骤进行分析,有些许不同。
class Jobtype
{
public:
int key, index; // key保存ai和bi二者较小的值； index保存作业号i
bool job; ///将满足条件aib[i]? b[i]:a[i]; //分别取b[i]和a[i]值较小的作为关键字
d[i].job = a[i]<=b[i]; //将满足a[i] 完整代码
把在M1上工作的时间看做是先行工序时间，M2上的工作时间看成后行工序时间。
如果某个作业的M1时间>M2时间，它就是后行工序；反之，就是先行工序时间。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define n 6 //6个作业
using namespace std;
int M1[n]={2,7,6,4,6,8};
int M2[n]={5,3,2,7,9,2};
int c[n]={0}; //存放次序，注意：c[m]=k,意思是第m+1个执行的作业是k
class Node{
public:
int time; //时间
int index; //来自第几个作业
int position; //是先行工序还是后行工序
};
bool cmp(Node a,Node b){
return a.time<b.time;
}
int main(){
Node* node=new Node[n]; //设置n个Node型结构体，盛放n个作业
int first=0,end=n-1;
int time1=0,time2=0; //分别记录在机器1 和 机器2 上的时间
for(int i=0;i<n;i++){ // 数组打底工作
node[i].index=i; //记录一下当前这个node节点放的是哪个作业
if(M1[i]>M2[i]){
node[i].time=M2[i];
node[i].position=2; //后行工序
}
else{
node[i].time=M1[i];
node[i].position=1; //先行工序
}
}
//虽然把n个作业都赋值到了Node型结构体中，
//但是大小交错，没有顺序，
//所以需要排序
sort(node,node+n,cmp);
//排完序后，把原本顺序都乱了，先行、后行工作虽然交错，但都已经从小到大排列了
//需要用c数组记录执行顺序，先行工序从前往后放，后行工序从后往前放
for(int i=0;i<n;i++){
if(node[i].position==1){ //先序
c[first]=node[i].index;
first++;
}
if(node[i].position==2){ //后序
c[end]=node[i].index;
end --;
}
}
time1=M1[c[0]];
time2=time1+M2[c[0]];
for(int i=1;i<n;i++){
time1+=M1[c[i]];
time2=time1>time2?time1+M2[c[i]]:time2+M2[c[i]];
}
printf("次序：\n");
for(int i=0;i<n;i++){
printf("%3d",c[i]+1);
}
putchar('\n');
printf("%d\n",time2);
return 0;
}
0-1背包问题
问题描述
给定n个物品和一个背包。物品i的重量为wi，价值为vi，背包容量为c。
如何选择装入背包中的物品，使得装入背包的物品的价值最大？
每种物品i只有两种选择，装入或者不装入，既不能装入多次，也不能只装入一部分。
此问题称为0-1背包问题。
问题形式化描述
问题的形式描述是：给定c＞0，$w_i$＞0，$v_i$＞0，1≤i≤n，求n元0-1向量($x_1$, $x_2$, …, $x_n$)，使得
(物品i的重量为wi，价值为vi，背包容量为c。)
最优子结构性质
设($y_1$,$y_2$, …, $y_n$)是所给0-1背包问题的一个最优解，则($y_2$, …, $y_n$)是下面子问题的最优解：
反之，假如($y_2$, …, $y_n$)不是上面子问题最优解，则设($z_2$, …, $z_n$)是该子问题最优解，则($y_1$,$y_2$, …, $y_n$)是原问题的最优解，而($y_1$,$y_2$, …, $y_n$)不是原最优解。矛盾。
设($z_2$, …, $z_n$)是该子问题最优解,($y_2$, …, $y_n$)不是上面子问题最优解
因此， ($y_1$, $z_2$, …, $z_n$)所给0-1背包问题的一个最优解，而($y_1$, …, $y_n$)不是原0-1背包问题的一个最优解，矛盾，因此( $z_2$, …, $z_n$)不是上述子问题的一个最优解， ($y_2$, …, $y_n$) 是子问题最优解，最优子结构性质成立。
0-1背包问题的递归式
从第n个物品开始依次向前装，装的顺序为：
（n, n-1, n-2, …, i+1, i, i-1, …, 1）
m(i, j)：当前背包容量为j，选择物品为n, n-1, n-2, …, i+1, i 装入背包产 生的价值
寻找递推关系式，面对当前商品i有两种可能性：
- 包的容量比商品i体积小，装不下，此时的价值与前n-i个的价值是一样的，即
m(i,j)=m(i+1,j)； - 还有足够的容量可以装该商品i，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即
m(i,j)=max｛ m(i+1, j)，m(i+1,j-wi)+vi ｝其中m(i+1,j)表示不装i的价值，m(i+1,j-wi)+vi 表示装了第i个商品，背包容量减少w(i), 但价值增加了v(i)；
由此可以得出递推关系式：
算法描述
- 用二维数组m[i][j], 0≤j≤c, 来存储m(i, j)的值。
- 求解0-1背包问题就是在二维数组m中填入相应的值。
- m[1][c]中的值就是该背包问题的解
在二维数组m中最先填入的应该是哪些呢？
二维数组m中最先填入物品n的最优解m(n, j)：
- 若0≤j＜$w_n$，m[n][j]=0；
- 若j≥$w_n$，m[n][j]=$v_n$。
例子
根据递推关系式得到表中数据：
构造最优解(x1,x2,…,xn)算法：
如果m[1][c]=m[2][c], 则x1=0, 否则x1=1;
如果x1=0, 则由m[2][c]构造解;
如果x1=1, 则由m[2][c-w1]构造解;
依次类推，可构造出相应的最优解:（x1,x2,…,xn）
上述例子最优解： (x1,x2, x3, x4)=(1,0,1,1)
核心算法
void Knapsack(int v[],int w[],int c,int n,int m[][10])
{
int jMax = min(w[n]-1,c);//背包剩余容量上限 范围[0~w[n]-1]
for(int j=0; j<=jMax;j++)
{
m[n][j]=0;
}
for(int j=w[n]; j<=c; j++)//限制范围[w[n]~c]
{
m[n][j] = v[n];
}
for(int i=n-1; i>1; i--)
{
jMax = min(w[i]-1,c);
for(int j=0; j<=jMax; j++)//背包不同剩余容量j<=jMax<c
{
m[i][j] = m[i+1][j];//没产生任何效益
}
for(int j=w[i]; j<=c; j++) //背包不同剩余容量j-wi >c
{
m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//效益值增长vi
}
}
m[1][c] = m[2][c];
if(c>=w[1])
{
m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);
}
}
最优求解算法Traceback
//x[]数组存储对应物品0-1向量,0不装入背包，1表示装入背包
void Traceback(int m[][10],int w[],int c,int n,int x[])
{
for(int i=1;i<n; i++)
{
if(m[i][c] == m[i+1][c])
{
x[i]=0;
}
else
{
x[i]=1;
c-=w[i];
}
}
x[n]=(m[n][c])?1:0;
}
0-1背包问题的阶跃性
但是，但是！！该算法有两个明显的缺点：
1. 基于上述代码，因为数组索引的需要，要求所给物品重量为整数。
2. 当背包容量C很大时，算法所需计算时间较多。当C>2^n^时，需要Ω(n*2^n^)计算时间。
所以，所以！！改进算法如下：
对于函数m(i,j)的值，当i确定，j为自变量时，是单调不减的跳跃式增长，如图所示。而这些跳跃点取决于在（物品i，物品i+1，……物品n）中选择放入哪些物品使得在放入重量小于容量 j (0<=j<=C)的情况下m取得最大值。对于每一个确定的i值，都有一个对应的跳跃点集Pi={ ( j, m(i,j) )，……}。j始终小于等于C
(1)开始求解时，先求Pi，初始时Pn+1={(0，0)}，i=n+1，由此按下列步骤计算Pi-1，Pi-2……P1，即Pn，Pn-1，……P1
(2)求Qi，利用Pi求出m（i，j-w[i-1]）+v[i-1]，即Pi当放入物品i-1后的变化后的跳跃点集Qi={ ( j+w[i-1], m(i,j)+v[i-1] )，……}，在函数图像上表现为所有跳跃点横轴坐标右移w[i-1]，纵轴坐标上移v[i-1]。
(3)求Pi-1，即求Pi∪Qi然后再去掉受控跳跃点后的点集。此处有个受控跳跃点的概念：若点(a,b)，(c,d)∈Pi∪Qi，且a<=c，b>d，则(c,d)受控于(a,b)，所以(c,d)∉Pi-1。去掉受控跳跃点，是为了求得在物品i-1放入后m较大的点，即 使m取最优值的跳跃点。
由此计算得出Pn，Pn-1，……，P1。求得P1的最后那个跳跃点即为所求的最优值m(1,C)。
例子
n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。跳跃点的计算过程如下：
初始时p[6]={(0,0)}
因此，q[6]=p[6]⊕(w[5],v[5])={(4,6)}
p[5]={(0,0),(4,6)}
q[5]=p[5]⊕(w[4],v[4])={(5,4),(9,10)}
p[4]={(0,0),(4,6),(9,10)} p[5]与q[5]的并集p[5]∪q[5]={(0,0),(4,6),(5,4),(9,10)}中跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到p[4]
q[4]=p[4]⊕(6，5)={(6，5)，(10，11)}
p[3]={(0，0)，(4，6)，(9，10)，(10，11)}
q[3]=p[3]⊕(2，3)={(2，3)，(6，9)}
p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)}
q[2]=p[2]⊕(2，6)={(2，6)，(4，9)，(6，12)，(8，15)}
p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}
p[1]的最后的那个跳跃点(8,15)即为所求的最优值，m(1,C)=15
完整代码
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1024;
int n; //物品个数
int c; //包的容量
int value[MAX]; //物品的价值
int weight[MAX]; //物品的重量
int x[MAX]; //n元0-1向量
int m[MAX][MAX]; //解的容器
void Input()
{
scanf("%d %d", &n, &c);
for(int i = 1; i <= n; ++i)
scanf("%d %d", &value[i], &weight[i]);
}
//创建最优解
void Knapsack()
{
memset(m, 0, sizeof(m));
for(int i = 1; i <= n; ++i) //逐行填表，i表示当前可选物品数，j表示当前背包的容量, 也就是从低到顶。
{
for(int j = 1; j <= c; ++j)
{
if(j < weight[i])
m[i][j] = m[i - 1][j];
else
{
m[i][j] = max(m[i - 1][j], m[i - 1][j - weight[i]] + value[i]);
}
}
}
}
//获取最优解(即设法将求得的最优解输出出来)
void Traceback()
{
int cc = c;
for(int i = n; i > 1; --i)
{
if(m[i][cc] == m[i - 1][cc])
x[i] = 0;
else
{
x[i] = 1;
cc -= weight[i];
}
}
if(cc >= weight[1])
x[1] = 1;
}
void Output()
{
cout << "最优解为 : " << m[n][c] << endl;
cout << "选择的物品的序号为 :" << endl;
for(int i = 1; i <= n; ++i)
if(x[i] == 1)
cout << i << " ";
cout << endl;
}
int main()
{
Input();
Knapsack();
Traceback();
Output();
}测试样例
输入
请先输入物品个数和包的容量(n c)：4 8
请输入每件物品的重量和价值(v w)：
2 1
1 4
4 2
3 3
输出
最优解为 : 9
选择的物品的序号为 :
1 3 4