目录
动态规划算法
算法介绍与思想
例子理解：斐波那契数
背包问题
问题介绍
算法思路
时间效率分析
代码实现
正文
动态规划算法
算法介绍与思想
动态规划(dynamic programming)是一种算法设计技术，它有着相当有趣的历史。作为一种使多阶段决策过程最优的通用方法，它是在20世纪50年代由一位卓越的美国数学家理查德·贝尔曼(Richard Bellman)发明的。因此，这个技术名字中的“programming”是计划和规划的意思，不是代表计算机中的编程。它不仅是应用数学中用来解决某类最优问题的重要工具，而且还在计算机领域中被当作一种通用的算法设计技术来使用。在这里，我们正是从这个角度来考虑这种技术的。
如果问题是由交叠的子问题构成的，我们就可以用动态规划技术来解决它。一般来说，这样的子问题出现在对给定问题求解的递推关系中，这个递推关系中包含了相同类型的更小子问题的解。动态规划法建议，与其对交叠的子问题一次又一次地求解，还不如对每个较小的子问题只求解一次并把结果记在表中，这样就可以从表中得出原始问题的解。
例子理解：斐波那契数
斐波那契数。我们可以发现它对这项技术做出了很好的阐述。斐波那契数是以下序列中的元素:
1 ，1 ，2 ，3 ，5 ，8 ，13 ，21 ，34 ，...... ，
它可以用一个简单的递推式和两个初始条件来定义:
如果我们试图利用第一个递推式直接计算第n个斐波那契数F(n)，可能必须对该函数的相同值重新计算好几遍。请注意，计算Fn)这个问题是以计算它的两个更小的交叠子问题F(n-1)和F(n -2)的形式来表达的。所以，我们可以简单地在一张一维表中填入n+1个Fn)的连续值。开始时，通过观察初始条件第二个递推式可以填入0和l，然后以式第一个递推式作为运算规则计算出其他所有的元素。显然，该数组的最后一个元素应该包含F(n)。这个非常简单的算法只需要一个单循环就能完成。
请注意，实际上，如果只存储斐波那契序列中最后两个元素的值，就可以避免使用额外的数组来完成这个任务。这种现象并不罕见，而且我们会在本章中遇到更多这样的例子。虽然动态规划法的直接应用也可以解释成一种特殊类型的空间换时间权衡技术，但有时候一个动态规划算法经过改进可以避免使用额外的空间。
某些算法无需计算出该序列前面所有的元素就可以给出第n个斐波那契数的值。然而，一般来说，一个算法如果基于经典的从底至上动态规划方法，那就需要解出给定问题的所有较小子问题。动态规划法的一个变化形式试图避免对不必要的子问题求解。
但无论我们使用动态规划的经典的从底至上版本还是它基于记忆功能的从顶至下版本，设计这样一种算法的关键步骤还是相同的，即导出一个问题实例的递推关系，该递推关系包含该问题的更小(并且是交叠的)子实例的解。但像计算第n个斐波那契数这样，直接表现为公式第一个递推式的形式，可以说是这个规则的一个极少例外。
由于动态规划的大多数应用都是求解最优化问题，因此我们需要指出这类应用中的一个一般性法则。理查德·贝尔曼称其为最优化法则(principle of optimality)。该法则认为最优化问题任一实例的最优解，都是由其子实例的最优解构成的。最优化法则在大多数情况下是成立的，尽管也有少数情况例外(一个相当罕见的例子，就是在图中找最长简单路径)。虽然在应用动态规划求解具体问题时，需要检查最优化法则是否适用，但在设计动态规划算法时，做一个这样的检查并不困难。
背包问题
问题介绍
背包问题是一种组合优化的NP完全问题1..也就是说，没有多项式时间复杂度的解法。背包问题的基本形式是:给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，我们如何选择，才能使得物品的总价值最高。
根据物品是否可以重复选择，背包问题可以分为以下几种类型：
01背包问题：每种物品只有一个，可以选择放或不放。
完全背包问题：每种物品有无限个，可以任意选择放或不放。
多重背包问题：每种物品有有限个，可以选择放或不放。
此外，还有—些其他的变形，例如恰好装满、求方案总数、求所有的方案等。
算法思路
我们用设计一个背包问题的动态规划算法来作为本节的开始:给定n个重量为w1，…"，wn,价值为v1，…, vn的物品和一个承重量为W的背包,求这些物品中最有价值的一个子集，并且要能够装到背包中。在这里假设所有的重量和背包的承重量都是正整数，而物品的数量不必是整数。
为了设计一个动态规划算法，需要推导出一个递推关系，用较小子实例的解的形式来表示背包问题的实例的解。让我们来考虑一个由前i个物品(1≤i≤n )定义的实例，物品的重量分别为w1，…, wi，价值分别为v1，…, vi，背包的承重量为j(1≤j≤W)。设F(i,j)为该实例的最优解的物品总价值，也就是说，是能够放进承重量为j的背包中的前i个物品中最有价值子集的总价值。可以把前i个物品中能够放进承重量为j的背包中的子集分成两个类别:包括第 i个物品的子集和不包括第i个物品的子集。然后有下面的结论:
(1)根据定义，在不包括第i个物品的子集中，最优子集的价值是F(i-1,j)。
(2)在包括第i个物品的子集中(因此，j-wi≥0)，最优子集是由该物品和前i-1个物品中能够放进承重量为j- w;的背包的最优子集组成。这种最优子集的总价值等于vi+F(i- 1,j - wi)。
因此，在前i个物品中最优解的总价值等于这两个价值中的较大值。当然，如果第i个物品不能放进背包,从前i个物品中选出的最优子集的总价值等于从前i-1个物品中选出的最优子集的总价值。这个结果导致了下面这个递推式:
我们可以很容易地如下定义初始条件:
当j≥0时，F(0,j)= 0;当i≥0时，F(i, 0)=0
我们的目标是求F(n, W)，即n个给定物品中能够放进承重量为W的背包的子集的最大总价值以及最优子集本身。
下图给出了涉及公式上面的递推式和公式初始条件的物品总价值。当i, j >0时，为了计算第i行第j列的单元格F(i,j)，我们拿前一行同一列的单元格与vi加上前一行左边wi列的单元格的和做比较，计算出两者的较大值。这个表格既可以逐行填，也可以逐列填。
时间效率分析
该算法的时间效率和空间效率都属于0(nW)。用来求最优解的具体组成的时间效率属于O(n)。
代码实现
#include <stdio.h> #define max(a,b) ((a)>(b)?(a):(b)) // n: 物品个数 // w: 物品重量数组 // v: 物品价值数组 // C: 背包容量 // 返回: 最大总价值 int knapsack(int n, int w[], int v[], int C) { // dp[j] 表示容量为j的背包的最大价值 int dp[C+1]; // 初始化边界条件 for (int j = 0; j <= C; j++) { dp[j] = 0; // 没有物品可选，价值为0 } // 状态转移方程 for (int i = 1; i <= n; i++) { for (int j = C; j >= w[i-1]; j--) { // 倒序遍历，避免覆盖之前的状态 // 在放入和不放入第i个物品中选择最大价值 dp[j] = max(dp[j], dp[j-w[i-1]] + v[i-1]); } } // 返回最终结果 return dp[C]; } int main() { // 测试数据 int n = 4; int w[] = {2,3,4,5}; //测试用例 int v[] = {3,4,5,6}; int C = 8; // 调用函数 int ans = knapsack(n,w,v,C); // 输出结果 printf("The maximum value is %d\n", ans); return 0; }
