关键词：
文章目录
- 一、01背包问题
- 二、完全背包问题
- 三、多重背包问题
- 四、分组背包
一、01背包问题
n个物品，每个物品的重量是，价值是
，背包的容量是
若每个物品最多只能装一个，且不能超过背包容量，则背包的最大价值是多少？
模板
int n; // 物品总数
int m; // 背包容量
int v[n]; // 价值
int w[n]; // 重量
二维形式
// f[i][j]表示在考虑前i个物品后，背包容量为j条件下的最大价值
int f[n][m];
// 先遍历物品，后遍历容量
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(j < w[i]) f[i][j] = f[i-1][j]; // 当前重量装不进，价值等于前i-1个物品
else f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i]); // 能装，需判断
cout << f[n][m];
一维形式
int f[m]; // f[j]表示背包容量为j条件下的最大价值
for(int i = 1; i <= n; ++i)
for(int j = m; j >= w[i]; --j)
f[j] = max(f[j], f[j - w[i]] + v[i]); // 注意是倒序，否则出现写后读错误
cout << f[m]; // 注意是m不是n
注意f[i][j]的含义：在考虑前i个物品后，背包容量为j条件下的最大价值。而不是表示选了i个物品的最大价值，实际上选择的物品数<=i。f[j]表示背包容量为j条件下的最大价值
二维压缩成一维，实际上是寻找避开写后读错误的方法:
f[i][j]始终只用上一行的数据f[i-1][...]更新（迭代更新的基础，如果还需用上上行数据则不可压缩）
f[i][j]始终用靠左边的数据f[i-1][<=j]更新（决定了只能倒序更新）
显然i=0时，f(i,j)=0，而初始化时自动赋予0，故不必但单独处理第0行
二、完全背包问题
假设背包容量为j时，最多可装入k个物品i，k不能无限大，因为背包容量有限，则有：
上述max括号里总共k+1项
考虑到：
上述max括号里总共k项
上式变形得：
因此我们得到：
也就是f[i][j]可以由其左侧的f[i,j-w[i]]和其正上方的f[i−1][j]推导出来
未优化的二维形式
// f[i][j]表示在考虑前i个物品后，背包容量为j条件下的最大价值
int f[N][M];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
// 第三重循环遍历上述的椭圆，找最大值，分别表示物品i取 0 ... j/w[i]次
for (int k = 0; k <= j / w[i]; k++)
f[i][j] = max(f[i][j], f[i - 1][j - k * w[i]] + k * v[i]); // 注意和01背包的对比
cout << f[n][m];
// 最内层的for循环求出 f[i-1][j] , f[i-1][j-w[i]] + v[i], f[i-1][j-2*w[i]] + 2*v[i], ..., f[i-1][j-k*w[i]] + k*v[i]中的最大值
优化的二维形式
// f[i][j]表示在考虑前i个物品后，背包容量为j条件下的最大价值
int f[N][M];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if(j < v[i]) f[i][j] = f[i-1][j]; // 当前重量装不进，价值等于前i-1个物品
else f[i][j] = max(f[i-1][j], f[i][j - w[i]] + v[i]); // max(不装物品i，装物品i(包含了装1个...装j/w[i]个的情况))
cout << f[n][m];
// f[i][j - w[i]] + v[i] = max(装0个物品i,装1个物品i,...,装k个物品i) + v[i]
// f[i][j - w[i]] + v[i] = max(f[i-1][j-w[i]], f[i-1][j-2*w[i]]+v[i], ..., f[i-1][j-(k+1)*w[i]]+k*v[i]) + v[i]
// f[i][j - w[i]] + v[i] = max(f[i-1][j-w[i]] + v[i], f[i-1][j-2*w[i]]+2*v[i], ..., f[i-1][j-(k+1)*w[i]]+(k+1)*v[i])
// f[i][j - w[i]] + v[i] = max(f[i-1][j-w[i]] + v[i], f[i-1][j-2*w[i]]+2*v[i], ..., f[i-1][j-(k+1)*w[i]]+(k+1)*v[i])
// f[i][j - w[i]] + v[i] = max(装1个,...,装j/w[i]个)
优化的一维形式
// f[i][j]表示在考虑前i个物品后，背包容量为j条件下的最大价值
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= m; j++)
f[j] = max(f[j], f[j - w[i]] + v[i]); // max(不装物品i，装物品i(包含了装1个...装j/w[i]个的情况))
cout << f[m];
注意： 内层循环遍历容量时，一定要是顺序的，因为我们在优化后的二维形式中写道，二维数组中计算f[i][j]时，就是需要使用到左侧（同一层）的计算结果，对于一维形式来说就是要使用已经计算后的结果。一维形式中，如果逆序遍历容量，计算后面容量时，使用的就是没有计算过的结果，体现在二维中，使用的就是上一层的结果，这是不对的
01背包和完全背包问题的一维写法只差了一个遍历的顺序，01背包使用逆序遍历，完全背包使用顺序遍历，因为转换到二维形式，01背包只需要使用的是上一层的结果，完全背包需要使用当前层的结果
三、多重背包问题
01背包：物品i最多选1次
完全背包：物品i可以选无数次
多重背包：物品i最多选次
由于多重背包和完全背包都是可以物品选多次，所以状态转移方程也一样，只是多了一个限制条件
朴素写法如下：
f[i][j] = max(f[i-1][j], f[i-1][j-k*w[i]]+k*v[i]) // k为 0 -> s[i]
// f[i][j]表示在考虑前i个物品后，背包容量为j条件下的最大价值
int f[N][M];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
// 第三重循环遍历上述的椭圆，找最大值，分别表示物品i取几次
for (int k = 0; k <= j / w[i] && k <= s[i]; k++)
f[i][j] = max(f[i][j], f[i - 1][j - k * w[i]] + k * v[i]); // 注意和01背包的对比
cout << f[n][m];
我们试试使用完全背包问题的优化方式
上述max括号里总共s[i]+1项
考虑到：
max(放0个物品i，放1个物品i，放2个物品i，放s[i]个物品i)
上述max括号里总共s[i]+1项
上式变形得：
我们现在需要根据(3)式的结果，推出(1)式的结果，(1)式的后s[i]项和(3)式的前s[i]项完全一样，但我们无法使用(3)式中s[i]+1项的最大值，推出(3)式的前s[i]项的最大值，所以无法使用完全背包问题的优化方式
二进制优化
根据二进制表示，可以知道 可以由系数0和1线性组合出
，如果我们用k+1个新的物品，来代替多重背包的一个物品，使用01背包的方式计算出这k+1个物品选或不选
比如说S=200，我们使用1、2、4、8、16、32、64、73这8个物品，代替200这个物品，对这8个物品进行选或不选，我们就能表示出当前这个物品选[0,200]次
按照上面的，如果给我们一个一般的S，我们使用1、2、4、8、…、、C，组合出S，则我们有
，以及
也就是说，给我们一个物品最多选择S次，其实就是有S个这样的物品，我们可以将S个相同的物品，按照二进制的方式合并成个物品，再对这
个物品使用01背包算法，如果说原来有n类物品，每类物品有s个，总共
个，我们合并后，就变成了总共
个
// 读入物品个数时顺便打包
int k = 1; // 当前包裹大小
int idx = 0;
// n表示原来物品数量，循环读入n个物品的重量，价值，数量
for(int i = 1; i <= n; i++)
cin >> wi >> vi >> si; // 物品重量，物品价值，物品数量
// 开始用si个物品合成log2 si个物品
while (k <= si)
idx++ ; // 实际物品种数
w[idx] = wi * k;
v[idx] = vi * k;
si -= k;
k *= 2; // 二进制倍增包裹大小
if(si > 0)
idx++;
w[idx] = wi * si;
v[idx] = vi * si;
//现在的n表示合成后的物品数量
int n = idx;
for(int i = 1; i <= n; i++)
for(int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j-w[i]]+v[i]);
cout << f[m];
四、分组背包
完全背包问题是考虑第i个物品选几个，分组背包问题是考虑第i组物品选哪个或不选（每组物品中至多拿1个）
实际上是带有约束的01背包问题，状态计算为：
// n组物品
for(int i = 1; i <= n; i++)
cin >> s[i];
for(int j = 1; j <= s[i]; j++)
cin >> w[i][j] >> v[i][j];
// 遍历物品组数
for(int i = 1; i <= n; i++)
// 遍历背包容量
for (int j = m; j >= 1; j -- )
// 组内遍历物品
for(int k = 0; k <= s[i]; k++)
f[j] = max(f[j], f[j-w[i][k]]+v[i][k]);
cout << f[m] << endl;
背包问题（01背包，完全背包，多重背包）
...http://www.cnblogs.com/daoluanxiaozi/archive/2012/05/06/2486105.html 背包问题，经典有背包九讲。01背包 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些... 查看详情
01背包，完全背包，多重背包，混合背包
详见大牛背包九讲(下载地址：http://pan.baidu.com/s/1b9edXW)1//Class->物品种类，val->价值，room->所占空间，num->物品数量，Room->背包容量23#include<stdio.h>4constintmaxn=1e6;56intbag[maxn];7intRoom;89voidzero_one_bag( 查看详情
01背包完全背包多重背包
参考（都有些错误）：https://github.com/guanjunjian/Interview-Summary/blob/master/notes/algorithms/%E7%BB%8F%E5%85%B8%E7%AE%97%E6%B3%95/01%E8%83%8C%E5%8C%85.mdhttps://blog.csdn.net/na_beginning/article/details/6 查看详情
动态规划背包问题01背包完全背包多重背包
一、01背包有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。这是最基础的背包问题，总的来说就... 查看详情
动态规划之背包问题-01背包+完全背包+多重背包(代码片段)
01背包有n种不同的物品，每种物品分别有各自的体积v[i]，价值 w[i] 现给一个容量为V的背包，问这个背包最多可装下多少价值的物品。1for(inti=1;i<=n;i++)2for(intj=V;j>=v[i];j--)3dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//dp[V]为所求完全背包0... 查看详情
模板背包
（死亡）本文部分参照背包九讲（链接点这里）先看三道题：01背包，完全背包，混合背包请记住这个题面：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。有... 查看详情
01背包+完全背包+多重背包+单调队列(代码片段)
01背包代码：逆序更新intn,m,f[105][N],dp[N];voidfun1()for(inti=1;i<=n;i++)//物品ifor(intj=1;j<=m;j++)//容量jif(j<w[i])f[i][j]=f[i-1][j];elsef[i][j]=max(f[i-1] 查看详情
01完全多重背包模板
背包问题：背包总容量为W，有n件重量为weight[i],权值为value[i]的物品1、01背包：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。1voidZeroOnePack(intweight,intvalue)2{3for(intw=W;w>=weight;w--)4dp[w]=max(dp[w-weight]+value,... 查看详情
acwing（基础）---01背包和完全背包多重背包问题(代码片段)
初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候... 查看详情
背包问题专栏（01，完全，多重）(代码片段)
...的模板是套用了A.S.KirigiriKyouko的模板。请dalao见谅一、01背包有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和... 查看详情
背包九讲
目录第一讲 01背包问题第二讲 完全背包问题第三讲 多重背包问题第四讲 混合三种背包问题第五讲 二维费用的背包问题第六讲 分组的背包问题第七讲 有依赖的背包问题第八讲 泛化物品第九讲 背包问题问法的变化附：... 查看详情
动态规划多重背包问题(代码片段)
说明前面已经介绍完了01背包和完全背包，今天介绍最后一种背包问题——多重背包。这个背包，听起来就很麻烦的样子。别慌，只要你理解了前面的两种背包问题，拿下多重背包简直小菜一碟。如果没有看过前两篇01背包和完... 查看详情
背包问题：0-1背包完全背包和多重背包
背包问题泛指以下这一种问题：给定一组有固定价值和固定重量的物品，以及一个已知最大承重量的背包，求在不超过背包最大承重量的前提下，能放进背包里面的物品的最大总价值。这一类问题是典型的使用动态规划解决的问... 查看详情
luogu1833樱花
背包问题小合集01背包完全背包多重背包混着来对于01背包：把它想象成最大物品数为1的多重背包对于完全背包：把它想象成最大物品数为m/w[i]的多重背包对于多重背包：把它想象成。。。等等这本来就是个多重背包数据比较水... 查看详情
2018.02.06(背包专卖店)
2018.02.06背包专卖店系列 今天我们学习了背包问题，浏览了一个规模宏大的背包专卖店。。。领略了许许多多的背包。01背包完全背包多重背包混合背包部分背包二维费用背包分组背包有依赖背包1.01背包思路：。。。核... 查看详情
背包专题c-thetroubleofxiaoqianhdu3591混合背包：多重背包+完全背包
InthecountryofALPC,Xiaoqianisaveryfamousmathematician.Sheisimmersedincalculate,andshewanttousetheminimumnumberofcoinsineveryshopping.(Thenumbersoftheshoppingincludethecoinsshegavethestoreandthestoreba 查看详情
动态规划问题3--多重背包(代码片段)
多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情
动态规划问题3--多重背包(代码片段)
多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情