# **动态规划**

## 思想

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。

动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。

因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。

我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

## **动态规划的基本模型**

### **多阶段决策过程的最优化问题** 

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。如下图所示：

![image-20201130212106704](https://picreso.oss-cn-beijing.aliyuncs.com/image-20201130212106704.png)

​    多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。

**【例1】最短路径问题。下图给出了一个地图，地图中的每个顶点代表一个城市，两个城市间的一条连线代表道路，连线上的数值代表道路的长度。现在想从城市A到达城市E，怎样走路程最短？最短路程的长度是多少？**

![image-20201130212206651](https://picreso.oss-cn-beijing.aliyuncs.com/image-20201130212206651.png)

**【算法分析】**

​    把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的最短距离。

具体计算过程如下：

![image-20201130212233042](https://picreso.oss-cn-beijing.aliyuncs.com/image-20201130212233042.png)

``` 
S1： K = 4 有

​     F4（D1）= 3，

​     F4（D2）= 4，

​     F4（D3）= 3；

S2： K = 3 有

​     F3（C1）= MIN{ D3（C1，D1）+ F4（D1），D3（C1，D2）+ F4（D2）}

​             = MIN{ 5+3，6+4 } = 8

​     F3（C2）= D3（C2，D1）+ F4（D1）= 5+3 = 8

​     F3（C3）= D3（C3，D3）+ F4（D3）= 8+3 = 11

​     F3（C4）= D3（C4，D3）+ F4（D3）= 3+3 = 6

S3： K = 2 有  

​     F2（B1）= MIN{ D2（B1，C1）+ F3（C1），D2（B1，C2）+ F3（C2），

​     D2（B1，C3）+ F3(C3)} = MIN{ 1+8,6+8,3+11} = 9

​     F2（B2）= MIN{ D2（B2，C2）+ F3（C2），D2（B2，C4）+ F3（C4）}

​             = MIN{ 8+8，4+6 } = 10

S4： K = 1 有 

​     F1（A）= MIN{ D1（A，B1）+ F2（B1），D1（A，B2）+ F2（B2）}

​            = MIN{ 5+9，3+10} = 13
```



​    因此由A点到E点的全过程最短路径为A→B2→C4→D3→E；最短路程长度为13。

​    从以上过程可以看出，每个阶段中，都求出本阶段的各个初始状态到终点E的最短距离，当逆序倒推到过程起点A时，便得到了全过程的最短路径和最短距离。

​    在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与阶段有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，我们称这种解决多阶段决策最优化的过程为动态规划程序设计方法。



``` 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;
}

```



## **动态规划的基本概念和基本模型构成** 

 现在我们来介绍动态规划的基本概念。

1. **阶段和阶段变量：**

​    用动态规划求解一个问题时，需要将问题的全过程恰当地分成若干个相互联系的阶段，以便按一定的次序去求解。描述阶段的变量称为阶段变量，通常用K表示，阶段的划分一般是根据时间和空间的自然特征来划分，同时阶段的划分要便于把问题转化成多阶段决策过程，如例题1中，可将其划分成4个阶段，即K = 1，2，3，4。

2. **状态和状态变量：**

​    某一阶段的出发位置称为状态，通常一个阶段包含若干状态。一般地，状态可由变量来描述，用来描述状态的变量称为状态变量。如例题1中，C3是一个状态变量。

3. **决策、决策变量和决策允许集合**：

​    在对问题的处理中作出的每种选择性的行动就是决策。即从该阶段的每一个状态出发，通过一次选择性的行动转移至下一阶段的相应状态。一个实际问题可能要有多次决策和多个决策点，在每一个阶段的每一个状态中都需要有一次决策，决策也可以用变量来描述，称这种变量为决策变量。在实际问题中，决策变量的取值往往限制在某一个范围之内，此范围称为允许决策集合。如例题1中，F3（C3）就是一个决策变量。

4．**策略和最优策略：**

​    所有阶段依次排列构成问题的全过程。全过程中各阶段决策变量所组成的有序总体称为策略。在实际问题中，从决策允许集合中找出最优效果的策略成为最优策略。

5. **状态转移方程**

​    前一阶段的终点就是后一阶段的起点，对前一阶段的状态作出某种决策，产生后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。

### **最优化原理与无后效性** 

​      上面已经介绍了动态规划模型的基本组成，现在需要解决的问题是：什么样的“多阶段决策问题”才可以采用动态规划的方法求解。

​      一般来说，能够采用动态规划方法求解的问题，必须满足最优化原理和无后效性原则：

​      1、动态规划的最优化原理。作为整个过程的最优策略具有：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略的性质。也可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，而非最优解对问题的求解没有影响。在例题1最短路径问题中，A到E的最优路径上的任一点到终点E的路径，也必然是该点到终点E的一条最优路径，即整体优化可以分解为若干个局部优化。

​      2、动态规划的无后效性原则。所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整的总结，此前的历史只能通过当前的状态去影响过程未来的演变。在例题1最短路径问题中，问题被划分成各个阶段之后，阶段K中的状态只能由阶段K+1中的状态通过状态转移方程得来，与其它状态没有关系，特别与未发生的状态没有关系，例如从Ci到E的最短路径，只与Ci的位置有关，它是由Di中的状态通过状态转移方程得来，与E状态，特别是A到Ci的路径选择无关，这就是无后效性。

​      由此可见，对于不能划分阶段的问题，不能运用动态规划来解；对于能划分阶段，但不符合最优化原理的，也不能用动态规划来解；既能划分阶段，又符合最优化原理的，但不具备无后效性原则，还是不能用动态规划来解；误用动态规划程序设计方法求解会导致错误的结果。

### **动态规划设计方法的一般模式** 

​    动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态；或倒过来，从结束状态开始，通过对中间阶段决策的选择，达到初始状态。这些决策形成一个决策序列，同时确定了完成整个过程的一条活动路线，通常是求最优活动路线。

动态规划的设计都有着一定的模式，一般要经历以下几个步骤：

1、划分阶段

​    按照问题的时间或空间特征，把问题划分为若干个阶段。在划分阶段时，注意划分后的阶段一定是有序的或者是可排序的，否则问题就无法求解。

2、确定状态和状态变量

​    将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

3、确定决策并写出状态转移方程

​    因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可以写出。但事实上常常是反过来做，根据相邻两段的各个状态之间的关系来确定决策。

4、寻找边界条件

​    给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

## 动态规划与递推
​    由于动态规划的“名气”如此之大，以至于很多人甚至一些资料书上都往往把一种与动态规划十分相似的算法，当作是动态规划。这种算法就是递推。实际上，这两种算法还是很容易区分的。

​    按解题的目标来分，信息学试题主要分四类：判定性问题、构造性问题、计数问题和最优化问题。我们在竞赛中碰到的大多是最优化问题，而动态规划正是解决最优化问题的有力武器，因此动态规划在竞赛中的地位日益提高。而递推法在处理判定性问题和计数问题方面也是一把利器。下面分别就两个例子，谈一下递推法和动态规划在这两个方面的联系。

**【例2】数塔问题（IOI94）有形如图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。**

![image-20201130212555529](https://picreso.oss-cn-beijing.aliyuncs.com/image-20201130212555529.png)

​    这道题如果用枚举法，在数塔层数稍大的情况下（如40），则需要列举出的路径条数将是一个非常庞大的数目。如果用贪心法又往往得不到最优解。在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算。从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要

左右两道路径上的最大值求出来了才能作出决策。同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。

​    一般说来，很多最优化问题都有着对应的计数问题；反过来，很多计数问题也有着对应的最优化问题。因此，我们在遇到这两类问题时，不妨多联系、多发展，举一反三，从比较中更深入地理解动态规划的思想。

​    其实递推和动态规划这两种方法的思想本来就很相似，也不必说是谁借用了谁的思想。关键在于我们要掌握这种思想，这样我们无论在用动态规划法解最优化问题，或是在用递推法解判定型、计数问题时，都能得心应手、游刃有余了。

**【解法一】（逆推法）**

**【算法分析】**

​    1. 贪心法往往得不到最优解：本题若采用贪心法则：13-11-12-14-13，其和为63,但存在另一条路：13-8-26-15-24，其和为86。

​    贪心法问题所在：眼光短浅。

​    2. 动态规划求解：动态规划求解问题的过程归纳为：自顶向下的分析，自底向上计算。

​    其基本方法是：

​    划分阶段：按三角形的行，划分阶段，若有n行，则有n-1个阶段。

​    A．从根结点13出发，选取它的两个方向中的一条支路，当到倒数第二层时，每个结点其后继仅有两个结点，可以直接比较，选择最大值为前进方向，从而求得从根结点开始到底端的最大路径。

​    B．自底向上计算：（给出递推式和终止条件）

​    1. 从底层开始，本身数即为最大数；

​    2. 倒数第二层的计算，取决于底层的数据：12+6=18，13+14=27，24+15=39，24+8=32；

​    3. 倒数第三层的计算，取决于底二层计算的数据：27+12=39，39+7=46，39+26=65

​    4. 倒数第四层的计算，取决于底三层计算的数据：46+11=57，65+8=73

​    5. 最后的路径：13——8——26——15——24 

​    C．数据结构及算法设计

​    1. 图形转化：直角三角形，便于搜索：向下、向右

​    2. 用三维数组表示数塔：a[x,y,1]表示行、列及结点本身数据,a[x,y,2]能够取得最大值,a[x,y,3]表示前进的方向——0向下，1向右；

​    3. 算法：

​    数组初始化，输入每个结点值及初始的最大路径、前进方向为0；

​    从倒数第二层开始向上一层求最大路径，共循环N-1次；

​    从顶向下，输出路径：究竟向下还是向右取决于列的值，若列的值比原先多1则向右，否则向下。

``` c
参考程序
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	int n,x,y;
	int a[51][51][3];
	cout<<"please input the number of rows:";
	cin>>n;
	memset(a,0,sizeof(0));
	for (x=1;x<=n;x++)                         //输入数塔的初始值
     	for (y=1;y<=x;y++)
	     	{
			cin>>a[x][y][1];
			a[x][y][2]=a[x][y][1];
			a[x][y][3]=0;                          //路径走向，默认向下
		} 
      for (x=n-1;x>=1;x--)
            for (y=1;y<=x;y++)
                  if (a[x+1][y][2]>a[x+1][y+1][2])        //选择路径，保留最大路径值
                  { a[x][y][2]=a[x][y][2]+a[x+1][y][2]; a[x][y][3]=0; }
                  else { a[x][y][2]=a[x][y][2]+a[x+1][y+1][2]; a[x][y][3]=1; }
      cout<<"max="<<a[1][1][2]<<endl;           //输出数塔最大值
      y=1;
      for (x=1;x<=n-1;x++)                      //输出数塔最大值的路径
      {
             cout<<a[x][y][1]<<"->";
             y=y+a[x][y][3];                       //下一行的列数
      }
     cout<<a[n][y][1]<<endl;
}

输入：
5               //数塔层数
13
11   8
12   7    26
6   14    15    8
12   7    13   24    11

输出结果：
 max=86
 13->8->26->15->24


```

**【解法二】（顺推法）**

**【算法分析】**

​    此题贪心法往往得不到最优解，例如13-11-12-14-13其路径的值为63，但这不是最优解。

​    穷举搜索往往是不可能的，当层数N = 100时，路径条数P = 299这是一个非常大的数，即使用世界上最快的电子计算机，也不能在规定时间内计算出来。

​    对这道题唯一正确的方法是动态规划。如果得到一条由顶到底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶点至该中间点的路径所经过的数字和也为最大。因此本题是一个典型的多阶段决策最优化问题。在本题中仅要求输出最优解，为此我们设置了数组A[i,j]保存三角形数塔，B[i,j]保存状态值，按从上往下方式进行求解。

​    阶段i：以层数来划分阶段，由从上往下方式计算；因此可通过第一重循环:

​    for (int i=1;i<=n;i++) 枚举每一阶段； 

​    状态B[i][j]：由于每个阶段中有多个状态，因此可通过第二重循环:

​    for (int j=1;j<=i;j++)求出每个阶段的每个状态的最优解B[i][j]；

​    决 策：每个状态最多由上一层的两个结点连接过来，因此不需要做循环。

``` c
【参考程序】
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	int n,i,j,a[200][200],b[200][200],max;
    cin>>n;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for (i=1;i<=n;++i)
		for (j=1;j<=i;++jj)
      	{
        		cin>>a[i][j];
        		b[i][j]=a[i][j];
      	} 
    
     for (i=2;i<=n;++i)                         //选择路径，保留最大路径值
           for (j=1;j<=i;++j)
                 if (b[i-1][j-1]>b[i-1][j])
                       b[i][j]=b[i][j]+b[i-1][j-1];
                 else b[i][j]=b[i][j]+b[i-1][j];
     max=0;
     for (j=1;j<=n;++j)
            if (b[n][j]>max)                         //在第n行中找出数塔最大值
                  max=b[n][j];
     cout<<"Max="<<max<<endl;                  //输出数塔最大值  
}


```

**【例3】求最长不下降序列**

㈠.  问题描述：

​    设有由n个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)<>b(j) (i<>j)，若存在i1<i2<i3< … < ie 且有b(i1)<b(i2)< … <b(ie)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的不下降序列。

​    例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，同时也有7 ，9，16，18，19，21，22，63长度为8的不下降序列。

㈡.  算法分析：

​    根据动态规划的原理，由后往前进行搜索(当然从前往后也一样)。

1. 对b(n)来说，由于它是最后一个数，所以当从b(n)开始查找时，只存在长度为1的不下降序列；

2. 若从b(n-1)开始查找，则存在下面的两种可能性：
   1. 若b(n-1)<b(n)则存在长度为2的不下降序列b(n-1)，b(n)。
   2. 若b(n-1)>b(n)则存在长度为1的不下降序列b(n-1)或b(n)。
3. 一般若从b(i)开始，此时最长不下降序列应该按下列方法求出:

在b(i+1),b(i+2),…,b(n)中，找出一个比b(i)大的且最长的不下降序列，作为它的后继。

㈢.  数据结构：

​    为算法上的需要，定义一个整数类型二维数组b(N,3)

1. b(I,1)表示第I个数的数值本身；
2. b(I,2)表示从I位置到达N的最长不下降序列长度
3. b(I,3)表示从I位置开始最长不下降序列的下一个位置，若b[I,3]=0则表示后面没有连接项。

㈣.  求解过程：

1. 从倒数第二项开始计算，后面仅有1项，比较一次，因63>15，不符合要求，长度仍为1。
2. 从倒数第三项开始其后有2项，需做两次比较，得到目前最长的不下降序列为2，如下表：

![image-20201130212814347](https://picreso.oss-cn-beijing.aliyuncs.com/image-20201130212814347.png)

㈤.  一般处理过程是：

1. 在i+1,i+2,…,n项中，找出比b[I,1]大的最长长度L以及位置K;

2. 若L>0，则b[I,2]:=L+1;b[I,3]:=k;

​     最后本题经过计算，其数据存储表如下：

![image-20201130212824273](https://picreso.oss-cn-beijing.aliyuncs.com/image-20201130212824273.png)

``` c
初始化:
for (i=1;i<=n;i++)
{
       cin>>b[i][1];
       b[i][2]=1;b[i][3]=0;
}
下面给出求最长不下降序列的算法:
for (i=n-1;i>=1;i--)
{
       l=0;k=0;
       for (j=i+1;j<=n;j++)
             if((b[j][1]>b[i][1])&&(b[j][2]>l))
             {
                   l=b[j][2];
                   k=j;
             }
       if (l>0) 
       {
             b[i][2]=l+1;
             b[i][3]=k;
       }
}
下面找出最长不下降序列：
k=1;
for (j=1;j<=n;j++)
      if (b[j][2]>b[k][2])  k=j;

最长不下降序列长度为b[k][2]序列
while (k!=0)  
{
      cout<<’’<<b[k][1];
      k=b[k][3];
}

```

``` c
#include<iostream>
using namespace std;
int main()
{
   int n,i,j,l,k,b[200][10]; 
   cout<<"input n:"<<endl;
   cin>>n;
   for (i=1;i<=n;i++)                          //输入序列的初始值
    {
      cin>>b[i][1];
      b[i][2]=1;b[i][3]=0;
    }
       for (i=n-1;i>=1;i--)                       //求最长不下降序列
     {
       l=0;k=0;
        for (j=i+1;j<=n;j++)
         if ((b[j][1]>b[i][1])&&(b[j][2]>l))
          {
             l=b[j][2];
             k=j;
          }
        if (l>0)
         {
           b[i][2]=l+1;b[i][3]=k;
         }  
     }
     k=1;
     for (j=1;j<=n;j++)                        //求最长不下降序列的起始位置
      if (b[j][2]>b[k][2]) k=j;
     cout<<"max="<<b[k][2]<<endl;              //输出结果
     while (k!=0)                              //输出最长不下降序列
     {
        cout<<' '<<b[k][1];
        k=b[k][3];   
      } 
}
程序运行结果：
输入：14
13 7 9 16 38 24 37 18 44 19 21 22 63 15
输出：max=8
7  9  16  18  19  21  22  63


```

**【例4】拦截导弹(Noip1999)**

　　**某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。**

　　**输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。**

**样例：**

**INPUT                    OUTPUT**

**389 207 155 300 299 170 158 65     6（最多能拦截的导弹数）**

​                       **2（要拦截所有导弹最少要配备的系统数）**

**【算法分析】**

  **第一问即经典的最长不下降子序列问题，可以用一般的DP算法，也可以用高效算法，但这个题的数据规模不需要。**

　　**用a[x]表示原序列中第x个元素，b[x]表示长度为x的不下降子序列的长度，。当处理第a[x]时，可查找它可以连接到长度最大为多少的不下降子序列后（即与部分b[x]比较）。假设可以连到长度最大为max的不下降子序列后，则b[x]:=max+1。b数组被赋值的最大值就是第一问的答案。**

　　**第二问用贪心法即可。每颗导弹来袭时，使用能拦截这颗导弹的防御系统中上一次拦截导弹高度最低的那一套来拦截。若不存在符合这一条件的系统，则使用一套新系统。**

``` c
【参考程序】（顺推法）
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
  int i,j,k,x,n,max,m,a[10000],b[10000],h[10000];
  i=1;n=0;m=0;
  memset(a,0,sizeof(a));
  memset(b,0,sizeof(b));
  memset(h,0,sizeof(h));
  while (cin>>a[i])
   {
      max=0;
      for (j=1;j<=i-1;j++)                //计算前i-1个导弹最佳拦截的方案
       if (a[j]>=a[i])
        if (b[j]>max)
         max=b[j];
      b[i]=max+1;  
if (b[i]>m) m=b[i];
      x=0;
      for (k=1;k<=n;k++)                  //计算由哪一套系统拦截导弹
       if (h[k]>=a[i]) 
         if (x==0) x=k;
         else if (h[k]<h[x]) x=k;          //如果有多套系统可拦截，则选择上一次拦截高度最低的
      if (x==0) {n++;x=n;}                //新增一套导弹拦截系统
      h[x]=a[i];
      i++;
   } 
  cout<<m<<endl<<n<<endl;
}经过计算，其数据存储表如下
	

```

![image-20201130212935486](https://picreso.oss-cn-beijing.aliyuncs.com/image-20201130212935486.png)

**【例5】**下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。

![image-20201130212957901](https://picreso.oss-cn-beijing.aliyuncs.com/image-20201130212957901.png)

如图：求v1到v10的最短路径长度及最短路径。

【样例输入】short.in

10

0 2 5 1 0 0 0 0 0 0
 0 0 0 0 12 14 0 0 0 0
 0 0 0 0 6 10 4 0 0 0
 0 0 0 0 13 12 11 0 0 0
 0 0 0 0 0 0 0 3 9 0
 0 0 0 0 0 0 0 6 5 0
 0 0 0 0 0 0 0 0 10 0
 0 0 0 0 0 0 0 0 0 5
 0 0 0 0 0 0 0 0 0 2
 0 0 0 0 0 0 0 0 0 0

【样例输出】short.out

minlong=19

1 3 5 8 10

【算法分析】逆推法

​    设f[i]表示点i到v10的最短路径长度，则 f[10]=0

 f[i]=min{ a[i][x]+f[x] 当a[i][x]>0 ,i<x<=n时}

``` c
　#include<iostream>
　using namespace std;
　#include<cstring>
　#include<cstdio>
　int main()
{
　   long n,i,j,x,f[100],c[100],a[100][100]; 
　   memset(a,0,sizeof(a));
　   memset(c,0,sizeof(c));
　   cin>>n;
　   for (i=1;i<=n;i++)                         //输入各个城市之间距离
　     for (j=1;j<=n;j++)
　       cin>>a[i][j];
　   for (i=1;i<=n;i++)
　     f[i]=1000000;                            //初始化，默认每一个城市到达终点都是1000000
　   f[n]=0;
　   for (i=n-1;i>=1;i--)                       //从终点往前逆推，计算最短路径
　    for (x=i+1;x<=n;x++)                      //若f[x]=1000000表示城市x到终点城市不通
　     if ((a[i][x]>0)&&(f[x]!=1000000)&&(f[i]>a[i][x]+f[x])) 
　      {                                       //a[i][x]>0表示城市i和城市x通路
　        f[i]=a[i][x]+f[x];                    //城市i到终点最短路径的值
　        c[i]=x;
　      }
　    cout<<"minlong="<<f[1]<<endl;             //输出最短路径的值
　    x=1;
　while (x!=0)                              //输出路过的各个城市
　     {
　        cout<<x<<' ';
　        x=c[x];
　     } 
　     cout<<endl; 
　}


```

【例6】挖地雷

【问题描述】

　　在一个地图上有N个地窖（N<=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。

【输入格式】

  N                     //地窖的个数

  W1，W2，……WN                               //每个地窖中的地雷数

  X1，Y1                   //表示从X1可到Y1

  X2，Y2

  ……

  0，0                    //表示输入结束

【输出格式】

  K1-K2-…-Kv                //挖地雷的顺序

  MAX                    //最多挖出的地雷数

【输入样例】Mine.in

  6

  5 10 20 5 4 5

  1 2

  1 4

  2 4

  3 4

  4 5

   4 6

  5 6

  0 0

【输出样例】Mine.out

  3-4-5-6

  34

【算法分析】

　　本题是一个经典的动态规划问题。很明显，题目规定所有路径都是单向的，所以满足无后效性原则和最优化原理。设W[i]为第i个地窖所藏有的地雷数，A[i][j]表示第i个地窖与第j个地窖之间是否有通路，F(i)为从第i个地窖开始最多可以挖出的地雷数，则有如下递归式：

　　F[i]=max{ W[i]+ F[j]}        (i<j<=n , A[i][j]=true)

　　边界：F[n]=W[n]

　　于是就可以通过递推的方法，从后F(n)往前逐个找出所有的F[i]，再从中找一个最大的即为问题2的解。对于具体所走的路径（问题1），可以通过一个向后的链接来实现。

``` c
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
   long f[201]={0},w[201],c[201]={0};
   bool a[201][201]={0};
   long i,j,n,x,y,l,k,max;
   memset(f,0,sizeof(f));
        memset(c,0,sizeof(c));
   memset(a,false,sizeof(a));
   cin>>n;
   for (i=1;i<=n;i++)
     cin>>w[i];                                //输入每个地窖中的地雷数
   do
    {
      cin>>x>>y;                               //表示从X可到Y
      if ((x!=0)&&(y!=0)) a[x][y]=true;
    }while ((x!=0)||(y!=0));
    f[n]=w[n];                                 //从后F[n]往前逐个找出所有的F[i]
    for (i=n-1;i>=1;i--)
     {
      l=0;k=0;
      for (j=i+1;j<=n;j++)
       if ((a[i][j])&&(f[j]>l))
         { l=f[j]; k=j; }
      f[i]=l+w[i];                             //保存从第i个地窖起能挖到最大地雷数
      c[i]=k;                                  //k地窖是i地窖最优路径
     }
     k=1;
     for (j=2;j<=n;j++)                        //计算最多挖出的地雷数
      if (f[j]>f[k]) k=j;
     max=f[k];
     cout<<k;
     k=c[k];
     while (k!=0)                              //输出挖地雷的顺序
      {
        cout<<"-"<<k;
        k=c[k];
      } 
     cout<<endl;
     cout<<max<<endl;                          //输出最多挖出的地雷数
}


```

**【例7】** 友好城市

 **【问题描述】**

​    Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。

​    每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

**【输入格式】**

​    第1行，一个整数N(1<=N<=5000)，表示城市数。

​    第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。(0<=xi<=10000)

**【输出格式】**

​    仅一行，输出一个整数，表示政府所能批准的最多申请数。

**【输入样例】**

  7

  22 4

  2 6

  10 3

  15 12

  9 8

  17 17

  4 2

【输出样例】

4

【算法分析】

​    　　我们将每对友好城市看成一条线段，则这道题的描述化为：有N条线段，问最少去掉多少条线，可以使剩下的线段互不交叉？

　　第一，以北岸为线的起点而南岸为线的终点；先将所有的线按照起点坐标值从小到大排序，按照每条线的终点坐标计算交叉数：求线I的交叉数A[I]，则检查所有1..I-1条线，若线J( 1<= J< I)的终点值大于线I的终点值，则线I与线J相交。A[I]与A[J]同时加1。整个搜索量最大为5000*5000。

第二，将A数组从大到小排序，每删除一条线，则将与之相交的线的A值减1，重复这个过程，直到所有A值都为0。此时剩下的线则全不交叉。 

如上数据，则可得下面结果：

![image-20201130213257714](https://picreso.oss-cn-beijing.aliyuncs.com/image-20201130213257714.png)

​    此时，1、2、3航线的交叉数都一样，如果删去的是3、5线，则剩下的1、2、4线互不相交，最多航线数为3；但如果删去的是2、3，则还要删去第5线才符合要求，此时的最多航线数为2，不是最优解。

​    于是，我们从上面的分析中再深入，将航线按起点坐标排好序后，如上所述，在本题中，只要线J的起点小于线I的起点，同时它的终点也小于线I的终点，则线J和线I不相交。因此，求所有线中最多能有多少条线不相交，实际上是从终点坐标值数列中求一个最长不下降序列。这就把题目转化为一个非常典型的动态规划题目了。

​    求最长不下降序列的规划方程如下：

　　   L(Si)=max{L(Sj)}+1；1< = j < i且 Sj < Si。Si为航线的终点坐标值。

　　从以上分析过程可以得出：当我们拿到一道题时，不要急于求解，而应先将题目的表面现象一层层象剥竹笋一样去掉，只留下最实质的内容。这时再来设计算法，往往能事半功倍。

【例8】合唱队形

【问题描述】

　　N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

　　合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1≤i≤K)。

　　你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

【输入文件】

　　输入文件chorus.in的第一行是一个整数N（2 ≤ N ≤ 100），表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti（130 ≤ Ti ≤ 230）是第i位同学的身高（厘米）。

【输出文件】

　　输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

【样例输入】

8

186 186 150 200 160 130 197 220

【样例输出】

4

【数据规模】

对于50%的数据，保证有n ≤ 20；对于全部的数据，保证有n≤100。

【算法分析】

　　我们按照由左而右和由右而左的顺序，将n个同学的身高排成数列。如何分别在这两个数列中寻求递增的、未必连续的最长子序列，就成为问题的关键。设

　　a 为身高序列，其中a[i]为同学i的身高；

　　b 为由左而右身高递增的人数序列，其中 b[i]为同学1‥同学i间（包括同学i）身高满足递增顺序的最多人数。显然b[i]={b[j]|同学j的身高<同学i的身高}+1；

　　c为由右而左身高递增的人数序列，其中c[i]为同学n‥同学i间（包括同学i）身高满足递增顺序的最多人数。显然c[i]={c[j]|同学j的身高<同学i的身高}+1；

　　由上述状态转移方程可知，计算合唱队形的问题具备了最优子结构性质(要使b[i]和c[i]最大，子问题的解b[j]和c[k]必须最大(1≤j≤i-1 ，i+1≤k≤n))和重迭子问题的性质(为求得b[i]和c[i]，必须一一查阅子问题的解b[1]‥b[i-1]和c[i+1]‥c[n])，因此可采用动态程序设计的方法求解。

　　显然，合唱队的人数为(公式中同学i被重复计算，因此减1)，n减去合唱队人数即为解。

``` c
#include<cstring>
#include<iostream>
using namespace std;
int a[200],b[200],c[200];
main()
{
  int n,i,j,max;
  cin>>n;                                         //读学生数
  memset(b,0,sizeof(b));                //身高满足递增顺序的两个队列初始化
  memset(c,0,sizeof(c)); 
  for (i=1;i<=n;i++)                          //读每个学生的身高
   cin>>a[i];
  for (i=1;i<=n;i++)                          //按照由左而右的顺序计算b序列
   {
     b[i]=1;
     for (j=1;j<=i-1;j++)
      if ((a[i]>a[j])&&(b[j]+1>b[i]))
       b[i]=b[j]+1;
   }   
  for (i=n;i>=1;i--)                           //按照由右而左的顺序计算c序列
   {
     c[i]=1;
     for (j=i+1;j<=n;j++)
      if ((a[j]<a[i])&&(c[j]+1>c[i]))
        c[i]=c[j]+1;
   } 
  max=0;                                       //计算合唱队的人数max（其中1人被重复计算
  for (i=1;i<=n;i++)
    if (b[i]+c[i]>max)
       max=b[i]+c[i];
  cout<<n-max+1<<endl;                         //输出出列人数
}
　　　这个算法的时间复杂度为O(n2)，在1秒时限内可解决n≤100范围内的问题。


```

**【例9】机器分配**

**【问题描述】**

　　**总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。**

　　**输入数据文件格式为：第一行有两个数，第一个数是分公司数N，第二个数是设备台数M。**

**接下来是一个N\*M的矩阵，表明了第 I个公司分配 J台机器的盈利。**

**【输入样例】assigned.in**

　　**3 3                    //3个分公司分3台机器**

　　**30 40 50**

　　**20 30 50**

　　**20 25 30**

**【输出样例】assigned.out**

　　**70                     //最大盈利值为70**

　　**1 1                    //第一分公司分1台**

　　**2 1                    //第二分公司分1台**

　　**3 1                    //第三分公司分1台**

**【算法分析】**

``` 
　　按照公司的顺序来分配机器，即按照公司的顺序划分阶段，第一个阶段把M台设备分给第一个公司，记录下来获得的各个盈利值，然后把M台设备分给前两个公司，和第一个阶段比较记录下来更优的各个盈利值，一直到第N个阶段把M台机器全部分给了N个公司，就可以得到最优解，下面来讨论两个阶段之间的关系，设数组F[I][J]表示前I个公司分配J台机器的最大盈利，数组F[I-1][K]表示前I-1个公司分配K台机器的最大盈利(1≤I≤N,1≤J≤M,0≤K≤J),用Value[I][J]表示第I个公司分配 J台机器的盈利, 则F[I][J]可以由下面的式子中取最大值获得：

 F[I-1][0]+Value[I][J]  //前I-1公司分配0台机器最大盈利+第I个公司分配J台的机器的盈利

 F[I-1][1]+Value[I][J-1] //前I-1公司分配1台机器最大盈利+第I个公司分配J-1台的机器的盈利

 F[I-1][2]+Value[I][J-2] //前I-1公司分配2台机器最大盈利+第I个公司分配J-2台的机器的盈利

 F[I-1][J-1]+Value[I][1] //前I-1公司J-1分配台机器最大盈利+第I个公司分配1台的机器的盈利

 F[I-1][J]+Value[I][0]  //前I-1公司分配J台机器最大盈利+第I个公司分配0台的机器的盈利

　　在这里用机器数用做每个阶段的状态，由于Value[I][J]的值为定值，要使前面每个式子的值最大，就必须使第i-1阶段的各个状态的值最大，阶段i的状态只能由阶段i-1中的状态通过状态转移方程求得，与其他状态没有关系。由此可见，该问题具备了最优子结构和无后效性原则，适宜使用动态程序设计方法求解。状态转移方程为：F[I][J]=MAX{F[I-1][K]+Value[I][J-K]} (1≤I≤N,1≤J≤M,0≤K≤J)

　　初始值：F[0][0]=0，F[n][m]的值即为所求最大盈利值。
```

``` c
【参考程序】
#include<iostream>
using namespace std;
#include<cstring>
int show(int,int);
long max1,f[11][20],value[11][20];
int main()
{
  long m,n,i,j,k;
  cin>>n>>m;
  for (i=1;i<=n;i++)
   for (j=1;j<=m;j++)
    cin>>value[i][j];
  for (i=1;i<=n;i++)
   for (j=1;j<=m;j++)
    { 
      max1=0;
      for (k=0;k<=j;k++)
       if (f[i-1][k]+value[i][j-k]>max1)
          max1=f[i-1][k]+value[i][j-k];
      f[i][j]=max1; 
    } 
  
cout<<f[n][m]<<endl;                         //输出最大盈利值
  show(n,m);                                   //输出分配情况
}
int show(int i,int j)                          //输出各分公司分配情况
{
  int k;
  if (i==0) return 0;
  for (k=0;k<=j;k++)
   if (max1==f[i-1][k]+value[i][j-k])          //递归求各公司分配的机器数量
     {
       max1=f[i-1][k];
       show(i-1,k);
       cout<<i<<" "<<j-k<<endl;
       break;
     }
}


```

## **背包问题**

### **一、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件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”，此时能获得的最大价值就是`f [i-1][v-w[i]`]再加上通过放入第i件物品获得的价值c[i]。** 

　　      **注意`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][0..V]`的所有值。那么，如果只用一个数组f [0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态`f[i][v]`呢？`f[i][v]是由f[i-1][v]`和`f[i-1][v-w[i]]`两个子问题递推而来，能否保证在推`f[i][v]`时（也即在第i次主循环中推f[v]时）能够得到`f[i-1][v]和f[i-1][v-w[i]]`的值呢？事实上，这要求在每次主循环中我们以v=V..0的逆序推f[v]，这样才能保证推f[v]时f[v-w[i]]保存的是状态`f[i-1][v-w[i]]`的值。

伪代码如下：

``` c
　　for i=1..N 
　　　for v=V..0 
　　　　　f[v]=max{f[v],f[v-w[i]]+c[i]}; 
```

其中f[v]=max{f[v],f[v-w[i]]+c[i]}相当于转移方程`f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}`，

因为现在的f[v-w[i]]就相当于原来的`f[i-1][v-w[i]]`。如果将v的循环顺序从上面的逆序改成顺序的话，

那么则成了`f[i][v]由f[i][v-w[i]]`推知，与本题意不符，但它却是另一个重要的完全背包问题最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。

**【例1】 0/1背包**

**【问题描述】**

​     **一个旅行者有一个最多能用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**

【解法一】设f[i][v]表示前i件物品，总重量不超过v的最优价值，则`f[i][v]=max(f[i-1][v-w[i]]+c[i]，f[i-1][v]) ；f[n][m]`即为最优解,给出程序：

``` c


#include<cstdio>

using namespace std;

const int maxm = 201, maxn = 31;

int m, n;

int w[maxn], c[maxn];

int f[maxn][maxm]; 



int max(int x,int y) { x>y?x:y;}           //求x和y最大值



int main(){

  scanf("%d%d",&m, &n);     //背包容量m和物品数量n

  for (int i = 1; i <= n; i++)     //在初始化循环变量部分，定义一个变量并初始化

   scanf("%d%d",&w[i],&c[i]);  //每个物品的重量和价值

  for (int i = 1; i <= n; i++)     // f[i][v]表示前i件物品，总重量不超过v的最优价值

    for (int v = m; v > 0; v--)

      if (w[i] <= v) f[i][v] = max(f[i-1][v],f[i-1][v-w[i]]+c[i]);

        else f[i][v] = f[i-1][v];

   printf("%d",f[n][m]);      // f[n][m]为最优解

   return 0;

}

　　　使用二维数组存储各子问题时方便，但当maxm较大时，如maxm=2000时不能定义二维数组f，怎么办，其实可以用一维数组。
```

【解法二】本问题的数学模型如下：设 f[v]表示重量不超过v公斤的最大价值， 则f[v]=max{f[v]，f[v-w[i]]+c[i]} ，当v>=w[i]，1<=i<=n 。程序如下：

``` c
#include<cstdio>
using namespace std;

const int maxm = 2001, maxn = 31;
int m, n;
int w[maxn], c[maxn];
int f[maxm]; 
int main(){
    scanf("%d%d",&m, &n);            //背包容量m和物品数量n
    for (int i=1; i <= n; i++)
        scanf("%d%d",&w[i],&c[i]);     //每个物品的重量和价值
   
    for (int i=1; i <= n; i++)             //设f(v)表示重量不超过v公斤的最大价值
        for (int v = m; v >= w[i]; v--)
            if (f[v-w[i]]+c[i]>f[v])
                f[v] = f[v-w[i]]+c[i];
printf("%d",f[m]);                      // f(m)为最优解
return 0;
}
```

  总结:

　　01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。

### 二、完全背包问题

问题:

　　　有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 

**基本思路:**

　　这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，`f[i][v]`表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：`f[i][v]=max{f[i-1][v-k*w[i]]+k*c[i]|0<=k*w[i]<= v}`。

　　将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。

　　这个算法使用一维数组，先看伪代码：

``` c 
　　for i=1..N

　　　for v=0..V

　　　　 f[v]=max{f[v],f[v-w[i]]+c[i]}; 
```

　　你会发现，这个伪代码与01背包问题的伪代码只有v的循环次序不同而已。

为什么这样一改就可行呢？首先想想为什么01背包问题中要按照v=V..0的逆序来循环。

这是因为要保证第i次循环中的状态`f[i][v]`是由状态`f[i-1][v-w[i]]`递推而来。

换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果`f[i-1][v-w[i]]`。

而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果`f[i][v-w[i]]`，所以就可以并且必须采用v= 0..V的顺序循环。这就是这个简单的程序为何成立的道理。

　　这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价地变形成这种形式：`f[i][v]=max{f[i-1][v],f[i][v-w[i]]+c[i]}`，将这个方程用一维数组实现，便得到了上面的伪代码。

【例9-12】、完全背包问题

【问题描述】

　　设有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

【解法一】

　`　设f[i][v]表示前i件物品，总重量不超过v的最优价值，则f[i][v]=max(f[i][v-w[i]]+c[i]，f[i-1][v]) ；f[n][m]即为最优解。`

``` c


【参考程序】

#include<cstdio>

using namespace std;



const int maxm = 201, maxn = 31;

int m, n;

int w[maxn], c[maxn];

int f[maxn][maxm]; 

int main()

{

  scanf("%d%d",&m, &n);      //背包容量m和物品数量n

  for (int i = 1; i <= n; i++) 
    scanf(“%d%d”,&w[i],&c[i]);  //每个物品的重量和价值

  for (int i = 1; i <= n; i++)      //f[i][v]表示前i件物品，总重量不超过v的最优价值

    for (int v = 1; v <= m; v++)

      if (v < w[i]) f[i][v] = f[i-1][v];

      else

　　　　　　　　if (f[i-1][v] > f[i][v-w[i]]+c[i]) f[i][v] = f[i-1][v];

        else f[i][v] = f[i][v-w[i]]+c[i]; 

  printf("max=%d",f[n][m]);     // f[n][m]为最优解

  return 0;

}
```

**【解法二】**

　　**本问题的数学模型如下：**

　　**设 f(v)表示重量不超过v公斤的最大价值， 则 f(v)=max{f(v)，f(v-w[i])+c[i]}** **（v>=w[i] ，1<=i<=n） 。**

``` c
【参考程序】

#include<cstdio>

using namespace std;

const int maxm=2001,maxn=31;

int n,m,v,i;

int c[maxn],w[maxn];

int f[maxm];



int main()

{

  scanf("%d%d",&m,&n);      //背包容量m和物品数量n

  for(i=1;i<=n;i++) 

    scanf("%d%d",&w[i],&c[i]);

  for(i=1;i<=n;i++)

    for(v=w[i];v<=m;v++)     //设 f[v]表示重量不超过v公斤的最大价值

      if(f[v-w[i]]+c[i]>f[v]) f[v]=f[v-w[i]]+c[i];

  printf("max=%d\n",f[m]);      // f[m]为最优解

  return 0;

}
```



**一个简单有效的优化**

　　   完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足w[i]<=w[j]且c[i]>=c[j]，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高的j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。



**转化为01背包问题求解**

　　   既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第i种物品最多选V/w[i]件，于是可以把第i种物品转化为V/w[i]件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。

　　更高效的转化方法是：把第i种物品拆成费用为`w[i]*2^k、价值为c[i]*2^k`的若干件物品，其中k满足w[i]*2^k<V。这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log(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*∑n[i])。`

转化为01背包问题

　　  另一种好想好写的基本方法是转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为∑n[i]的01背包问题，直接求解，复杂度仍然是O(V*∑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]间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..n[i]两段来分别讨论得出，并不难，希望你自己思考尝试一下。

　　  这样就将第i种物品分成了O(logn[i])种物品，将原问题转化为了复杂度为O(V*∑logn[i])的01背包问题，是很大的改进。

**【例3】庆功会**

**【问题描述】**

**为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。**

**【输入格式】**

**第一行二个数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**

``` c
【解法一】朴素算法 
【参考程序】
#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;
} 

【解法二】进行二进制优化，转换为01背包
【参考程序】
#include<cstdio>
int v[10001],w[10001];
int f[6001];
int n,m,n1;
int max(int a,int b){
    return a>b?a:b;                             //这句话等于：if (a>b) return a; else return b;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x,y,s,t=1;
        scanf("%d%d%d",&x,&y,&s);
        while (s>=t) {
            v[++n1]=x*t;                        //相当于n1++;  v[n1]=x*t;
            w[n1]=y*t;
            s-=t;
            t*=2;
        }
        v[++n1]=x*s;
        w[n1]=y*s;                             //把s以2的指数分堆：1，2，4，…，2^(k-1)，s-2^k+1,
    }
 for(int i=1;i<=n1;i++)
        for(int j=m;j>=v[i];j--)
           f[j]=max(f[j],f[j-v[i]]+w[i]); 
    printf("%d\n",f[m]);
    return 0;
}





```

**小结** 
　　       这里我们看到了将一个算法的复杂度由O(V*∑n[i])改进到O(V*∑logn[i])的过程，还知道了存在应用超出NOIP范围的知识的O(VN)算法。希望你特别注意“拆分物品”的思想和方法，自己证明一下它的正确性，并用尽量简洁的程序来实现。 

### 四、混合三种背包问题

问题

　　　如果将01背包、完全背包、多重背包混合起来。也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。应该怎么求解呢？

01背包与完全背包的混合

　　考虑到在01背包和完全背包中最后给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(VN)。

伪代码如下：

``` c
for i=1..N

　if 第i件物品是01背包 

　　for v=V..0 

　　　f[v]=max{f[v],f[v-w[i]]+c[i]}; 

　else if 第i件物品是完全背包 

　　for v=0..V 

　　　f[v]=max{f[v],f[v-w[i]]+c[i]}; 
```

再加上多重背包

　　如果再加上有的物品最多可以取有限次，那么原则上也可以给出O(VN)的解法：遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过NOIP范围的算法的话，用多重背包中将每个这类物品分成O(log n[i])个01背包的物品的方法也已经很优了。

**【例4】混合背包**

**【问题描述】**

**一个旅行者有一个最多能用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 4**

**2 1 0**

**3 3 1**

**4 5 4**

**【样例输出】mix.out**

**11**

**【样例解释】**

**选第一件物品1件和第三件物品2件。** 

``` c

#include<cstdio>
using namespace std;
int m, n;
int w[31], c[31], p[31];
int f[201];

int max(int x,int y) {  return  x>y?x:y; }
int main(){
    scanf("%d%d",&m,&n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d",&w[i],&c[i],&p[i]);
    for (int i = 1; i <= n; i++)
        if (p[i] == 0)  {                                   //完全背包
            for (int j = w[i]; j <= m; j++)
                f[j] = max(f[j], f[j-w[i]]+c[i]);
        }
        else {
            for (int j = 1; j <= p[i]; j++)           //01背包和多重背包
                for (int k = m; k >= w[i]; k--)
                    f[k] = max(f[k],f[k-w[i]]+c[i]);
        }
    printf("%d",f[m]); 
    return 0;
}

```

**小结** 

　　有人说，困难的题目都是由简单的题目叠加而来的。这句话是否是公理暂且存之不论，但它在本讲中已经得到了充分的体现。本来01背包、完全背包、多重背包都不是什么难题，但将它们简单地组合起来以后就得到了这样一道一定能吓倒不少人的题目。但只要基础扎实，领会三种基本背包问题的思想，就可以做到把困难的题目拆分成简单的题目来解决。

### **五、二维费用的背包问题**

**问题**

　　　**二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价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】潜水员**

**【问题描述】**

  **潜水员为了潜水要使用特殊的装备。他有一个带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个气缸里的氧和氮的容量及汽缸重量。**

**【输出格式】**

 **仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。**

``` c
【参考程序】
#include<cstdio>
#include<cstring>                                   //初始化memset要用到
using namespace std;
int v, u, k;
int a[1001], b[1001], c[1001];
int f[101][101];

int main(){
    memset(f,127,sizeof(f));                    //初始化为一个很大的正整数
    f[0][0] = 0;
    scanf("%d%d%d",&v,&u,&k);
    for (int i = 1; i <= k; i++)
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
    for (int i = 1; i <= k; i++)
      for (int j = v; j >= 0; j--)
        for (int l = u; l >= 0; l--)
        {
           int t1 = j+ a[i],t2 = l + b[i];
           if (t1 > v)  t1 = v;                        //若氮、氧含量超过需求，可直接用需求量代换，
           if (t2> u)  t2 = u;                        //不影响最优解
           if (f[t1][t2] > f[j][l] + c[i])  f[t1][t2] = f[j][l] + c[i];
        }
    printf("%d",f[v][u]);
    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组}。

使用一维数组的伪代码如下：

``` c
for 所有的组k

  for v=V..0

​    for 所有的i属于组k

　　　　　　f[v]=max{f[v],f[v-w[i]]+c[i]}


```



　　注意这里的三层循环的顺序，“for v=V..0”这一层循环必须在“for 所有的i属于组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**

``` c
【参考程序】
#include<cstdio>
using namespace std;
int v, n, t;
int w[31], c[31];
int a[11][32], f[201];
int main(){
    scanf("%d%d%d",&v,&n,&t);
    for (int i = 1; i <= n; i++){
　　 int p;
        scanf("%d%d%d",&w[i],&c[i],&p);
        a[p][++a[p][0]] = i;
    }
    for (int k = 1; k <= t; k++)
        for (int j = v; j >= 0; j--)
            for (int i = 1; i <= a[k][0]; i++)
                if (j >= w[a[k][i]]) {
                    int tmp = a[k][i];
                    if (f[j] < f[j-w[tmp]]+c[tmp])
                        f[j] = f[j-w[tmp]]+c[tmp]; 
                }
    printf("%d",f[v]);
    return 0;
}

```

**小结**
       分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题。 

### **七、有依赖的背包问题**

**简化的问题** 

​    **这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。**

**算法**

​    **这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。**

​    **按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策略。（事实上，设有n个附件，则策略有2^n+1个，为指数级。）** 

​    **考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个主件和它的附件集合实际上对应于分组的背包中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。**

​    **再考虑分组的背包中的一句话： 可以对每组中的物品应用完全背包中“一个简单有效的优化”。这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，我们可以对主件i的“附件集合”先进行**

   **一次01背包，得到费用依次为0..V-w[i]所有这些值时相应的最大价值f'[0..V-w[i]]。那么这个主件及它的附件集合相当于V-w[i]+1个物品的物品组，其中费用为w[i]+k的物品的价值为f'[k]+c[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件i转化为 V-w[i]+1个物品的物品组，就可以直接应用分组的背包的算法解决问题了。** 

​    **更一般的问题是：依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。**

​    **解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01 背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。**

​    **事实上，这是一种树形DP，其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完P08后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。**

**小结**

​    NOIP2006的那道背包问题，通过引入“物品组”和“依赖”的概念可以加深对这题的理解，还可以解决它的推广问题。用物品组的思想考虑那题中极其特殊的依赖关系：物品不能既作主件又作附件，每个主件最多有两个附件，可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组，这便揭示了问题的某种本质。

### **八、背包问题的方案总数**

对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。

对于这类改变问法的问题，一般只需将状态转移方程中的max改成sum即可。例如若每件物品均是01背包中的物品，转移方程即为`f[i][v]=sum{f[i-1][v],f[i-1][v-w[i]]+c[i]}，初始条件f[0][0]=1。`

事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。

【例9-17】、货币系统

【问题描述】

　　给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。样例：设n=3，m=10，要求输入和输出的格式如下：

【样例输入】money.in

3 10                //3种面值组成面值为10的方案

1                   //面值1

2                   //面值2

5                   //面值5

【样例输出】money.out

　　10               //有10种方案



``` c
【算法分析1】

　　   设f[j]表示面值为j的最大方案数， 如果f[j-k*a[i]]!=0则f[j]=f[j]+f[j-k*a[i]]，当1<=i<=n，m>=j>= a[i]，1<=k<=j / a[i]。
    
#include<cstdio>
int m, n;
int a[1001];
long long f[10001];                     //注意要用long long 

int main()
{
    scanf("%d%d",&n,&m);              //n种面值的货币，组成面值为m
    for (int i = 1; i <= n; i++)
       scanf("%d",&a[i]);               //输入每一种面值
    f[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= a[i]; j--)         //f[j]表示面值为j的总方案数
            for (int k = 1; k <= j / a[i]; k++)
                f[j] += f[j-k*a[i]];
    printf("%I64d",f[m]);                 // f[m]为最优解
    return 0;
}

【算法分析2】
    设f[j]表示面值为j的总方案数，如果f[j-a[i]]!=0则f[j]=f[j]+f[j-a[i]],1<=i<=n,a[i]<=j<=m。
【参考程序2】
#include<cstdio>
using namespace std;

int n, m;
int a[101];
long long f[10001];            

int main(){
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i++)
       scanf("%d",&a[i]);
    f[0] = 1;
    for (int i = 1; i <= n; i++)
       for (int j = a[i]; j <= m; j++)
          f[j] += f[j-a[i]];
    printf("%I64d",f[m]);
    return 0;
}

```

小结:

显然，这里不可能穷尽背包类动态规划问题所有的问法。甚至还存在一类将背包类动态规划问题与其它领域（例如数论、图论）结合起来的问题，在这篇论背包问题的专文中也不会论及。但只要深刻领会前述所有类别的背包问题的思路和状态转移方程，遇到其它的变形问法，只要题目难度还属于NOIP，应该也不难想出算法。

触类旁通、举一反三，应该也是一个OIer应有的品质吧。