本文主要是介绍月球美容计划之维尼的背包（基础篇），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前言
背包放在了寒假集训安排比较靠前的位置，虽然时间长，但遗忘的还不是很厉害，但是重新复习起来，却发现背包难度要在最短路，最小生成树等初等图论之上。背包的适用范围太广泛了，正是这种应用广泛还可以举一反三的算法，越是难以掌握。
一直在看背包九讲，看它把背包问题模型化并给出了出色的模板代码。但是看完更感觉背包不像一种算法，更像一种思想，我们就是把各种问题模拟成背包问题，那么，模型化并尝试举一反三，不失为学习背包的良策。
但实在是无法深入各个模型，背包一拖再拖，逢一批出洞烧烤之际，离群把总结敲完，尝试把心得总结，确定C语言模板，以备后用。
01背包
01背包才是最基础的背包模型，各种其他背包都可以化为01背包模型。
01背包的题目情景也很单纯：
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 C[i]，得到的
价值是 W[i]。求解将哪些物品装入背包可使价值总和最大。
其中模型的关键特点如下：
1.有限种物品，
2.每种物品只有一个，
3.每个物品有且只有两种状态，装入背包 || 不装入，
4.背包体积一定；
基本思路
01背包的基本思路来自其关键特点：每种物品有且只有两种状态，装入（1），或不装入（0），然而，考虑第i件物品放入体积为V的背包的时候是在考虑前i - 1件物品放入体积为V的背包基础之上产生的，而在考虑第i件物品的时候，我们能且只能做把第i件物品放入背包或者不放入背包，所以，假如我们已经有了前i - 1个物品的最优解，那么我们做第i个物品的决断是很简单的，就是比较一下放和不放的收益。
所以我们便得到了01背包的状态转移方程：
F[i][v] = max (F[i − 1][v] , F[i − 1][v − C[i]] + W[i]);
然后我们的假定条件（已知前i - 1个物品的最优解）是可得的，所以，对于这样的算法，就有了可以实现的代码：
int qmax (int a,int b){return a > b ? a : b;}....memset (dp,0,sizeof (dp));for (i = 1;i < n;i++)for (k = C[i];k <= V;k--){if (k >= C[i])dp[i][k] = qmax(dp[i - 1][k],dp[i - 1][k - C[i]] + W[i]);}
当然，这用了二维空间，背包九讲也介绍了如果优化空间复杂度，（Ps’因为题目要求不同，不代表二维比一维次，有时需要背包中间值，二维比一维更好些）变二维为一维，代码如下：
for (i = 0;i < n;i++)for (k = V;k <= C[i];k--){if (k >= C[i])dp[k] = qmax(dp[k],dp[k - C[i]] + W[i]);}
他的优化原理是因为第i行之与第i - 1行有关，因此，前面的没有存储的必要，当前一行的数据被使用过，就直接覆盖掉好了，不一定要必须保存下来，但是也正是如此，优化的时候一定要注意第二层循环一定要有V执行到C[i],原因是k - C[i]<=k，也就是说，你在生成第i行数据的时候，利用的第i - 1行的数据不能被覆盖掉，然而，第i行的生成要利用同行位置靠前的数据，因此，从后向前覆盖正好可以避免这个问题。
完全背包
完全背包也是非常重要的背包模型，也是寒假学的两个背包模型之一，其实就是01背包的简单升级版，其问题情境是这个样子的：
有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品
的费用是 C[i]，价值是 W[i]。求解：将哪些物品装入背包，可使这些物品的耗费的费用总
和不超过背包容量，且价值总和最大。
不讨论它的关键特点，之找出他和01的异同：
相同点：
1.都是有限个物品
2.都是一定以及的背包
3.都追求利益最大化
不同点：
1.01背包每种物品有限，有且只有一个，而完全背包没有限制
2.01背包只需要为每种物品考虑选取两个状态（放或不放）之一，而完全背包不仅需要考虑每种物品的放或不放，还有考虑放多少。
基本思路
背包九讲种介绍了不止一种的思路（包括性价比排序，转化为01背包），其中最基础的方法虽然我不想总结但的确很直白的说出什么是完全背包，其状态转移方程：
F[i][v] = max{F[i − 1][v − kC[i]] + kW[i]| 0 ≤ kCi≤ v}
但其过高的时间复杂度让我提不起兴趣，因此，我只想总结生成出模型代码更高效更简单的那种，也就是那个O(VN)的算法：
先说他的状态转换方程：
F[i][v] = max(F[i − 1][v],F[i][v − C[i]] + W[i])
其基本思路是这个样子的，先抛开每种物品放几个不说，先把问题分解为每种物品放与不放和每个物品放几个两个问题，那么，只需要考虑第i件物品能不能放这一个问题就好了，
那么，就可以写成这样的代码模型（一维）：
for (i = 0;i < n;i++)for (k = C[i];k <= V;k++){if (k >= C[i])dp[k] = qmax(dp[k],dp[k - C[i]] + W[i]);}（二维）for (i = 1;i < n;i++)for (k = C[i];k <= V;k++){if (k >= C[i])dp[i][k] = qmax(dp[i - 1][k],dp[i][k - C[i]] + W[i]);}
其实比较01和完全的代码模型，发现差别不大，在一维模型中，差别反而就是当时强调不能犯的错误for (k = C[i];k <= V;k++)。其实这样的原因很简单，因为状态转移方程比较的是F[i − 1][v],F[i][v − C[i]] + W[i]之间的大小关系，当准备装入第i件物品的时候，不仅仅需要判断第i - 1 件，也需要判断第i件，原因很简单，完全背包放入某种物品的数目没有限制，当你每次装完一个这个物品的时候，不代表这个物品不能再被装入，也就是这样，导致在构建一维数组的时候，可以直接使用第i行的数据，来进行判断，是不是可以再多装一个同类物品。
多重背包
有一种背包叫做多重背包，然而在寒假集训中胖学长没有讲，迫于当时时间有限，背包九讲也就没有及时跟上，九讲看完两讲就去做题了，但是当看完第3讲第4讲才发现背包的灵活，也更坚定的认为学好模型很简单，用好模型定不容易，固认为越是灵活的东西，越是不容易掌握。
先说一下多重背包的问题情境：
有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 M[i]件可用，每件耗费的
空间是 C[i]，价值是 W[i]。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超
过背包容量，且价值总和最大。
根据题目情境，很容易就能找出多重背包的特色，多重背包很像完全背包但又有差异，其关键特点就是：每种物品不再是无限个而是有限个。
也正是因为多重背包与完全背包相似而差异不大，所以多重背包的解决算法就是从完全背包上发展而来。
那么就可以说一下基本算法：
其状态转移方程：F[i][v] = max{F[i − 1][v − k ∗ C[i]] + k ∗ W[i]| 0 ≤ k ≤ M[i]},复杂度是 O(V ΣMi)。
我一点也不看好以上的思路，但是背包九讲提出把多重化为01的思路还是通用性挺好的，但是我还没有做过多重背包的题目，现在也不过就是空谈理论。
所以就截取背包九讲的两个方法：
方法一：
将第 i 种物品分成若干件 01 背包中的物品，其中每件物品有一个系
数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。令这些系数分别为
1,2,22...2k−1,Mi− 2k+ 1，且 k 是满足 Mi− 2k+ 1 > 0 的最大整数。例如，如果 Mi
为 13，则相应的 k = 3，这种最多取 13 件的物品应被分成系数分别为 1,2,4,6 的四件
物品。
这个就是把多重背包看做01背包，用到了“拆分物品”的思想，因为还没敲过这个方法，还带找时间做过多重背包的题目亲身实践。
方法二：
设 F[i,j] 表示“用了前 i 种物品填满容量为 j 的背包后，最多还剩
下几个第 i 种物品可用”，如果 F[i,j] = −1 则说明这种状态不可行，若可行应满足
0 ≤ F[i,j] ≤ Mi。最终 F[N][0...V ] 便是多重背包可行性问题的答案。
没有实践就没有收获，多重背包只能说有了个大体的认识，也许某次遇见它会有个做题的方向，但还是最好找时间找找多重的题目做做。
尾声
本想一篇文章就把背包写完，没想到越写越多，在图书馆敲了两个小时，才发现写的只是个基础，而后续应用以及拓展根本没涉及，只能分篇了。又需要找时间写写背包的拓展应用。
Ps`：背包题目还是做得少，所能想到的根本拓展不开。
这篇关于月球美容计划之维尼的背包（基础篇）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
