摘 要: 本文介绍了01背包问题及使用动态规划算法进行解决该问题。并对该算法方法对01背包问题进行求解的过程进行算法改进，减少算法的空间复杂度。
关键词: 背包问题; 动态规划算法；算法改进
背包问题是一个经典的动态规划模型，很多关于算法的 教材都把它作为一道例题，该问题既简单又容易理解，而且 在某种程度上还能够揭示动态规划的本质。 将具有不同重量和价值的物体装入一个有固定载重量的 背包，以获取最大价值，这类问题被称为背包问题。背包问题可以扩展出很多种问题，而0l背包问题是最常见、最有代表性的背包问题。[1]
对01背包问题的描述：
0-l背包问题：给定n种物品和一背包。物品i的重量是Wi．其价 值为Vi，背包的容量为C。问应如何选择装入背包中物品，使得装入背 包中物品的总价值最大?
先给出一个实例01背包问题：假设N=3（有三件物品），三个物品的重量为{20，15，10}，三个物品的价值为{20，30，25}，对于一个最大承重为25的背包，求包中物品的组合最大的价值是多少？
动态规划算法通常用于求解具有某种最优性质的问题遥在这类问 题中可能会有许多可行解遥每一个解都对应于一个值我们希望找到具有最优值的解遥动态规划算法与分治法类似其基本思想也是将待 求解问题分解成若干个子问题先求解子问题然后从这些子问题的解得到原问题的解遥与分治法不同的是适合于用动态规划求解的问 题经分解得到子问题往往不是互相的遥若用分治法来解这类问题则分解得到的子问题数目太多有些子问题被重复计算了很多次遥如果我们能够保存已解决的子问题的答案而在需要时再找出已求得的答案这样就可以避免大量的重复计算节省时间遥我们可以用一个表来记录所有已解的子问题的答案，不管该子问题以后是否被用到,只要它被计算过就将其结果填入表中,这就是动态规划法的基本思路,具体的动态规划算法多种多样,但它们具有相同的填表格式。 [2]
动态规划方法解题一般会先创建一个dp表，一般是一维或者二维数组。然后将状态表填写完整，我们要的结果一般就是dp表中的某一个值。而我们的dp表的每一个值含义实际上都是一个状态表示。dp表的状态表示一般可以由题目条件得出，最多的情况是抽象的“经验”得出。然后就是在分析问题的过程中，发现了重复的子问题，将子问题抽象为一个状态表示。
状态转移方程就是状态表示等于一个式子，并可以用之前的状态来表示。给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件, 一般只要解决问题的阶段状态和状态转移决策确定了就可以 写出状态转移方程包括边界条件.实际应用中可以按以下几个简化的步骤进行设计,分析最优解的性质并刻画其结构特征递归的定义最优解,以自底向上或自顶向下的记忆化方式计算出最优值遥,根据计算最优值时得到的信息构造问题的最优解
填表是根据状态转移方程来填表，保证填表的时候不越界，
为了保证填写当前状态的时候，所需要的状态已经被计算过了，要确定填表的顺序。
结合题目要求加状态表示得出最终答案
对于一个物品来说只有两种状态就是放入背包或者不放入背包。那么确定这个题目的状态表示为：optp[i][j],i表示第几个物品，j表示当前背包的最大容量，状态表示的含义是：从前i个物品中挑选，总体积不超过j,所有选择中可以挑选出来的最大值。接着根据问题写出状态转移方程，我们从最后一个物品考虑，最后一个物品只有两种状态，放入或者不放入。第一种情况，当最后一个物品不放入背包，那么也就是意味着我们需要在前i-1个物品中进行选择，但是总体积不超过j.这种情况的状态转移方程为：optp[i][j] = opto[i-1][j]。第二种情况，最后一个物品放入，那么可以确定的是这最后一个物品是必然要放入的，那么就已经确定了最后一个物品的价值一定要纳入计算，并且我们需要在那么我们依旧从剩下的i-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[i][j]的值由optp[i-1][j]和dp[i-1][j-Vi]两个位置的状态值确定，两点在d[x][y]的上方或者忧伤，所以填表顺序从上往下填写。最后由题意可知数组的最后一个元素：optp[n][V]就是要求的答案输出即可。
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]);
}案例分析 现有载重量为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)。
在上述算法中，时间复杂度不能再继续优化了，但是空 间复杂度是可以继续优化的。对应上述算法中描述的状态表来说，为了兼顾物品的数目和背包的体积的问题，所以定义一一个二维数组。数组中每一个位置都保存的是当前状态下的最优解。但是不难发现一个问题：每一个位置的数据来源于当前位置上一行的数据。而除了这两行往上的数据空间虽然保存了数据，但是数据没有用，也就意着这部分空间可以被释放掉。使用两个一行数组进行滚动交替就可以进行数据更迭。那么从原先开辟n*v个空间，n表示物品个数，v表示背包容量。变成了v,v表示背包数量。所以在定义两个一位数组，optp[i][j],表示当前i个物品的存放情况，完成后，将optp的数据交给一个temp[i][j]数组保存，此时temp[i][j],保存的就是前i-1个物品的的存放情况。两个数组滚动交替。当要填写optp数组的j位置的值时，如果当前位置不放，状态转移方程为：：optp[i][j] = opto[i-1][j],
其中optp[i-1]就是temp[i][j]数组，也就是当前要填写的数据就保存在temp数组相同的下标内。而当optp的j物品是要选时，那么可以确定的是这最后一个物品是必然要放入的，那么就已经确定了最后一个物品的价值一定要纳入计算，并且我们需要在那么我们依旧从剩下的x-1个物品中挑选最大价值方案即可。但是此时往前i-1个物品中选择最大价值方案时，体积不是j，因为最后一个物品必须选，所以剩余体积为：j-Vi，因为要排除掉最后一个物品的体积，也就是选择的时候，要保证当前背包一定要留有最后一个物品的容量，也就是说这种情况还需要满足：j-Vi>=0.所以这种情况的状态转移方程为：
optp[j]= Wi+ temp[j-Vi](j>Vi).
由于要取最大的值，分两种情况，所以就取两种情况的最大值就是我们需要的结果：
Max(temp[j],optp[i][j]=Wi+temp[j-Vi](j>Vi).)
优化算法主逻辑代码：
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("Dp2函数测算总价值最大为：%d\n", temp[V]);我们发现，实际上述代码还可以进行进一步的空间优化。观察发现，optp[i][j]只 与optp[i-1][j]和optp[i-1][J—weight[i]]有关，与 optp[k][1](k=1，2，……，i一2，i+l，……11，j=l， 2，……，m)无关，故可考虑只用一维数组一optp来存储， 一optp[j]相当于optp[i][j]。而考虑到optp[i][j]是由 optp[i][j]和optp[i—1][j—weight[i]]共同计算得到的， 故该算法中的j循环要从后往前计算，一optp[]的计算算法设 计如下所示：
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);
}
}对优化结果分析：
显然使用一维数组的方式对结果没有影响，所以优化如上。
4 实验对比
double begin1 = clock();
Back(1, n,c,v,w,&Bweight,&Bvalue);
//Sleep(1);
printf("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();动态规划算法求解背包问题时对子过程用枚举法求解，而且约束条件越多，决策的搜索范围越小。求解也越容易。但是对于规模较大的问题它并不是一个理想的算法。计算和存储量的需要对于状态空间和决策空间的维数的增长争指数增长关系。此时计算时间和存储量过大。
但是由于背包问题解的总组合数有2n个，因此，随着物件数n的增大，其解的空间将以2n级增长。算法进行优化过后，空间复杂度变为O(V),V被背包容量，时间复杂度也得到小范围的优化。[4]
参考文献:
补充：完整测试代码
#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;
}
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- fenyunshixun.cn 版权所有 湘ICP备2023022495号-9
违法及侵权请联系：TEL:199 18 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务