01背包

问题分析代码实现从前往后拿，递归实现非递归实现非递归实现，自上向下填充

允接上一文章内容：

算法 动态规划: link.

问题分析

按照普通思维，首先想到应该为贪心算法，也就是计算每个物品重量价值比，将性价比高的物品装入背包，但是这并不是该问题的最优解，因为物品不是可分割的，不能按照重量价值比进行选择

这道问题的最优解应该通过动态规划求解，那么其递归方程式为：

在这里f(i,j)，记为当背包容量为 j，现有 i 物品可拿，所能装进背包的最大价值

再者我们举例说明，假设背包总容量为8，现在有四件物品，其重量，价值分别为：

首先我们是一个 f(4,8)，即当容量为8，有4件物品可拿，所能装进背包的最大价值，接着第二步，选择对第四件物品拿与不拿，继而得到②③，f(3,3)+8，即容量为3，有 3 件物品可拿的最大价值加上 8（第四件物品的价值），或者 f(3,8)，容量 8，有 3 件物品可拿的最大价值

随着我们的不断细分，最终得到最大值为12，也就是拿走第二件与第四件物品，对于上面的方式，无论是从后往前拿还是从前往后拿都是相同的

那么我们再看上面的递归方程式就很明了了

代码实现

从前往后拿，递归实现

int Knapsack(vector<int>& w, vector<int>& v, int i, int j, int n){if (i == n) //只有一个物品{return j >= w[i] ? v[i] : 0;}else{if (j < w[i]) //背包容量不足{return Knapsack(w, v, i + 1, j, n);}else{int maxv1 = Knapsack(w, v, i + 1, j, n);//不装该物品int maxv2 = Knapsack(w, v, i + 1, j - w[i], n) + v[i]; //装该物品return maxv1 > maxv2 ? maxv1 : maxv2;}}}int main(){const int n = 5; //物品数量const int c = 10; //背包容量vector<int> w = {0,2,2,6,6,4 }; //重量vector<int> v = {0,6,3,5,4,6 }; //价值int maxv = Knapsack(w, v, 1, c, n);//i jcout << maxv << endl;return 0;}

非递归实现

void print_vect(const vector<vector<int>>& m){for (int i = 1; i < m.size(); ++i){for (int j = 1; j < m[i].size(); ++j){printf("%4d", m[i][j]);}printf("\n");}printf("\n");}int Knapsack2(vector<int>& w, vector<int>& v, int n, int c, vector<vector<int>>& m){if (n == 0) return 0;for (int j = 0; j <= c; ++j) //填充最后一行{m[n][j] = j >= w[n] ? v[n] : 0;}print_vect(m);for (int i = n - 1; i >= 1; --i){for (int j = 1; j <= c; ++j){if (j >= w[i]){m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);//通过容量与价值进行判断}else{m[i][j] = m[i - 1][j];}}print_vect(m);}}int main(){const int n = 5; //物品数量const int c = 10; //背包容量vector<int> w = {0,2,2,6,6,4 }; //重量vector<int> v = {0,6,3,5,4,6 }; //价值vector<vector<int>> m(n + 1, vector<int>(c + 1, 0)); Knapsack2(w, v, n, c, m);return 0;}return 0;}

在非递归实现中，我们首先传入了一个表格，其格式如下：

进入函数第一步，对最后一行进行填充，接下来自下向上每一行进行填充

m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);

在填充过程中，例如黄色位置：j >= w[i]，但是通过价值比较，4<6所以依然填入的是6，一直到 9 位置，10>6 则在此填入10

非递归实现，自上向下填充

void print_vect(const vector<vector<int>>& m){for (int i = 1; i < m.size(); ++i){for (int j = 1; j < m[i].size(); ++j){printf("%4d", m[i][j]);}printf("\n");}printf("\n");}void Knapsack3(vector<int>& w, vector<int>& v, int n, int c, vector<vector<int>>& m){for (int i = 1; i <= n; ++i) //行{for (int j = 1; j <= c; ++j) //列{if (j < w[i]){m[i][j] = m[i - 1][j]; //拷贝上面的}else{m[i][j] = std::max(m[i - 1][j], m[i - 1][j - w[i]] + v[i]);//判断放与不放的最优解}}print_vect(m);}}int main(){const int n = 5; //物品数量const int c = 10; //背包容量vector<int> w = {0,2,2,6,6,4 }; //重量vector<int> v = {0,6,3,5,4,6 }; //价值vector<vector<int>> m(n + 1, vector<int>(c + 1, 0)); Knapsack3(w, v, n, c, m);return 0;}

最后的代码是，通过上述表中的变化，对每个物品加上bool值来确定是否取走了该物品

void backx(vector<int>& w, vector<vector<int>>& m, int n, int c,vector<bool>& x){for (int i = n; i >= 1; --i){if (m[i][c] != m[i - 1][c]) //该物品放入了背包{x[i] = true;c = c - w[i];}}}int main(){const int n = 5; //物品数量const int c = 10; //背包容量vector<int> w = {0,2,2,6,6,4 }; //重量vector<int> v = {0,6,3,5,4,6 }; //价值vector<vector<int>> m(n + 1, vector<int>(c + 1, 0)); vector<bool> X(n + 1,false);Knapsack3(w, v, n, c, m);backx(w, m, n, c, X);for (int i = 1;i<=n;++i){if (X[i]){cout << i << endl;}}return 0;}

如果觉得《算法 动态规划 01背包问题》对你有帮助，请点赞、收藏，并留下你的观点哦！