多维多重背包问题_满满干货！背包问题全总结（带c++源码）

目录：

• 动态规划简介
• 0-1 背包问题
• 完全背包问题
• 多重背包问题
• 混合背包问题
• 二维（多维）费用背包问题
• 分组的背包问题
• 有依赖的背包问题

动态规划简介

在学习背包问题之前需要对动态规划有一定的了解 。一般来说，当一个最优决策问题可以划分成规模更小的子问题，且具有最优子结构（即全局的最优解包含了子问题的最优解），则可以考虑用动态规划算法。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。

动态规划算法最重要的便是寻找状态转移方程，即多段决策过程的递推关系。关于动态规划的更多内容，我们以后会再总结。

今天我们来学习动态规划的经典应用问题：背包问题。本文是对网上流传多年的《背包问题九讲》进行纠错和补充，把其中讲的模糊的地方清晰化，并加入了一些例题用c++实现。 文中出现的所有代码均为本人编写 ，欢迎指正。

• 0-1 背包问题

题目

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

把0-1背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选），Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积（重量）；

b) 建立模型，即求max(V1X1+V2X2+…+VnXn)；

c) 约束条件，W1X1+W2X2+…+WnXn<capacity；

d) 定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值；

基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

优化空间复杂度

以上方法的时间和空间复杂度均为O(N*V)（）其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。由于我们在计算f[i][v]时要用到f[i-1][v]和f[i-1][v-c[i]],因此要保证合适的计算顺序。

如果只用一个数组f[0..V]，如何保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？事实上，这要求在每次主循环中我们以v=V..0的顺序（逆序）推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：

for i=1..Nfor v=V..0f[v]=max{f[v],f[v-c[i]]+w[i]};//f[v]初始值为？

这段程序中，i从小往大递增，对应的分f[v]其实隐式的具有i这一轮次信息，即第i 轮迭代完成后f[v]就是之前的f[i][v]。

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，

事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出一个处理一件01背包中的物品过程，以后的代码中直接调用不加说明。

过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。

procedure ZeroOnePack(cost,weight)ZeroOnePack(c[i],w[i]);f[v]=max{f[v],f[v-cost]+weight}

注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了，就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1]，这是显然的，因为装不进去。

有了这个过程以后，01背包问题的伪代码就可以这样写：

for i=1..NZeroOnePack(c[i],w[i]);

初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。

为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。

如何根据表格复原答案？

以上的算法可给出背包的最大价值，却还没给出具体选择那些物品可以获得最大价值。由于空间复杂度优化后的算法只保存了当前的价值信息，丢失了之前的信息，故无法用来寻找最优解的组成。我们需要用未优化的算法来找解的组成。

根据填表的原理可以有如下的寻解方式：1) f(i,j)=f(i-1,j)时，说明没有选择第i个商品，则回到f(i-1,j)；2) f(i,j)=f(i-1,j-w(i))+w(i)实时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到f(i-1,j-w(i))；3) 一直遍历到i＝0结束为止，所有解的组成都会找到。

下面来看一道相关例题

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/house-robberclass Solution { public:int rob(vector<int>& nums) {if(nums.size()<1)return 0;if(nums.size()==1)return nums[0];int dp[nums.size()];//dp[i]表示前i间房子可以获得的最大金额。dp[0]=nums[0];dp[1]=max(nums[1],nums[0]);for(int i=2;i<nums.size();i++){dp[i]=max(dp[i-1],dp[i-2]+nums[i]);//状态转移方程}return dp[nums.size()-1];} };

• 完全背包问题

题目

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路

这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件…… V/c[i]件。如果仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

这跟01背包问题一样有O(N*V)个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态f[i][v]的时间是O(v/c[i])，总的复杂度是超过O(VN)的。

将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。

//基本算法,已运行检验过。 #include<iostream> #include<vector> using namespace std; int completeKnapsak(vector<int>&w,vector<int>&c, int&volume){ vector<int>dp(volume+1,0); for(int i=0;i<w.size();i++) { for(int v=volume;v>=0;v--)//为什么逆序前面已经讲过。{ for(int k=0;k*c[i]<=v;k++) { dp[v]=max(dp[v],dp[v-k*c[i]]+k*w[i]); } } } return dp[volume];} int main(){ int a[]={7,5,8,6,4,2,9}; vector<int>w(a,a+sizeof(a)/sizeof(int)); int b[]={2,1,5,3,7,4,8}; vector<int>c(b,b+sizeof(b)/sizeof(int)); int volume=15; cout<<completeKnapsak(w,c,volume); return 0;}

一个简单有效的优化

完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j]（即i代价小而收益大），则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。

这个优化可以简单的O(N^2)地实现，一般都可以承受。另外，针对背包问题而言，比较不错的一种方法是：首先将费用大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以O(V+N)地完成这个优化。

#include<iostream> #include<vector> #include<map> using namespace std;int completeKnapsak(vector<int>&w,vector<int>&c,int&volume){vector<int>dp(volume+1,0);map<int,int> resid;map<int,int>::iterator it;for(int i=0; i<c.size();i++)//成本相同时，保留收益最高者。{ if(c[i]>volume)continue;it=resid.find(c[i]);if(it==resid.end()) resid[c[i]]=w[i];else{resid[c[i]]=max(resid[c[i]],w[i]);}}for(map<int,int>::iterator id=resid.begin();id!=resid.end();id++){for(int v=volume;v>=0;v--)//为什么逆序前面已经讲过。{for(int k=0;k*id->first<=v;k++){dp[v]=max(dp[v],dp[v-k*id->first]+k*id->second);}}}return dp[volume];}int main(){int a[]={7,5,8,6,4,2,9};vector<int>w(a,a+sizeof(a)/sizeof(int));int b[]={2,1,5,3,7,4,8};vector<int>c(b,b+sizeof(b)/sizeof(int))；int volume=15;cout<<completeKnapsak(w,c,volume);return 0; }

转化为01背包问题求解

既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第i种物品最多选V/c[i]件，于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。

更高效的转化方法是：把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品，其中k满足c[i]*2^k<=V。这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log(V/c[i]))件物品，是一个很大的改进。

//用二进制的方法，我写了两个版本，在此均给出 #include<iostream> #include<vector> #include<cmath> using namespace std; int completeKnapsak_1(vector<int>&w,vector<int>&c, int&volume) {vector<int>dp(volume+1,0);vector<int>newc;vector<int>neww;int ni;for(int i=0;i<c.size();i++){ ni=volume/c[i];int k;for(k=0;(pow(2,k+1))<=ni;k++){ newc.push_back(c[i]*(pow(2,k))); neww.push_back(w[i]*pow(2,k)); } newc.push_back(c[i]*(ni-pow(2,k)+1)); neww.push_back(w[i]*(ni-pow(2,k)+1)); } for(int i=0;i<newc.size();i++) { for(int v=volume;v>=newc[i];v--) { dp[v]=max(dp[v],dp[v-newc[i]]+ neww[i]); } } return dp[volume];} int completeKnapsak_2(vector<int>&w,vector<int>&c, int&volume)//这个程序完成了和上面一样的功能，但是节省了空间。 {vector<int>dp(volume+1,0);int ni;for(int i=0;i<c.size();i++){ni=volume/c[i];int k=1;while(k<ni){ for(int v=volume;v>=k*c[i];v--)//ZeroOnePack(k*w,k*c) { dp[v]=max(dp[v],dp[v-k*c[i]]+k*w[i]);}ni-=k;k*=2;}for(int v=volume;v>=ni*c[i];v--)//ZeroOnePack(ni*w,ni*c) { dp[v]=max(dp[v],dp[v-ni*c[i]]+ni*w[i]);}}return dp[volume]; }int main() { int a[]={7,5,8,6,4,2,9}; vector<int>w(a,a+sizeof(a)/sizeof(int)); int b[]={2,1,5,3,7,4,8}; vector<int>c(b,b+sizeof(b)/sizeof(int)); int volume=50; cout<<endl; cout<<completeKnapsak_2(w,c,volume); return 0;}

但我们有更优的O(VN)的算法。

O(VN)的算法

这个算法使用一维数组，先看伪代码：

for i=1..Nfor v=0..Vf[v]=max{f[v],f[v-cost]+weight}

你会发现，这个伪代码与01背包的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么01背包中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。

这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价地变形成这种形式：

f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}

其实这个方程的本质就是，我们要在所有可能的情况中找到最优者（动态规划就是一种聪明的穷举法）。而对于第i步而言，在完全背包问题的语境下，只有两种可能，要么一个都不选，要么至少选一个，分别对应f[i-1][v]和f[i][v-c[i]]+w[i]。

将这个方程用一维数组实现，便得到了上面的伪代码。

最后抽象出处理一件完全背包类物品的过程伪代码，以后会用到：

procedure CompletePack(cost,weight)for v=cost..Vf[v]=max{f[v],f[v-c[i]]+w[i]}#include<iostream> #include<vector> #include<cmath> using namespace std; int completeKnapsak(vector<int>&w,vector<int>&c, int&volume){ vector<int>dp(volume+1,0); for(int i=0;i<c.size();i++) { for(int v=c[i];v<=volume;v++) { dp[v]=max(dp[v],dp[v-c[i]]+w[i]); } } return dp[volume];} int main(){ int a[]={7,5,8,6,4,2,9}; vector<int>w(a,a+sizeof(a)/sizeof(int)); int b[]={2,1,5,3,7,4,8}; vector<int>c(b,b+sizeof(b)/sizeof(int)); int volume=15; cout<<endl; cout<<completeKnapsak(w,c,volume); return 0;}

完整内容可查看下面这篇推文：

https://mp.weixin.qq.com/s/c5Q23XscHf-MPQHjQVIKBQ​mp.weixin.qq.com

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的多维多重背包问题_满满干货！背包问题全总结（带c++源码）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。