1背包问题假设有一个背包体积是 V另外有 n 个物品物品的体积分别是 v1, v2, ... vn每个物品的价值是 w1, w2, ... wn。求怎么将物品放到背包里才能使背包中物品的价值最大 背包问题是一个典型的动态规划问题。动态规划问题中经常包含一个最字比如最大价值 ? 最短路径 ? 动态规划问题的求解思路包括以下几点1只看眼前利益动态规划关键字是动态也就是说结果是在变化的。在计算过程中只看眼前利益只要当前这种情况满足要求那么这就是中间的一个结果。所有情况都遍历完之后的眼前利益就是最终想要的结果。下边的代码是找数组的最大值。FindMax函数中找最大值的时候max 一直是已经遍历的数据的最大值一直在更新体现了只看眼前利益max 也一直在更新直到把数据都遍历完max 就是最终的结果。这就是动态规划。这是动态规划一个最简单的例子。#include iostream int FindMax(int *data, int size) { int max -1; for (int i 0; i 4; i) { if (data[i] max) { max data[i]; } } return max; } int main() { int data[4] {100, 200, 50, 10}; std::cout max: FindMax(data, 4) std::endl; return 0; }2选与不选选与不选就是分类讨论的思想。比如背包问题当考虑一个物品时要考虑两种情况即这个物品放入背包的话最终能放入的最大价值是多少这个物品不放入背包的话最终能放入的价值最大是多少。如果有 n 个物品每个物品都要做这样的分类讨论共有 2 的 n 次方种组合。把这些所有的情况的价值都计算出来哪个组合的价值最大那么这个组合就是最终的结果。排列组合把所有情况都列举出来再找满足条件的结果。3记录历史信息在动态规划的计算过程中对一些情况的讨论往往会重复在计算过程中可以记录历史信息那么可以减小后边的重复计算。背包问题分为两类0-1 背包和无限背包。0-1 背包说的是每个物品的数量只有一个 也就是这个物品要么放进去要么不放进去只有两种情况。无限背包说的是每个物品的数量有无数个每个物品都可以放 0 个1 个或者多个。数据遍历是很多算法的基础。无论是排序算法还是搜索算法或者动态规划。算法的基础就是对一定数量的数据进行遍历在遍历的过程中嵌入自己的算法逻辑逻辑的不同就产生了了不同的算法。数据保存在数据结构中比如数组链表二叉树图。每种数据结构都有自己的遍历方法。1.1 0-1 背包牛客网 01背包链接。01背包使用一维数组时间复杂度是 O(n)使用选与不选的原始算法时间复杂度是 O(2 的 n 次方)。所以优先选用以为数组。1.1.1 一维数组#includeiostream #includevector using namespace std; // 能够放下的最大价值 int MaxValue(std::vectorint v, std::vectorint w, int n, int V) { // 数组的长度是 V 1 // 之所以比背包的体积大 1这样就最大可以使用 V 做数组的下标了便于使用 std::vectorint value(V 1); // 数组元素的值是这个体积下能放下的价值初始化为 0 value.assign(V 1, 0); // 两层循环第一层循环遍历物品 for (int i 0; i n; i) { // 第二层循环遍历背包剩余的空间能放下当前这个物品的空间 // 体积从大到小进行遍历 for (int j V; j v[i]; j--) { // value[j] 是没放这个物品的时候背包在 j 这个体积下的价值 // value[j - v[i]] w[i] 是放下这个物品的时候j 体积下的价值 if (value[j - v[i]] w[i] value[j]) { value[j] value[j - v[i]] w[i]; } } } return value[V]; } // 背包正好装满时的最大价值 int FullMaxValue(std::vectorint v, std::vectorint w, int n, int V) { std::vectorint value(V 1); // 与背包能放下的最大值比较的话 // 初始值是不一样的 // 将 value[0] 初始化为 0 其它的元素初始化为一个非常小的数 // 这个非常小的数要保证物品价值都加起来和这个数相加也不会大于 0 // 这样能保证正好装满的时候value[V] 是大于 0 的 // 最后可以通过 value[V] 是不是大于 0 来判断背包是不是可以正好装满 // 如果能正好装满那么 value[V] 价值是在 value[0] 也就是 0 的基础上加上物品的价值 // 所以value[V] 是大于 0 的。 // 如果不能正好装满那么 value[V] 的价值在计算过程中肯定与一个非常小的数进行了相加 // 所以 value[V] 是小于 0 的 value.assign(V 1, -99999999); value[0] 0; for (int i 0; i n; i) { int tmp_v v[i]; int tmp_w w[i]; for (int j V; j tmp_v; j--) { int value_old value[j]; int value_new value[j - tmp_v] tmp_w; if (value_new value_old) { value[j] value_new; } } } if (value[V] 0) { return 0; } return value[V]; } int main() { int n 0; int V 0; std::vectorint v; std::vectorint w; cin n V; for (int i 0; i n; i) { int a 0; int b 0; cin a b; v.push_back(a); w.push_back(b); } std::cout MaxValue(v, w, n, V) std::endl; std::cout FullMaxValue(v, w, n, V); return 0; }1.1.2 选与不选选与不选使用递归算法。递归算法的时间复杂度是O(2的 n 次方)时间复杂度太大在牛客网上运行经常超时。使用一维数组的方式时间复杂度是 O(n)所以有限选择数组的方式。#includeiostream #includevector using namespace std; // 保存背包能放得下的最大价值 int max_value 0; // 保存背包正好放满时的最大价值 int max_full_value 0; // 已放入的物品的价值 int value 0; // 已放入的物品的体积 int volume 0; void MaxValue(std::vectorint v, std::vectorint w, int n, int V, int index) { if (volume V) { return; } if (index n) { if (volume V value max_value) { max_value value; } if (volume V value max_full_value) { max_full_value value; } return; } for (int i index; i n; i) { // 选择这个物品 volume v[i]; value w[i]; MaxValue(v, w, n, V, i 1); // 不选择这个物品 volume - v[i]; value - w[i]; MaxValue(v, w, n, V, i 1); } } int main() { int n 0; int V 0; std::vectorint v; std::vectorint w; cin n V; for (int i 0; i n; i) { int a 0; int b 0; cin a b; v.push_back(a); w.push_back(b); } MaxValue(v, w, n, V, 0); std::cout max_value std::endl; std::cout max_full_value; return 0; }1.2 无限背包无限背包也叫完全背包牛客网链接如下。完全背包无限背包说的是每个物品的个数都有无限个。可以使用一维数组的方式来求解与 01 背包不同的是在遍历体积的时候需要从小到大进行遍历01 背包是从大到小进行遍历的。为什么从小到大进行遍历呢这样对于一个物品可以遍历到放置多个的情况。比如一个背包的体积是 10一个物品的体积是 2。如果从小到大进行遍历那么只放这个物品的话可以放置 5 个这样的物品体积遍历到 2 的时候可以放一个4 的时候可以再放一个以此类推。如果从大到小进行遍历从 10 遍历到 2那么只能放置一个不能在前边放置的基础之上再次进行放置。#include iostream #include vector using namespace std; int MaxValue(std::vectorint v, std::vectorint w, int n, int V) { std::vectorint value(V 1); value.assign(V 1, 0); for (int i 0; i n; i) { int tmp_v v[i]; int tmp_w w[i]; for (int j tmp_v; j V; j) { int value_old value[j]; int value_new value[j - tmp_v] tmp_w; if (value_new value_old) { value[j] value_new; } } } return value[V]; } int BagFullMaxValue(std::vectorint v, std::vectorint w, int n, int V) { std::vectorint value(V 1); value.assign(V 1, -99999999); value[0] 0; for (int i 0; i n; i) { int tmp_v v[i]; int tmp_w w[i]; for (int j tmp_v; j V; j) { int value_old value[j]; int value_new value[j - tmp_v] tmp_w; if (value_new value_old) { value[j] value_new; } } } if (value[V] 0) { return 0; } return value[V]; } int main() { int n 0; int V 0; std::vectorint v; std::vectorint w; cin n V; for (int i 0; i n; i) { int a 0; int b 0; cin a b; v.push_back(a); w.push_back(b); } int max_value MaxValue(v, w, n, V); int bag_full_max_value BagFullMaxValue(v, w, n, V); std::cout max_value std::endl; std::cout bag_full_max_value std::endl; }2组合之和(数可以复用)39. 组合总和 - 力扣LeetCode看到一个题目我们往往会先在脑子里去想算法过程是什么样的排序、搜索、循环、判断。当想着想着很难想清楚的时候这种时候可以考虑是不是动态规划是不是递归。本题就是一个动态规划的题目而动态规划很多时候又会用到递归算法。class Solution { public: vectorvectorint combinationSum(vectorint candidates, int target) { vectorint one_result; combinationSumHelper(candidates, target, 0, one_result); //参考无限背包问题的循环算法不好实现 // int remain target; // int size candidates.size(); // for (int i 0; i size;) { // if (remain 0) { // ret.push_back(one_result); // } // if (candidates[i] remain) { // //循环算法没有办法在这一个位置做两个选择 // //递归算法可以在这一个地方分两叉 // one_result.push_back(candidates[i]); // } else { // i; // continue; // } // } return ret; } void combinationSumHelper(vectorint candidates, int target_remain, int index, vectorint one_result) { //递归退出条件 if (index candidates.size()) { return; } //递归退出条件 if (target_remain 0) { ret.push_back(one_result); return; } //不选 combinationSumHelper(candidates, target_remain, index 1, one_result); int data candidates[index]; //选 if (data target_remain) { one_result.push_back(data); //每个数可以不限次数使用决定了这里得index就是index不能传index1 combinationSumHelper(candidates, target_remain - data, index, one_result); one_result.pop_back(); } } vectorvectorint ret; };3三角形最小路径和120. 三角形最小路径和 - 力扣LeetCode路径的问题在二叉树、图中也常见到这样的问题。用一个vector来保存路径典型的三段式的递归算法vector.push_back(当前元素)递归vector.pop(当前元素)但是使用这种算法时间复杂度是2的n次方导致运行超时class Solution { public: int minimumTotal(vectorvectorint triangle) { height_ triangle.size(); vectorint path; path.push_back(triangle[0][0]); impl(triangle, 1, 0, path); return min_; } void impl(vectorvectorint triangle, int level, int index, vectorint path) { if (level height_) { int tmp 0; for (auto data : path) { tmp data; } if (tmp min_) { min_ tmp; } return; } path.push_back(triangle[level][index]); impl(triangle, level 1, index, path); path.pop_back(); path.push_back(triangle[level][index 1]); impl(triangle, level 1, index 1, path); path.pop_back(); } int min_ 100000000; int height_ 1; };可以不用path来保存路径因为题目的结果也没有要把路径打印出来在二叉树、图中的路径题中往往是需要将符合目标的路径打印出来这样的题目需要path来保存路径。而当前这个题目不需要将路径打印出来而是求最小的和那么就可以不保存路径而是用一个变量来保存当前的和对应上边三段式中的vector操作就成为了和的加减操作。但是这样的算法时间复杂度仍然是2的n次方仍然会导致运行超时。class Solution { public: int minimumTotal(vectorvectorint triangle) { height_ triangle.size(); return impl(triangle, 0, 0); } int impl(vectorvectorint triangle, int level, int index) { if (level height_) { return 0; } int sum triangle[level][index]; int sum1 impl(triangle, level 1, index); int sum2 impl(triangle, level 1, index 1); if (sum1 sum2) { return sum sum1; } return sum sum2; } int height_ 1; };动态规划不仅仅是只能通过递归算法来实现也可以通过for循环来实现也就是迭代算法。使用二维数组来保存历史状态。两层循环外层循环是遍历数组的层数内存循环是遍历一个一维数组每一层数组的第一个元素和最后一个元素以及中间的元素要分别处理因为第一个元素只受上一层的第一个元素影响最后一个元素只收上一层的最后一个元素影响中间的元素受上一层的同等下标的元素以及前一个下标 的元素影响。class Solution { public: int minimumTotal(vectorvectorint triangle) { int height triangle.size(); vectorvectorint sum(height, vectorint(height,0)); sum[0][0] triangle[0][0]; for (int level 1; level height; level) { for (int i 0; i level; i) { if (i 0) { sum[level][i] sum[level - 1][i] triangle[level][i]; } else if (i level) { sum[level][i] sum[level - 1][i - 1] triangle[level][i]; } else { sum[level][i] sum[level - 1][i] sum[level - 1][i - 1] ? sum[level - 1][i] triangle[level][i] : sum[level - 1][i - 1] triangle[level][i]; } } } int ret 100000000; for (auto tmp : sum[height - 1]) { if (tmp ret) { ret tmp; } } return ret; } };类似于背包问题中可以将二维数组优化为一维数组来实现本题目也可以将二维数组进行优化。使用一维数组之后对于每一层的数据进行遍历要从大到小进行遍历。从大到小进行遍历的时候使用的元素值才是上一层的结果而从小到大进行遍历那么上一层的数据会被覆盖。class Solution { public: int minimumTotal(vectorvectorint triangle) { int height triangle.size(); vectorint sum(height, 0); sum[0] triangle[0][0]; for (int level 1; level height; level) { for (int i level; i 0; i--) { if (i 0) { sum[i] sum[i] triangle[level][i]; } else if (i level) { sum[i] sum[i - 1] triangle[level][i]; } else { sum[i] sum[i] sum[i - 1] ? sum[i] triangle[level][i] : sum[i - 1] triangle[level][i]; } } } int ret 100000000; for (auto tmp : sum) { if (tmp ret) { ret tmp; } } return ret; } };