01 关于knapsack问题的动态编程算法和回溯算法的比较研究
摘 要: 本文介绍了01背包问题和动态规划已经回溯两种算法。并使用两种方法对01背包问题进行求解。
关键词: 背包问题; 动态规划算法；回溯算法
目录
1 引言
2 动态规划算法
2.1 动态规划算法思想介绍
2.2 动态规划算法求解的基本步骤
2.2.1 确定状态表示
2.2.2写状态转移方程
2.2.3 初始化状态表
2.2.4 确定状态表的填写顺序
2.2.5确定返回值
2.3 算法设计
2.4算法实现
2.5 案例分析
3.回溯算法
3.1回溯算法思想介绍
3.2回溯算法解题步骤
3.3 算法设计
3.4 算法实现
3.5 案例分析
4 实验对比
5 总 结
1 引言
背包问题是一个经典的动态规划模型，很多关于算法的 教材都把它作为一道例题，该问题既简单又容易理解，而且 在某种程度上还能够揭示动态规划的本质。 将具有不同重量和价值的物体装入一个有固定载重量的 背包，以获取最大价值，这类问题被称为背包问题。 背包问题可以扩展出很多种问题，而0l背包问题是最常见、最有代表性的背包问题。[1]
对01背包问题的描述：
o-l背包问题：给定n种物品和一背包。物品i的重量是Wi．其价 值为Vi，背包的容量为C。问应如何选择装入背包中物品，使得装入背 包中物品的总价值最大?
先给出一个实例01背包问题：假设N=3（有三件物品），三个物品的重量为{20，15，10}，三个物品的价值为{20，30，25}，对于一个最大承重为25的背包，求包中物品的组合最大的价值是多少？下面分别以动态规划法和回溯法来解决这个实例。
2 动态规划算法
2.1 动态规划算法思想介绍
动态规划算法通常用于求解具有某种最优性质的问题遥在这类问 题中袁可能会有许多可行解遥每一个解都对应于一个值袁我们希望找到具有最优值的解遥动态规划算法与分治法类似袁其基本思想也是将待 求解问题分解成若干个子问题袁先求解子问题袁然后从这些子问题的 解得到原问题的解遥 与分治法不同的是袁适合于用动态规划求解的问 题袁经分解得到子问题往往不是互相独立的遥 若用分治法来解这类问 题袁则分解得到的子问题数目太多袁有些子问题被重复计算了很多次遥 如果我们能够保存已解决的子问题的答案袁而在需要时再找出已求得 的答案袁这样就可以避免大量的重复计算袁节省时间遥我们可以用一个 表来记录所有已解的子问题的答案遥 不管该子问题以后是否被用到袁 只要它被计算过袁就将其结果填入表中遥 这就是动态规划法的基本思 路遥 具体的动态规划算法多种多样袁但它们具有相同的填表格式。 [2]
2.2 动态规划算法求解的基本步骤
2.2.1 确定状态表示
动态规划方法解题一般会先创建一个dp表，一般是一维或者二维数组。然后将状态表填写完整，我们要的结果一般就是dp表中的某一个值。而我们的dp表的每一个值含义实际上都是一个状态表示。dp表的状态表示一般可以由题目条件得出，最多的情况是抽象的“经验”得出。然后就是在分析问题的过程中，发现了重复的子问题，将子问题抽象为一个状态表示。
2.2.2写状态转移方程
状态转移方程就是状态表示等于一个式子，并可以用之前的状态来表示。给出的状态转移方程是一个递推式袁需要一个递推的终止条件或 边界条件遥 一般袁只要解决问题的阶段尧状态和状态转移决策确定了袁就可以 写出状态转移方程渊包括边界条件冤遥实际应用中可以按以下几个简化 的步骤进行设计院 渊员冤分析最优解的性质袁并刻画其结构特征遥 渊圆冤递归的定义最优解遥 渊猿冤以自底向上或自顶向下的记忆化方式渊备忘录法冤计算出最优 值遥 渊源冤根据计算最优值时得到的信息袁构造问题的最优解
2.2.3 初始化状态表
填表是根据状态转移方程来填表，保证填表的时候不越界，
2.2.4 确定状态表的填写顺序
为了保证填写当前状态的时候，所需要的状态已经被计算过了，要确定填表的顺序。
2.2.5确定返回值
结合题目要求加状态表示得出最终答案
2.3 算法设计
对于一个物品来说只有两种状态就是放入背包或者不放入背包。那么确定这个题目的状态表示为：optp[i][j],i表示第几个物品，j表示当前背包的最大容量，状态表示的含义是：从前i个物品中挑选，总体积不超过j,所有选择中可以挑选出来的最大值。接着根据问题写出状态转移方程，我们从最后一个物品考虑，最后一个物品只有两种状态，放入或者不放入。第一种情况，当最后一个物品不放入背包，那么也就是意味着我们需要在前i-1个物品中进行选择，但是总体积不超过j.这种情况的状态转移方程为：optp[i][j] = opto[i-1][j]。第二种情况，最后一个物品放入，那么可以确定的是这最后一个物品是必然要放入的，那么就已经确定了最后一个物品的价值一定要纳入计算，并且我们需要在那么我们依旧从剩下的x-1个物品中挑选最大价值方案即可。但是此时往前i-1个物品中选择最大价值方案时，体积不是j，因为最后一个物品必须选，所以剩余体积为：j-Vi，因为要排除掉最后一个物品的体积，也就是选择的时候，要保证当前背包一定要留有最后一个物品的容量，也就是说这种情况还需要满足：j-Vi>=0.所以这种情况的状态转移方程为：
optp[i][j]= Wi+ optp[i-1][j-Vi](j>Vi).
由于要取最大的值，分两种情况，所以就取两种情况的最大值就是我们需要的结果：
Max(optp[i][j]=optp[i-1][j],optp[i][j]=Wi+optp[i-1][j-Vi](j>Vi).)但是值得注意的是第二种情况可能不存在。然后初始化一下dp状态表，防止填表越界。由于我们的dp[x][y]的值由optp[x-1][y]和dp[x-1][y-Vx]两个位置的状态值确定，两点在d[x][y]的上方或者忧伤，所以填表顺序从上往下填写。最后由题意可知数组的最后一个元素：optp[n][V]就是要求的答案输出即可。
2.4算法实现
void Dp(int n ,int V,int v[],int w[])
{
int dp[1000][1000] = { 0 };
//初始化状态表
int x = 1;
for (x = 1; x <= n; x++)
{
int y = 1;
for (y = 1; y <= V; y++)
{
//用容积来控制确定要放入背包的物体
dp[x][y] = dp[x - 1][y];
//情况1，第x个物品不选
if (y >= v[x])
{
int a = dp[x][y];
int b = dp[x - 1][y - v[x]] + w[x];
//情况2.第x个物品要选择
dp[x][y] = max(a, b);//取两种情况的最大值放入状态表中
}
}
}
//dp[n][v]就是要求的值
printf("总价值最大为：%d\n", dp[n][V]);
}2.5 案例分析
案例分析 现有载重量为10的背包，有四个物体A、B、C、D，其重 量分别为4、2、5、3，价值分别为4、3、5、8，要求放入物 体使背包所获价值最大。 用optp[i][j]来存储这四个物体在不同载重量的背包下 所获的价值，计算过程如下表所示：
相应的，对于optp[i][J]，物体的放入情况及重量如下 表所示：
2.6 算法复杂度
该算法中，二维数组dp的大小为n*V，物体的重量、价值和解向量大小都等于物体个数n，相当于额外开辟了一个dp数组由于保存状态，这是使用其他算法不会消耗的空间，故该算法的空间复杂度为0(nV)。由于算法为了初始化，其次判断每个物品的状态并计算，使用了两层循环，基本语句的执行次数为两层循环次数相乘，所以整个算法的时间复杂度为 0(nV)。
3.回溯算法
3.1回溯算法思想介绍
回溯算法是搜索算法中的一种控制策略 。它在包含 问题的所有解的解空间树中，按照深度优先的策略，从 根结点出发搜索解空间树。算法搜索至解空间树的任一 结点时，总是先判断该结点是否肯定不包含问题的解 ， 如果肯定不包含，则跳过对 以该结点为根的子树的系统 搜索，逐层 向其祖先结点回溯。否则进入该子树，继续 按深度优先的策略进行搜索 。回溯算法在用来求问题的 所有解时，要回溯到根，且根结点的所有子树都已被搜 索遍才结束。回溯算法在用来求 问题的任一解时，只要 搜索到问题的一个解就可以结束 。这种以深度优先的方 式系统地搜索问题的解的算法称为回溯算法 。[3]
3.2回溯算法解题步骤
（1）针对所给问题定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3） 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免 无效的搜索。
3.3 算法设计
对于每种物品我们有两种选择，放或者不放。对于每一个物品我们都要这样考虑。对物品分别进行编号，初始情况背包是空的，我们需要考虑每个物品的每种情况，当我们对于每一种物品我们都考虑过了，也就是找到了一种基本的情况，此时可以计算当前背包里面的总价值了。然后回溯：每次找出一种满足条件的基本情况就进行一次回溯，找到最后放入包中的物品并将其取出，接着考虑是否放入编号在这个物品之后的第一个物品。然后当考虑完所有物品的放入情况得到一个解。并将两个解进行比较，保留最大的值。这样我们就可以得到一颗决策树，树的第i层表示第i个物品的放入情况：
剪枝函数为：当前背包容量+即将放入的物品的体积<背包总体积
3.4 算法实现
void Back(int i,int n,double c,int *cnt,double max[],double *Bvalue,double *Bweight,double w[],double v[])
{
if (i > n)//到了最后一个
{
max[*cnt] = *Bvalue;
*cnt++;
if (*cnt > 1)//比较得出最大值
{
double temp = 0.0;
if (max[*cnt - 2] > max[*cnt - 1])
{
temp = max[*cnt - 1];
max[*cnt - 1] = max[*cnt - 2];
max[*cnt - 2] = temp;
}
}
else
{
double tem = 0.0;
if (max[0] > max[1])
{
tem = max[1];
max[1] = max[0];
max[0] = tem;
}
}
return;
}
if (*Bweight + v[i] <= c)
{
*Bweight += v[i];//计算可以放的情况的背包质量和价值
*Bvalue += w[i];
Back(i +1,n,c,cnt,max,Bvalue,Bweight,w,v);
*Bweight -= v[i];
*Bvalue -= w[i];
}
//不可以放的情况
Back(i + 1, n, c, cnt, max, Bvalue, Bweight, w, v);
}3.5 案例分析
首先从1号物品开始，一号物品放入，然后看二号物品可不可以放入，二号物品放入时容量超出背包容量不满足，发生剪枝，然后二号不放，看三号物品是否放入，放入的话超过背包容积，所以不放入，得到第一种解，只放入一号物品，此时最大价值为25.然后回溯到一号物品状态选择，一号选择不放入，看二号状态，选择放入，满足条件，再看三号是否放入，满足条件得到一种可行解，此时只放入二号和三号物品，价值为55.然后回溯到3号不放入，满足条件，得到一种解，此时只放入二号，解为30.然后回溯到二号物品选择状态，选择不放入，然后看三号物品状态选择，选择放入，满足条件，得到一个解，此时只放入三号物品。解为25.然后回溯到三号物品状态选择。选择不放入，得到一个解，此时三个都不放入。价值为0.如下图所示
3.6 算法复杂度
算法的时间复杂度为0(n·2^n)为n物品个数。算法递归的最大层数为n层，其次调用算法额外开辟了一个保存结果的数组max，这个是常数级别，所以空间复杂度为o(n),n为物品个数。
4 实验对比
将回溯算法与动态规划算法放入一个案例下面进行测算。
double begin1 = clock();
Back(1, n,c,v,w,&Bweight,&Bvalue);
printf("Back函数测算最大价值为：%d\n", max[cnt - 1]);
double end1 = clock();
double begin2 = clock();
Dp(n, c, v, w);
double end2 = clock();
printf("Back:%lf\n", end1 - begin1);
printf("Dp:%lf\n", end2 - begin2);来比较运行时间的长短：
5 总 结
动态规划算法求解背包问题时对子过程用枚举法求解，而且约束条件越多，决策的搜索范围越小。求解也越容易。但是对于规模较大的问题它并不是一个理想的算法。计算和存储量的需要对于状态空间和决策空间的维数的增长争指数增长关系。此时计算时间和存储量过大。
回溯法：回溯法需要为问题定义一个解空间。这个解空间必须至少包含问题的一个解。使用递归回溯法解决背包问题的优点在于它算法思想简单。而且它能完全遍历搜索空间．肯定能找到问题的最优解。
但是由于背包问题解的总组合数有2n个，因此，随着物件数n的增大，其解的空间将以2n级增长。相对动态规划算法，回溯法不需要二维数组的存储空间。但是在回溯过程中递归栈会越来越大。
因此虽然用这两种方法都能得到问题的最优解。但是当背包问题的规模较大时二者的计算时间较多和存储量较大。因此都不是解规模较大的背包问题的最优算法。[4]
参考文献:
- 刘继,夏定纯. 用动态规划法与回溯法实现0-1背包问题的比较[J]. 科技信息,2010(19):462. DOI:10.3969/j.issn.1001-9960.2010.19.346.邱宁. 汉诺塔问题的非递归算法分析[J].浙江树人大学学报，2005.5(02)：117-118.
- 张莹. 动态规划算法综述[J]. 科技视界,2014(28):126-126,158. DOI:10.3969/j.issn.2095-2457.2014.28.094.
- 王凤红. 回溯算法[J]. 中国现代教育装备,2011(14):88-90. DOI:10.3969/j.issn.1672-1438.2011.14.046.
- 刘继,夏定纯. 用动态规划法与回溯法实现0-1背包问题的比较[J]. 科技信息,2010(19):462. DOI:10.3969/j.issn.1001-9960.2010.19.346.邱宁. 汉诺塔问题的非递归算法分析[J].浙江树人大学学报，2005.5(02)：117-118.
附录：源码
#include<stdio.h>
#include<time.h>
#include<Windows.h>
#define N 100
int dp[N][N] = { 0 };//定义动态规划算法的状态表
int optp[N] = { 0 };
int Max(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
int max[100] = { 0 };//保存回溯算法最后的结果
int cnt = 0;//用作保存结果的下标
void Back(int i, int n, int c, int* v, int* w, int* Bweight, int* Bvalue)
{
if (i > n)//到了最后一个
{
max[cnt] = *Bvalue;
cnt++;
if (cnt > 1)
{
int temp = 0;
if (max[cnt - 2] > max[cnt - 1])
{
temp = max[cnt - 1];
max[cnt - 1] = max[cnt - 2];
max[cnt - 2] = temp;
}
}
else
{
int tem = 0;
if (max[0] > max[1])
{
tem = max[1];
max[1] = max[0];
max[0] = tem;
}
}
return;
}
if (*Bweight + v[i] <= c)
{
*Bweight += v[i];//计算可以放的情况的背包质量和价值
*Bvalue += w[i];
Back(i + 1,n,c,v,w,Bweight,Bvalue);
*Bweight -= v[i];
*Bvalue -= w[i];
}
//不可以放的情况
Back(i + 1, n,c,v,w,Bweight,Bvalue);
//
}
//优化3
void Dp3(int n, int V, int* v, int* w)
{
//dp表已经初始化
//开始填表
int i = 1;
for (i = 1; i <= n; i++)
{
int j = 1;
for (j = V; j >=v[i]; j--)//修改遍历顺序
{
int a = optp[j];
int b = optp[j - v[i] ]+ w[i];
optp[j] = Max(a, b);
}
}
printf("Dp函数测算总价值最大为：%d\n", optp[V]);
}
//优化2
void Dp2(int n, int V, int* v, int* w)
{
//dp表已经初始化
//开始填表
int i = 1;
int temp[N] = { 0 };
for (i = 1; i <= n; i++)
{
int j = 1;
for (j = 1; j <=V; j++)
{
int a = temp[j];
if (j >=v[i])
{
int b = temp[j - v[i]] + w[i];
optp[j] = Max(a, b);
}
}
memcpy(temp, optp, sizeof(temp));
}
printf("Dp函数测算总价值最大为：%d\n", temp[V]);
}
//优化1
void Dp1(int n,int V,int * v,int * w)
{
//dp表已经初始化
//开始填表
int x = 1;
for (x = 1; x <= n; x++)
{
int y = 1;
for (y = 1; y <= V; y++)//
{
dp[x][y] = dp[x - 1][y];
if (y >= v[x])
{
int a = dp[x][y];
int b = dp[x - 1][y - v[x]] + w[x];
dp[x][y] = Max(a, b);
}
}
}
printf("Dp函数测算总价值最大为：%d\n", dp[n][V]);
}
int main()
{
int n = 0;//当前物品个数
int c = 0;//当前背包容量
printf("请输入物品个数>:");
scanf("%d", &n);
printf("请输入背包容量>:");
scanf("%d", &c);
int w[100] = { 0};//表示物品的价值数组
printf("请依次输入物品的重量或者体积>:\n");
int i = 0;
int v[100] = { 0 };//表示物品的体积或者重量数组
for (i = 1; i <= n; i++)
{
scanf("%d", &v[i]);
}
printf("请依次输入每个物品的价值：》\n");
for (i = 1; i <= n; i++)
{
scanf("%d", &w[i]);
}
int Bweight = 0;//表示当前背包容量
int Bvalue = 0;//表示当前背包价值
double begin1 = clock();
Back(1, n,c,v,w,&Bweight,&Bvalue);
Sleep(1);
("Back函数测算最大价值为：%d\n", max[cnt - 1]);//保留解法
double end1 = clock();
double begin2 = clock();
//Sleep(1);
Dp1(n, c, v, w);//dp数组
double end2 = clock();
double begin3 = clock();
Dp2(n, c, v, w);//两个一维数组
double end3 = clock();
double begin4 = clock();
Dp3(n, c, v, w);//一个一维数组
double end4 = clock();
//printf("Back:%lf\n", end1 - begin1);
printf("Dp1:%lf\n", end2 - begin2);
printf("Dp2:%lf\n", end3 - begin3);
printf("Dp3:%lf\n", end4 - begin4);
return 0;
}