划水划的太久了，需要做一些复健运动。这篇文章拿来更新最近重新学习DP的笔记。
动态规划
动态规划是用于解决最优化问题的一种方法，而不是某一个算法。对于不同问题，最优解的条件不同，因而有着不同的DP设计方法。因而在实际中必须对具体问题分析处理。
基本模型
动态规划适用于多阶段决策过程的最优化问题。多阶段决策过程，是指问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。
在每个阶段所采取的决策，一般来说是与阶段有关的。决策依赖于当前的状态，同时会引起状态的转移。一个决策序列就是在变化的状态中产生出来的，称这种解决多阶段决策最优化的过程为动态规划程序设计方法。
例1 最短路径问题
下图给出了一个地图，地图中的每个顶点代表一个城市，两个城市间的一条连线代表道路，连线上的数值代表道路的长度。现在想从城市A到达城市E，怎样走路程最短？最短路程的长度是多少？
把A到E的全过程分成四个阶段，用K表示阶段变量，第1阶段有一个初始状态A，有两条可供选择的支路A-B1、A-B2；第2阶段有两个初始状态B1、B2，B1有三条可供选择的支路，B2有两条可供选择的支路……。用DK（XI，X+1J）表示在第K阶段由初始状态XI到下阶段的初始状态X+1J的路径距离，FK（XI）表示从第K阶段的XI到终点E的最短距离，利用倒推的方法，求解A到E的最短距离。
对应的C++程序如下：
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
long d[5][5][5],f[10][10];
memset(d,42,sizeof(d)); //有些路径是不通的,赋值为较大值，用于判断
d[1][1][1]=5;d[1][1][2]=3;d[2][1][1]=1; //以下给可通路径赋正常值
d[2][1][2]=6;d[2][1][3]=3;d[2][2][2]=8
d[2][2][4]=4;d[3][1][1]=5;d[3][1][2]=6;
d[3][2][1]=5;d[3][3][3]=8;d[3][4][3]=3;
d[4][1][1]=3;d[4][2][1]=4;d[4][3][1]=3;
for (int i=0;i<=9;++i)
for (int j=0;j<=9;++j) f[i][j]=10000000;
f[5][1]=0;
for (int i=4;i>=1;--i)
for (int j=1;j<=4;++j)
for (int k=1;k<=4;++k)
if (f[i][j]>d[i][j][k]+f[i+1][k]) //即使走非法路径，也不影响答案
f[i][j]=d[i][j][k]+f[i+1][k];
cout<<f[1][1]<<endl;
}
基本概念
-
阶段和阶段变量：
用动态规划求解一个问题时，需要将问题的全过程恰当地分成若干个相互联系的阶段，以便按一定的次序去求解。描述阶段的变量称为阶段变量，通常用K表示，阶段的划分一般是根据时间和空间的自然特征来划分，同时阶段的划分要便于把问题转化成多阶段决策过程，如例题1中，可将其划分成4个阶段，即K = 1，2，3，4。
-
状态和状态变量：
某一阶段的出发位置称为状态，通常一个阶段包含若干状态。一般地，状态可由变量来描述，用来描述状态的变量称为状态变量。如例题1中，C3是一个状态变量。
-
决策、决策变量和决策允许集合：
在对问题的处理中作出的每种选择性的行动就是决策。即从该阶段的每一个状态出发，通过一次选择性的行动转移至下一阶段的相应状态。一个实际问题可能要有多次决策和多个决策点，在每一个阶段的每一个状态中都需要有一次决策，决策也可以用变量来描述，称这种变量为决策变量。在实际问题中，决策变量的取值往往限制在某一个范围之内，此范围称为允许决策集合。如例题1中，F3（C3）就是一个决策变量。
-
策略和最优策略：
所有阶段依次排列构成问题的全过程。全过程中各阶段决策变量所组成的有序总体称为策略。在实际问题中，从决策允许集合中找出最优效果的策略成为最优策略。
-
状态转移方程
前一阶段的终点就是后一阶段的起点，对前一阶段的状态作出某种决策，产生后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。
最优化原理与无后效性
一般来说，能够采用动态规划方法求解的问题，必须满足最优化原理和无后效性原则
动态规划的最优化原理
动态规划整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。这可以理解为子问题的局部最优将导致整个问题的全局最优。
动态规划的无后效性原则
无后效性原则指某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也即「未来与过去无关」。当前的状态是此前历史的一个完整的总结，此前的历史只能通过当前的状态去影响过程未来的演变。
由此可见，对于不能划分阶段的问题，不能运用动态规划来解；对于能划分阶段，但不符合最优化原理的，也不能用动态规划来解；既能划分阶段，又符合最优化原理的，但不具备无后效性原则，还是不能用动态规划来解；误用动态规划程序设计方法求解会导致错误的结果。
动态规划设计方法的一般模式
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态；或倒过来，从结束状态开始，通过对中间阶段决策的选择，达到初始状态。这些决策形成一个决策序列，同时确定了完成整个过程的一条活动路线，通常是求最优活动路线。
动态规划的设计都有着一定的模式，一般要经历以下几个步骤：
-
划分阶段
按照问题的时间或空间特征，把问题划分为若干个阶段。在划分阶段时，注意划分后的阶段一定是有序的或者是可排序的，否则问题就无法求解。
-
确定状态和状态变量
将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
-
确定决策并写出状态转移方程
因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可以写出。但事实上常常是反过来做，根据相邻两段的各个状态之间的关系来确定决策。
-
寻找边界条件
给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
动态规划与递推
由于动态规划的“名气”如此之大，以至于很多人甚至一些资料书上都往往把一种与动态规划十分相似的算法，当作是动态规划。这种算法就是递推。实际上，这两种算法还是很容易区分的。
按解题的目标来分，信息学试题主要分四类：判定性问题、构造性问题、计数问题和最优化问题。我们在竞赛中碰到的大多是最优化问题，而动态规划正是解决最优化问题的有力武器，因此动态规划在竞赛中的地位日益提高。而递推法在处理判定性问题和计数问题方面也是一把利器。下面分别就两个例子，谈一下递推法和动态规划在这两个方面的联系。
例9 最长公共子序列
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列(X=<x_1,x_2,cdots ,x_m>) ，则另一序列(Z=<z_1, z_2, cdots , z_k>) 是(X)的子序列是指存在一个严格递增的下标序列(<i_1,i_2,cdots,i_k>),使得对于所有(j=1,2,cdots,k) 有 (X_{ij}=Zj)。
给定两个序列(X＝<x_1, x_2, cdots , x_m>)和(Y=<y_1,y_2, cdots ,y_n>)．要求找出(X)和(Y)的一个最长公共子序列。
【输入】
共有两行。每行为一个由大写字母构成的长度不超过1000的字符串，表示序列X和Y。
【输出】
第一行为一个非负整数。表示所求得的最长公共子序列的长度。若不存在公共子序列．则输出文件仅有一行输出一个整数0。
【输入样例】
ABCBDAB BDCABA【输出样例】
4
思路分析：
这一题最容易想到的是暴力搜索。对于X的每一个子序列，都去判断它是否也为Y的一个子序列，在过程中选出最长的公共子序列。算法用时(O (2^m imes 2^n)).
事实上最长公共子序列问题具有最优子结构性质，因而可以用动态规划算法求解。
我们记(X_i) 为(X)序列的前(i)个字符((1 leq i leq m)), (Y_j)为(Y)序列的前(j)个字符((1 leq j leq n)). 假定(Z = <z_1, z_2, cdots, z_k> in ext{LCS}(X,Y)). 有：
-
若(x_m = y_n)，即两个给定序列最后一个字符相同，则不难用反证法证明：该字符必是X与Y的任一最长公共子序列Z（设长度为k）的最后一个字符，即有(z_k = x_m = y_n) 且显然有(Z_{k-1}in ext{LCS}(X_{m-1} , Y_{n-1}))即Z的前缀(Z_{k-1})是(X_{m-1})与(Y_{n-1})的最长公共子序列。此时，问题化归成求(X_{m-1})与(Y_{n-1})的最长公共子序列（( ext{LCS}(X,Y))的长度等于( ext{LCS}(X_{m-1} , Y_{n-1}))的长度加1）。
-
若(x_m eq y_n)，则要么(Zin ext{LCS}(X_{m-1} , Y))，要么(Zin ext{LCS}(X , Y_{n-1}))。此时(z_k eq x_m) 与 (z_k eq y_n) 至少有一个成立。若(z_k eq x_m)则(Zin ext{LCS}(X_{m-1} , Y))，若(z_k eq y_n) 则(Zin ext{LCS}(X , Y_{n-1}))。**故问题变为求$ ext{LCS}(X_{m-1} , Y)(与) ext{LCS}(X , Y_{n-1})(。** LCS(X , Y)的长度为：)max{ ext{LCS}(X_{m-1}, Y) ext{的长度}, ext{LCS}(X , Y_{n-1}) ext{的长度}}$。
由于上述当xm≠yn的情况中，求LCS(Xm-1 , Y)的长度与LCS(X , Yn-1)的长度，这两个问题不是相互独立的：两者都需要求LCS(Xm-1，Yn-1)的长度。另外两个序列的LCS中包含了两个序列的前缀的LCS，故问题具有最优子结构性质考虑用动态规划法。
也就是说，解决这个LCS问题，你要求三个长度：
- ( ext{LCS}(X_{m-1} , Y_{n-1}) ext{的长度}+ 1)
- ( ext{LCS}(X_{m-1}, Y) ext{的长度}, ext{LCS}(X , Y_{n-1}) ext{的长度})
- (max{ ext{LCS}(X_{m-1}, Y) ext{的长度}, ext{LCS}(X , Y_{n-1}) ext{的长度}})。
代码如下（YBT1265）：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 1010
char str1[ MAXN ], str2[ MAXN ];
int f[ MAXN ][ MAXN ]; // f[i][j] 存储字符串1从起始到i位置 字符串1从起始到j位置的LCS最大长度
int main()
{
scanf("%s", str1+1);
scanf("%s", str2+1);
memset( f, 0, sizeof( f ));
int len1 = strlen(str1+1), len2 = strlen(str2+1);
for( int i = 1; i <= len1; i++ ){
for( int j = 1; j <= len2; j++ ){
if( str1[i] == str2[j] ){ // 情况1 末尾相同
f[i][j] = f[i-1][j-1] + 1;
}
else{ // 情况2 末尾不同
f[i][j] = max(f[i-1][j], f[i][j-1]);
}
}
}
printf("%d
", f[len1][len2]);
return 0;
}
背包问题
01背包
有N件物品和一个容量为V的背包。第i件物品的费用（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品(部分或全部)恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}。
子问题「将前i件物品放入容量为v的背包中」所要决策的是对于第i件物品，放和不放入背包这两种选择。因而只涉及到已经讨论完的i-1种物品，即放等同于「将前i-1件物品放入剩下的容量为v-w[i]的背包中」，此时背包最大价值为f[i-1][v-w[i]]再加上通过放入第i件物品获得的价值c[i]；不放等同于「将前i-1件物品放入容量为v的背包中」，背包价值依旧为f[i-1][v]
基本上所有有关背包问题的方程都由这个方程衍生而来。
注意
f[i][v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N][V]，而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[i-1][v]，这样就可以保证f[N][V]就是最后的答案。但是若将所有f[i][j]的初始值都赋为0，你会发现f[n][v]也会是最后的答案。为什么呢？因为这样你默认了最开始f[i][j]是有意义的，只是价值为0，就看作是无物品放的背包价值都为0，所以对最终价值无影响，这样初始化后的状态表示就可以把“恰”字去掉。
优化空间复杂度
以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。
在上文的基本思路中，我们的主循环i = 1 -> n ，从而计算出二维数组f[i][j = 0...v] 的所有值，那么可以用一维数组f[0...v]实现吗？在二维数组的实现中，f[i][v] 是由 f[i-1][v] 和f[i-1][v-w[i]]两个子问题得来，那么如果要用一维数组实现，我们必须要保证在求f[i][v]时f[i-1][v]和f[i-1][v-w[i]]的值没有被覆盖。因此，我们要在每次主循环中令v = v->0的逆序去求f[v]，这样才能保证上述条件。
此时的转移方程为
for i = 1 ... N
for v = V ... 0
f[v] = max{f[v], f[v-w[i] + c[i]}
例1 01背包
【问题描述】
一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件，求旅行者能获得最大总价值。
【输入格式】
第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；
第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。
【输出格式】
仅一行，一个数，表示最大总价值。
【样例输入】package.in
10 4 2 1 3 3 4 5 7 9【样例输出】package.out
12
一维代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[ 220 ] = {0};
int main()
{
int M, N;
scanf("%d%d", &M, &N);
int w, c;
for( int i = 1; i <= N; i++ ){
scanf("%d%d", &w, &c);
for( int j = M; j >= 0; j-- ){
if( j-w >= 0 )
f[j] = max( f[j], f[j-w] + c );
}
}
printf("%d
", f[M]);
return 0;
}
总结
01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。
完全背包
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这个问题类似与01背包，不同的是每件物品的总量无限，即可以取0, 1, 2, ... 件。按照01背包的思路，便有f[i][v] = max{f[i-1][ v - k*w[i] ] + k*c[i] | 0 <= k*w[i] <= v}。
而对于压缩空间的一维数组实现，算法伪代码则为
for i = 1 ... N
for v = 0 ... V
f[v] = max{f[v], f[v-w[i] + c[i]}
这里变动只有v的循环顺序变为从0到V。为什么这样可行呢？
在01背包中，v从V到0循环是为了保证f[i][v]是由f[i-1][v-w[i]所推出，即保证了每件物品只选择一次。而完全背包中每种物品可选择无限件，因而可以从已经选过这种物品的背包中再加一件这种物品，这种策略使得必须采用v=0...V这种循环。
例2 完全背包问题 knapsack
【问题描述】
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
【输入格式】
第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；
第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。
【输出格式】
仅一行，一个数，表示最大总价值。
【样例输入】knapsack.in
```10 4
2 1
3 3
4 5
7 9
```【样例输出】knapsack.out
max=12
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[ 220 ] = {0};
int main()
{
int M, N;
scanf("%d%d", &M, &N);
int w, c;
for( int i = 1; i <= N; i++ ){
scanf("%d%d", &w, &c);
for( int j = 0; j <= M; j++ ){
if( j-w >= 0 )
f[j] = max( f[j], f[j-w] + c );
}
}
printf("max=%d
", f[M]);
return 0;
}
一个简单有效的优化
完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足(w_i leq w_j)且(c_i geq c_j)，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高的j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。
转化为01背包问题求解
既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第i种物品最多选V/w[i]件，于是可以把第i种物品转化为V/w[i]件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。
更高效的转化方法是：把第i种物品拆成费用为(w_i imes 2^k)、价值为(c_i imes 2^k)的若干件物品，其中(k)满足(w_i imes 2^k < V)。这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个(2^k)件物品的和。这样把每种物品拆成(log(frac{V}{w_i})+1)件物品，是一个很大的改进。
总结
完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程，分别在“基本思路”以及“O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。
多重背包问题
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本算法思路
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则：f[i][v]=max{f[i-1][v-k*w[i]]+k*c[i]|0<=k<=n[i]}。复杂度是(O(V imes sum n_i))。
转化为01背包问题
把第i种物品换成n[i]件01背包中的物品，则得到了物品数为∑n[i]的01背包问题，直接求解，复杂度仍然是(O(V imes sum n_i))。
但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。
方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,(2^{(k-1)}),(n_i-2^k+1)，且k是满足n[i]-2^k+1>0的最大整数(注意：这些系数已经可以组合出1~n[i]内的所有数字)。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。
分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示。这样就将第i种物品分成了(log n_i)种物品，将原问题转化为了复杂度为(O(V imes sum log{n_i}))的01背包问题，是很大的改进。
例3 庆功会 party
【问题描述】
为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
【输入格式】
第一行二个数n(n<=500)，m(m<=6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。
接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和购买的数量（买0件到s件均可），其中v<=100，w<=1000，s<=10。【输出格式】
第一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。
【输入样例】
5 1000 80 20 4 40 50 9 30 50 7 40 30 6 20 20 1【输出样例】
1040
参考代码1 朴素算法
#include<cstdio>
using namespace std;
int v[6002], w[6002], s[6002];
int f[6002];
int n, m;
int max(int x,int y) {
if (x < y) return y;
else return x;
}
int main(){
scanf("%d%d",&n,&m);
for (int i = 1; i <= n; i++)
scanf("%d%d%d",&v[i],&w[i],&s[i]);
for (int i = 1; i <= n; i++)
for (int j = m; j >= 0; j--)
for (int k = 0; k <= s[i]; k++){
if (j-k*v[i]<0) break;
f[j] = max(f[j],f[j-k*v[i]]+k*w[i]);
}
printf("%d",f[m]);
return 0;
}
代码二 二进制优化
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[ 6010 ] = {0};
int main()
{
int M, N;
scanf("%d%d", &N , &M);
int w, v, s;
int part_weight, part_value;
for( int i = 1; i <= N; i++ ){
scanf("%d%d%d", &w, &v, &s);
// 拆分成不同个数的物品
int k;
for( k = 1; s - (1 << k) + 1 > 0; k++){
part_weight = w * (1 << (k-1));
part_value = v * (1 << (k-1));
// 01 背包求解
for( int j = M; j >= 0; j-- ){
if( j-part_weight >= 0 )
f[j] = max( f[j], f[j-part_weight] + part_value );
}
}
// 最后一种
part_weight = w * (s - (1 << (k-1)) + 1);
part_value = v * (s - (1 << (k-1)) + 1);
for( int j = M; j >= 0; j-- ){
if( j-part_weight >= 0 )
f[j] = max( f[j], f[j-part_weight] + part_value );
}
}
printf("%d
", f[M]);
return 0;
}
总结
这里我们看到了将一个算法的复杂度由(O(V imes sum n_i))改进到(O(V imes sum log{n_i}))的过程，还知道了存在应用超出NOIP范围的知识的O(VN)算法。希望你特别注意「拆分物品」的思想和方法，自己证明一下它的正确性，并用尽量简洁的程序来实现。
混合背包
混合背包，是将上面三种背包问题混合而成的背包问题，即有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。
01背包与完全背包的混合
考虑到在01背包和完全背包中最后给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(VN)。
再加上多重背包
如果再加上有的物品最多可以取有限次，那么原则上也可以给出O(VN)的解法：遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过NOIP范围的算法的话，用多重背包中将每个这类物品分成O(log n[i])个01背包的物品的方法也已经很优了。
【例4】混合背包 mix
【问题描述】
一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
【输入格式】
第一行：二个整数，V(背包容量，V<=200)，N(物品数量，N<=30)；
第2..N+1行：每行三个整数Wi,Ci,Pi，前两个整数分别表示每个物品的重量，价值，第三个整数若为0，则说明此物品可以购买无数件，若为其他数字，则为此物品可购买的最多件数(Pi)。
【输出格式】
仅一行，一个数，表示最大总价值。
【样例输入】mix.in
10 3 2 1 0 3 3 1 4 5 4【样例输出】mix.out
11【样例解释】
选第一件物品1件和第三件物品2件。
参考程序（普通写法）：
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int m, n;
int i, j, k;
int w, p, s;
int pack[ 6010 ] = { 0 };
int item[ 31 ][ 2 ] = { 0 };
scanf("%d%d", &m, &n);
for( i = 1; i <= n; i++ ){
scanf("%d%d%d", &w, &p, &s);
if( s == 0 ){
for( j = w; j <= m; j++ ){
if( pack[ j ] < pack[ j - w ] + p ){
pack[ j ] = pack[ j - w ] + p;
}
}
}
else{
for( j = m; j >= w; j-- ){
for( k = 0; k <= s; k++){
if( j - k * w < 0 ) break;
if( pack[ j ] < pack[ j - k * w ] + p * k ){
pack[ j ] = pack[ j - k * w ] + p * k;
}
}
}
}
}
int ans = 0;
for( i = 1; i <= m; i++ ){
if( ans < pack[ i ] )
ans = pack[ i ];
}
printf("%d
", ans);
return 0;
}
二维费用的背包问题
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为c[i]。
算法思路
费用加了一维，只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+c[i]}。
如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。
物品总个数的限制
有时，「二维费用」的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种「件数」的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。换句话说，设f[v][m]表示付出费用v、最多选m件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0..V][0..M]范围内寻找答案。另外，如果要求「恰好取M件物品」，则在f[0..V][M]范围内寻找答案。
例5 潜水员 gas
【问题描述】
潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？
例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。
你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
【输入格式】
第一行有2整数m,n（1<=m<=21,1<=n<=79）。它们表示氧，氮各自需要的量。
第二行为整数k（1<=n<=1000）表示气缸的个数。
此后的k行，每行包括ai，bi，ci（1<=ai<=21，1<=bi<=79，1<=ci<=800）3整数。这些各自是：第i个气缸里的氧和氮的容量及汽缸重量。
【输出格式】
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。
参考代码：
#include <cstdio>
#include <cstring>
int main()
{
int o, n, q; // o -> Oxygen; n -> Nitrogen; q -> number of can
int oo, nn, ww;
int i, j, k;
int pack[ 88 ][ 88 ];
int v1, v2;
memset( pack, 0x7F, sizeof( pack ));
scanf("%d%d%d", &o, &n, &q);
pack[ 0 ][ 0 ] = 0;
for( i = 1; i <= q; i++ ){
scanf("%d%d%d", &oo, &nn, &ww);
for( j = o; j >= 0; j-- ){
for( k = n; k >= 0; k--){
v1 = j + oo;
v2 = k + nn;
// 这里是保证输出的pack[ o ][ n ]为所求值?
if( v1 > o ) v1 = o;
if( v2 > n ) v2 = n;
if( pack[ v1 ][ v2 ] > pack[ j ][ k ] + ww )
pack[ v1 ][ v2 ] = pack[ j ][ k ] + ww;
}
}
}
printf("%d", pack[ o ][ n ]);
return 0;
}
总结
事实上，当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一维以满足新的限制是一种比较通用的方法。
分组的背包问题
有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是c[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
算法分析
这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有f[k][v]=max{f[k-1][v]，f[k-1][v-w[i]]+c[i]|物品i属于第k组}。
一维数组的实现方法为代码如下：
for 所有的组k
for v = V...0
for 所有的i in 组k
f[v]=max{f[v],f[v-w[i]]+c[i]}
这里for v = V...0这一层循环必须在for 所有的i in 组k之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。
另外，显然可以对每组中的物品应用完全背包中「一个简单有效的优化」。
【例6】分组背包
【问题描述】
一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
【输入格式】
第一行：三个整数，V(背包容量，V<=200)，N(物品数量，N<=30)和T(最大组号，T<=10)；
第2..N+1行：每行三个整数Wi,Ci,P，表示每个物品的重量，价值，所属组号。
【输出格式】
仅一行，一个数，表示最大总价值。
【样例输入】group.in
10 6 3 2 1 1 3 3 1 4 8 2 6 9 2 2 8 3 3 9 3【样例输出】group.out
20
参考代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int pack[ 202 ];
int v, n, t;
int w[ 11 ][ 202 ], c[ 11 ][ 202 ]; // w -> 物品重量; c -> 物品价值
int group[ 11 ];
int a, b, p;
int i, j, k;
memset( pack, 0, sizeof( pack ));
memset( group, 0, sizeof( group ));
memset( w, 0, sizeof( w ));
memset( c, 0, sizeof( c ));
scanf("%d%d%d", &v, &n, &t); // v --> 背包重量; n --> 物品重量; t --> 最大组号
for( i = 1; i <= n; i++){
scanf("%d%d%d", &a, &b, &p);
group[ p ]++;
w[ p ][ group[ p ] ] = a;
c[ p ][ group[ p ] ] = b;
}
for( i = 1; i <= t; i++ ){
for( j = v; j >= 0; j-- ){
for( k = 0; k <= group[ i ]; k++ ){
if( j - w[ i ][ k ] >= 0 ){
pack[ j ] = max( pack[ j ], pack[ j - w[ i ][ k ] ] + c[ i ][ k ] );
}
}
}
}
printf("%d", pack[ v ]);
return 0;
}
小结
分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题。
有依赖的背包问题【未完】
简化的问题
这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。
算法分析
背包问题的方案总数
对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。
对于这类改变问法的问题，一般只需将状态转移方程中的max改成sum即可。例如若每件物品均是01背包中的物品，转移方程即为f[i][v]=sum{f[i-1][v],f[i-1][v-w[i]]+c[i]}，初始条件f[0][0]=1。
事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。
例7 货币系统
【问题描述】
给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。样例：设n=3，m=10，要求输入和输出的格式如下：
【样例输入】money.in
3 10 //3种面值组成面值为10的方案 1 //面值1 2 //面值2 5 //面值5【样例输出】money.out
10 //有10种方案
参考代码
#include <iostream>
#include <cstring>
using namespace std;
long long plan[ 10086 ];
int main( void )
{
int n, m;
int p;
int i, j, k;
memset( plan, 0, sizeof( plan ));
cin >> n >> m;
plan[ 0 ] = 1;
for( i = 1; i <= n; i++ ){
cin >> p;
for( j = m; j >= 0; j-- ){
for( k = 1; k <= j / p; k++){
plan[ j ] += plan[ j - k * p ];
}
}
}
cout << plan[ m ] << endl;
return 0;
}
小结
显然，这里不可能穷尽背包类动态规划问题所有的问法。甚至还存在一类将背包类动态规划问题与其它领域（例如数论、图论）结合起来的问题，在这篇论背包问题的专文中也不会论及。但只要深刻领会前述所有类别的背包问题的思路和状态转移方程，遇到其它的变形问法，应该也不难想出算法。
经典题
合并石子
石子放成一排
[NOI1995 石子合并] [CODEVS 1048] [YBT 1274]
在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
计算出将N堆石子合并成一堆的最小得分。
算法分析
由于只能选择相邻的两堆石子合并，所以无法用贪心方法一直选择最小石子堆。
这个问题符合动态规划的思想，通过不断更新合并所得结果来一步步得出最优解。
我们令f[i][j]表示从i堆到j堆的最小代价，sum[i][j]表示从i到j的石子总和，有最终结果f[1][N]，初始状态f[i][i]=0。通过两重循环依次得出合并2堆、3堆、...、N堆石子的最优结果。
有状态转移方程：f[i][j] = min{f[i][j], f[i][k] + f[k+1][j] + sum[i][j]} (i<=k<j) ，f[i][j]初始值为INF。
代码如下（用前缀和记录sum数组减少空间开销）：
/* By FrozenApple */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 110
#define INF 2147483640
int arr[ MAXN ], sum[ MAXN ], f[ MAXN ][ MAXN ];
int main()
{
int N;
scanf("%d", &N);
for( int i = 1; i <= N; i++ ){
scanf("%d", &arr[i] );
sum[i] = sum[i-1] + arr[i];
}
for( int len = 2; len <= N; len++ ){
for(int i = 1; i <= N - len + 1; i++ ){ // combine form i to j
int j = i + len - 1;
f[i][j] = INF;
for( int k = i; k <= j - 1; k++ ){
if( f[i][j] > f[i][k] + f[k+1][j] + (sum[j]-sum[i-1]) ){
f[i][j] = f[i][k] + f[k+1][j] + (sum[j]-sum[i-1]);
}
}
}
}
printf("%d
", f[1][N]);
return 0;
}
石子放成一圈 [未完成]
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
算法分析
不难发现，其实解法类似。不过由于是环形，我们要在每次相加只有都对个数取余数，以防止数组越界。
乘积最大 [题解未完成]
[NOIP2000 提高组第二题] [NOI 8782] [YBT 1275] [CODEVS 1017] [LUOGU 1018]
今年是国际数学联盟确定的“2000――世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰9090周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312， 当(N=3,K=1)时会有以下两种分法：
1、(3 imes 12=36) 2、(31 imes 2=62)
这时，符合题目要求的结果是: (31 imes 2 = 62)
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
算法分析
这一题按照插入的乘号数量来划分阶段。
代码如下：
/* By FrozenApple */
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN 43
using namespace std;
int N, K;
int f[ MAXN ];
char str[ MAXN ], stmp[ MAXN ];
void input( char *s ){
int sum = 0;
for( int i = 1; i <= N - K; i++ ){
sum = (sum << 3) + (sum << 1) + s[i] - '0';
f[i] = sum;
}
}
int main()
{
scanf("%d%d", &N, &K);
scanf("%s", str+1);
input(str);
for( int tk = 1; tk <= K; tk++ ){
for( int tn = N - K + tk; tn >= tk + 1; tn-- ){
f[tn] = -2147400000;
for( int i = tk; i <= tn - 1; i++ ){
memcpy(stmp, str + i + 1, tn - i);
stmp[tn-i] = 0;
if( f[i] * (atoi(stmp)) > f[tn] )
f[tn] = f[i] * (atoi(stmp));
}
}
}
printf("%d
", f[N]);
return 0;
}
编辑距离
codevs2598 luogu2758 ybt1276 noi2988
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
1、删除一个字符；
2、插入一个字符；
3、将一个字符改为另一个字符。
对任意的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。
算法分析
我们用f[i][j]表示字符串A从0到i，字符串B从0到j，他们的最优编辑距离。
最终结果为f[m][n]，m，n分别为两串串长。
易知f[0][0]为两串都为空时的编辑距离，应为0。f[i][0]是B串为空，A串长度为i时的编辑距离。
转移方程为：
- 当
a[i]=b[j]时，f[i][j]=f[i-1][j-1] - 否则，
f[i][j] = min{f[i-1][j-1]+1, f[i][j-1]+1, f[i-1][j]+1}
这里的3个值分别表示（假设是将A串变成B串）：1. 把a[i]改成b[i]； 2. 在a[i]之后插入b[i]，这时有a[i+1]==b[i]，从而只用继续讨论f[i][j-1]； 3. 删掉a[i]，之后只需要计算f[i-1][j]的距离。
参考代码如下：
/* By FrozenApple */
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 4010
using namespace std;
char str1[ MAXN ], str2[ MAXN ];
int f[ MAXN ][ MAXN ];
int M, N;
int main()
{
scanf("%s%s", str1+1, str2+1);
M = strlen(str1+1);
N = strlen(str2+1);
for( int i = 1; i <= M; i++ ){
f[i][0] = i;
}
for( int i = 1; i <= N; i++ ){
f[0][i] = i;
}
for( int i = 1; i <= M; i++ ){
for( int j = 1; j <= N; j++ ){
if( str1[i] == str2[j] )
f[i][j] = f[i-1][j-1];
else
f[i][j] = min(min(f[i-1][j-1], f[i][j-1]), f[i-1][j]) + 1;
}
}
printf("%d
", f[M][N]);
return 0;
}
方格取数 [题解未完成]
复制书稿
现在要把m本有顺序的书分给k给人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。
现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。
算法分析
参考代码：
/* By FrozenApple */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 510
int book[ MAXN ]; // 每本书页数
int sum[ MAXN ]; // 前缀和
int f[ MAXN ][ MAXN ];
int M, K;
void print(int i, int j){ // i本书，j个人
if( j == 0 ) return;
if( j == 1 ){
printf("1 %d
", i);
return;
}
int st = i;
if( st == 0 ){
print(0, j-1);
printf("0 0
");
}
else{
int cost = book[i];
while( st >= 2 && cost + book[st-1] <= f[M][K] ){
cost += book[st-1];
st--;
}
print(st-1, j-1);
printf("%d %d
", st, i);
}
}
int main()
{
memset( f, 0x7f, sizeof(f) );
scanf("%d%d", &M, &K);
for( int i = 1; i <= M; i++ ){
scanf("%d", &book[i]);
sum[i] = sum[i-1] + book[i];
f[i][1] = sum[i];
}
for( int j = 2; j <= K; j++ ){ // 分给j人
for( int i = 1; i <= M; i++ ){ // 书
for( int k = 1; k <= i - 1; k++ ){
if( f[i][j] > max(f[i-k][j-1], sum[i]-sum[i-k]) ){ // 从k位置划分
f[i][j] = max(f[i-k][j-1], sum[i]-sum[i-k]);
}
}
}
}
// printf("%d
", f[M][K]);
print(M, K);
return 0;
}
橱窗布置【未完成】
滑雪 [题解未完成]
糖果
ybt1299 [NOI2989]
我们从余数着手进行DP，f[i][j]表示前i颗糖果在余数为j情况下的最大值。
有动态转移方程：dp[i][j]=max(dp[i-1][j], dp[i][j])
/* By FrozenApple */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 110
int N, K;
int candy[MAXN], f[MAXN][MAXN];
int main(){
scanf("%d%d", &N, &K);
for( int i = 1; i <= N; i++ ){
scanf("%d", &candy[i]);
}
for( int i = 1; i <= N; i++ ){
for( int j = 0; j < K; j++ ){
f[i][j] = f[i-1][j];
}
for( int j = 0; j < K; j++ ){
if( f[i][(f[i-1][j]+candy[i])%K] < f[i-1][j] + candy[i] ) // 更新加入糖果之后的余数情况
f[i][(f[i-1][j]+candy[i])%K] = f[i-1][j] + candy[i];
}
}
printf("%d
", f[N][0]);
return 0;
}
大盗阿福
f[i]为前i家店铺的最大收益。决策为当前这家店要不要盗。
盗：f[i] = f[i-2]+a[i] 隔一家；不盗：f[i]=f[i-1]
/* By FrozenApple */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 100010
int N;
int f[ MAXN ], a[ MAXN ];
int main()
{
int T;
scanf("%d", &T);
while( T-- ){
memset( f, 0, sizeof( f ));
scanf("%d", &N);
for( int i = 1; i <= N; i++ ){
scanf("%d", &a[i]);
}
f[1] = a[1];
for( int i = 2; i <= N; i++ ){
f[i] = max( f[i-2] + a[i], f[i-1] );
}
printf("%d
", f[N]);
}
return 0;
}
股票买卖
由于要买卖两次，并且第二次买入必须要在第一次卖出之后，故问题被分为了两个阶段。我们可以采用两次DP，分别求出从第一天到第k天所能获得的最大利益f1[k]和从第k天到最后一天所能获得的最大利益f2[k]，这样求出两个数组之后再遍历一遍分割日期k就能找出结果。
/* By FrozenApple */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 100010
int f1[ MAXN ], f2[ MAXN ], a[ MAXN ];
int N;
int main()
{
int T;
scanf("%d", &T);
while( T-- ){
memset( f1, 0, sizeof(f1) );
memset( f2, 0, sizeof(f2) );
scanf("%d", &N);
for( int i = 1; i <= N; i++ ){
scanf("%d", &a[ i ]);
}
int mm = 0x7f7f7f7f;
for( int i = 1; i <= N; i++ ){
mm = min( mm, a[i] );
f1[i] = max(f1[i-1], a[i]-mm);
}
f2[N+1] = 0;
int mx = -0x7f7f7f7f;
for( int i = N; i >= 0; i-- ){
mx = max(mx, a[i]);
f2[i] = max(f2[i+1], mx-a[i]);
}
int ans = -0x7f7f7f7f;
for( int i = 1; i <= N; i++ ){
ans = max( ans, f1[i] + f2[i] );
}
printf("%d
",ans);
}
return 0;
}
上面做法在数据范围略大时会超时（YBT数据），优化版本：
/* By FrozenApple */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 100010
int f1[ MAXN ], f2[ MAXN ], a[ MAXN ];
int mms[ MAXN ], mxs[ MAXN ];
int N;
int main()
{
int T;
scanf("%d", &T);
while( T-- ){
memset( f1, 0, sizeof(f1) );
memset( f2, 0, sizeof(f2) );
memset( mms, 0, sizeof(mms) );
memset( mxs, 0, sizeof(mxs) );
scanf("%d", &N);
for( int i = 1; i <= N; i++ ){
scanf("%d", &a[ i ]);
}
mms[0] = 0x7f7f7f7f, mxs[N+1]= -0x7f7f7f7f;
for( int i = 1; i <= N; i++ ){
mms[i] = min( mms[i-1], a[i] );
mxs[N-i+1] = max(mxs[N-i+2],a[N-i+1]);
}
for( int i = 1; i <= N; i++ ){
f1[i] = max(f1[i-1], a[i]-mms[i]);
f2[N-i+1] = max(f2[N-i+2], mxs[N-i+1] - a[N-i+1]);
}
int ans = -0x7f7f7f7f;
for( int i = 1; i <= N; i++ ){
ans = max( ans, f1[i] + f2[i] );
}
printf("%d
",ans);
}
return 0;
}