最详细动态规划解析——背包问题
大家好，又见面了，我是你们的朋友全栈君。
动态规划的定义
要解决一个复杂的问题，可以考虑先解决其子问题。这便是典型的递归思想，比如最著名的斐波那契数列，讲递归必举的例子。
斐波纳契数列的定义如下：F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*） 用递归可以很快写出这样一个函数，咋一看真牛逼，几行代码就搞定了
int fib(int i)
{
if(i <= 1)
{
return 0;
}
return fib(i - 1) + fib(i - 2);
}将该函数的执行过程用图表示出来，就会发现fib4执行了一次，fib3执行了两次，fib2执行了三次，fib1计算了5次，重复的次数呈现爆发增长，接近与指数级。如果n取得足够大，暂且不说费时的问题，直接就会因为递归次数太多，函数堆栈溢出而程序奔溃。
那么很快就有人想到，用一个数组来保存曾经计算过的数据来避免重复计算。这种思想便是动态规划！ 我们来实现一下
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
int fib(int n, vector<int>& vec);
int main(int argc, char** argv)
{
if(argc != 2)
{
cout << "usage: ./a.out number" << endl;
}
int num = atoi(argv[1]);
vector<int> vec(num + 1, -1);
int ret = fib(num, vec);
cout << "fib(" << argv[1] << ")" << " = " << ret << endl;
return 0;
}
int fib(int n, vector<int>& vec)
{
if(n <= 1)
{
return 1;
}
if(vec[n] == -1)
{
vec[n] = fib(n - 1, vec) + fib(n - 2, vec);
}
return vec[n];
}当然，对于递归问题也可以转化为循环来解决。
#include <iostream>
#include <stdlib.h>
using namespace std;
int fib(int n);
int main(int argc, char** argv)
{
if(argc != 2)
{
cout << "usage: ./a.out number" << endl;
}
int ret = fib(atoi(argv[1]));
cout << "fib(" << argv[1] << ")" << " = " << ret << endl;
return 0;
}
int fib(int n)
{
if(n <= 1)
{
return 1;
}
int n1 = 1;
int n2 = 1;
for(int i = 1; i < n; ++i)
{
int temp = n1;
n1 = n1 + n2;
n2 = temp;
}
return n1;
}背包问题
现在我们来看一个复杂的问题，讲动态规划必须谈到的背包问题，如果理解了此方法，那么对于同一类型的问题都可以用类似的方法来解决，学算法最重要的是学会举一反三。背包问题分为01背包问题和完全背包问题，背包问题用知乎某答主的话讲就是：一个小偷背了一个背包潜进了金店，包就那么大，他如果保证他背出来所有物品加起来的价值最大。
01背包问题的描述：有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
要说明这个问题，要先了解一下背包问题的状态转换方程： f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }
其中： f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。 Pi表示第i件物品的价值。
初学者最不懂的地方可能就是这个状态方程了，i是什么鬼，j又是什么鬼？下面具体来说这个状态方程怎么来的。 之前说过动态规划是考虑递归的思想，要解决这个问题，首先想到解决其子问题。 要从5个中选出若干个装入容量为10的背包，可以分解为，将a物品装入背包，然后从其他四个中选出若干个装入剩余容量为8的袋子，因为a已经占去了2个位置；或者不装a，从其他四个中选出若干个装入容量为10的袋子？这两种做法中，价值最大的就是我们需要的方案。如果选择了第一种方案，那么继续分解，将b物品装入袋子，从其余三个中选出若干个装入剩余容量为6的袋子，或者不装b（也许你更乐意装b），从剩余三个中选出若干个装入剩余容量为8的袋子，选择这两种方案中价值最大的。依次类推，直到五个物品都选择完毕。将其一般化，用i代替a，用j代替10，用数学公式表达出来就是上面那个公式了，是不是觉得已经看懂了这个公式。 上面公式中还有个( j >= Wi )，表示剩余的容量至少要大于该物品的重量，才需要讨论装不装的问题。 既然子问题已经解决，那么自然想到用递归了，我们用递归来实现
#include <iostream>
#include <vector>
using namespace std;
vector<char> things = {
'a', 'b', 'c', 'd', 'e'};
vector<int> value = {
6, 3, 5, 4, 6};
vector<int> weight = {
2, 2, 6, 5, 4};
int backpack(int n, int w)
{
if(n == 0 | w == 0)
{
return 0;
}
int ret;
if(w < weight[5 - n])
{
ret = backpack(n - 1, w);
cout << "n = " << n << " w = " << w << " val = " << ret << endl;
return ret;
}
//n表示从多少件物品中选
//刚开始可以从五件物品中选，然后就是两种情况，放入第一件还是不放入第一件
//第一件选择完毕后，就需要从其余四件中选择，重复上面的过程
//
//当n=5时，5-n表示第一件，n=4时候，5-n表示第二件
int val1 = backpack(n - 1, w - weight[5 - n]) + value[5 - n];
int val2 = backpack(n - 1, w);
if(val1 > val2)
{
ret = val1;
//cout << "选择物品" << things[5 - n] << endl;
}
else if(val1 < val2)
{
ret = val2;
//cout << "不选择物品" << things[5 - n] << endl;
}
else
{
ret = val1;
//cout << "拿不拿" << things[5 - n] << "一样" << endl;
}
cout << "n = " << n << " w = " << w << " val = " << ret << endl;
return ret;
}
int main()
{
int ret = backpack(5, 10);
cout << "max value = " << ret << endl;
return 0;
}//输出结果
n = 1 w = 1 val = 0
n = 1 w = 6 val = 6
n = 2 w = 6 val = 6
n = 3 w = 6 val = 6
n = 1 w = 2 val = 0
n = 2 w = 2 val = 0
n = 1 w = 3 val = 0
n = 1 w = 8 val = 6
n = 2 w = 8 val = 6
n = 3 w = 8 val = 6
n = 4 w = 8 val = 9
n = 1 w = 2 val = 0
n = 2 w = 2 val = 0
n = 1 w = 3 val = 0
n = 1 w = 8 val = 6
n = 2 w = 8 val = 6
n = 3 w = 8 val = 6
n = 1 w = 4 val = 6
n = 2 w = 4 val = 6
n = 1 w = 5 val = 6
n = 1 w = 10 val = 6
n = 2 w = 10 val = 10
n = 3 w = 10 val = 11
n = 4 w = 10 val = 11
n = 5 w = 10 val = 15
max value = 15递归的过程是怎样的呢？
同样出现与求斐波那契数列相同的问题，有重复计算的地方。同样的，采取用数组来保存结果，这个结果就是上面那个表，显然我们要用一个二维数组才能完成该工作。可以采取，与之前相同的方法，在递归里加数组，但是这次我们换一种方式，用循环来做。
对于用循环来解文献2采用的列表方法非常有助于理解，因此我们采用其方法来讲述，不同的是我们会将这个表生成的过程进行详细阐述。下面这个表就是文献2中用来讲述背包问题的表，大家可以先考虑一下这个表示怎么生成的。
为了便于描述，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e可以选择了，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。对于d2单元格，表示只有物品e，d可以选择时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。所以这个表列上的数字表示背包目前的容量，该行以及该行以下的物品是可以选择的，而该行以上的物品则不是该行可以选择的。这个表是从下往上、从左往右生成的。
以第4列为例分析一下生成过程：e4用公式表示就是f[1, 4] = max{(f[0, 4 – 4] + 6), f[0, 4]}，对于d4用公式表示就是f[2, 4] = max{f[1, 4]}（因为容量为4的背包装不下重量为5的d物体），同理c4=f[3, 4]=max{f[2, 4]}，b4 = f[4, 4] = max{(f[3, 4 – 2] + 3), f[3, 4]}
/************************************************************************/
/* 01背包问题 ** 问题描述：有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？ /************************************************************************/
#include <tchar.h>
#include <iostream>
#include <vector>
#include <string.h>
#include <cstdlib>
using namespace std;
int weight[5] = {
2, 2, 6, 5, 4}; //每个物品的重量
int value[5] = {
6, 3, 5, 4, 6}; //每个物品的价值
int C[6][11]; //保存各种情况能装下物品价值的数组
vector<int> path;
void FindAnswer()
{
int capacity = 10;
for (int i = 5; i > 0; --i)
{
if (C[i][capacity] > C[i - 1][capacity])
{
path.push_back(i);
capacity -= weight[i - 1];
}
}
}
void Package()
{
for (int i = 0; i < 11; i++)
{
for (int j = 0; j <6; ++j)
{
if (i == 0)
{
//可选物品为0，所以能装的价值只能为0
C[j][i] = 0;
}
else if (j == 0)
{
//容量为零，所以能装的价值也是0
C[j][i] = 0;
}
else
{
//判断当前容量能放入
if (i >= weight[j - 1])
{
C[j][i] = max(C[j - 1][i], (C[j -1][i - weight[j - 1]] + value[j - 1]) );
}
//如果不能放入，则不放入该物品
else
{
C[j][i] = C[j - 1][i];
}
}
}
}
}
int _tmain(int args, TCHAR* argv[])
{
memset(C, -1, sizeof(C));
Package();
FindAnswer();
return 0;
}举一反三
动态规划来解决类似问题，大家可以试试： 硬币找零问题 金字塔最大路径问题
参考文献：
- http://baike.baidu.com/link?url=VaCiaDEjRqYPB433OJrlR8NluEuiKUYol1w9yGEzzzPsVkEKG9iKEIIgArEsbEmuiyJ-H12FFuFPQVJMaxbXYArPgpHx5kzfUSU48tJ4OBRhdf2_T2LAkVDAG-wx64Ad2Cl9sLVQHt3QuISVPip_Da
- http://blog.csdn.net/mu399/article/details/7722810
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/164396.html原文链接：https://javaforall.cn
腾讯云开发者
