背包问题（01背包，完全背包，多重背包）

关键词：

01背包

 

不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.

死亡骑士:"我要买道具!"

地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个."

死亡骑士:"好的,给我一个血瓶."

说完他掏出那张N元的大钞递给地精商人.

地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."

死亡骑士:"......你妹"

死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.

现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.

上面就是一个01背包问题。上面的问题可以描述为： 

有n个物品，每个物品的重量为weight[i]，每个物品的价值为value[i]。现在有一个背包，它所能容纳的重量为total，问：当你面对这么多有价值的物品时，你的背包所能带走的最大价值是多少？

思路：每个物品无非是装入背包或者不装入背包，那么就一个一个物品陆续放入背包中。可以有

tab[i][j] = max(tab[i-1][j-weight[i]]+value[i],tab[i-1][j]) ({i,j|0<i<=n,0<=j<=total})

其中i表示放第i个物品，j表示背包所容纳的重量，那么tab[i-1][j-weight[i]]+value[i]表示放入第i物品，刚开始接触会有疑问，tab[i-1][j-weight[i]]这个值，可以这样理解：tab[i-1][j]为装到上一个物品在背包j容量时的最佳值，那么如果我要求在j容量的时候放入现在的i物品的价值，那么是不是要先得到容量为（j-weight[i]）时候的价值，即先得到 tab[i-1][j-weight[i]] ，所以 tab[i-1][j-weight[i]]+value[i] 为放入第i物品的价值； tab[i-1][j] 就是不放入第i个物品。

动态规划的思维就在这里体现了，即tab[i-1][j]是tab[i][j]的最优解（我觉得上面的思路讲解较容易理解）。

例子：5个物品，（重量，价值）分别为：（5，12），（4，3），（7，10），（2，3），（6，6）。

背包容量	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5物品	0	0	0	0	0	0	6	12	12	15	15	18	22	22	25	25
4物品	0	0	3	3	3	3	3	12	12	15	15	18	22	22	25	25
3物品	0	0	0	0	0	0	0	12	12	15	15	15	22	22	22	22
2物品	0	0	0	0	3	12	12	12	12	15	15	15	15	15	15	15
1物品	0	0	0	0	0	12	12	12	12	12	12	12	12	12	12	12

故有： 

完全背包

不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.

死亡骑士:"我要买道具!"

地精商人:"我们这里有三种道具,血瓶150块无限个,魔法药200块无限个,无敌药水350块无限个."

死亡骑士:"好的,给我一个血瓶."

说完他掏出那张N元的大钞递给地精商人.

地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."

死亡骑士:"......你妹"

死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.

现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.

上面的魔兽场景描述跟上面的只有小小的差异，就是物品有一个变为了无限个，这就是完全背包问题。完全背包问题可以描述为：

有n种物品，每种物品有无限个，每个物品的重量为weight[i]，每个物品的价值为value[i]。现在有一个背包，它所能容纳的重量为total，问：当你面对这么多有价值的物品时，你的背包所能带走的最大价值是多少？

有了上面01背包的式子，这题会变的容易理解很多，只是这个式子要有小小的改动。01背包在二维数组上操作，就是为了防止一个物品被放入多次的情况。因此一维数组可以满足完全背包的问题。如下：

tab[j] = max(tab[j-weight[i]]+value[i],tab[j]);({i,j|0<i<=n,0<=j<=total})

根本就是一样的，只不过物品可以被放多次。

背包容量	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
i物品	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X

故有： 

多重背包

不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.

死亡骑士:"我要买道具!"

地精商人:"我们这里有三种道具,血瓶150块a个,魔法药200块b个,无敌药水350块c个."

死亡骑士:"好的,给我一个血瓶."

说完他掏出那张N元的大钞递给地精商人.

地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."

死亡骑士:"......你妹"

死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.

现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.

上面的魔兽场景描述跟上面的又有了小小的差异，就是物品有一个变为了有限个，问题也就变成了多重背包问题。

有n种物品，每种物品有amount[i]个，每个物品的重量为weight[i]，每个物品的价值为value[i]。现在有一个背包，它所能容纳的重量为total，问：当你面对这么多有价值的物品时，你的背包所能带走的最大价值是多少？

多重和完全更接近，多了数量的限制，用一个count[n]计数数组来限制物品i的数量。当放入第i个物品是较优值的时候，count[i]=count[j-weight[i]]+1（j 的含义请查看代码）;这样做是因为，放入第i个物品的操作是基于count[j-weight[i]]放入的，所以当count[i-weight[i]]>=amount[i]时，就要阻止放入即便放入第i个物品是较优值。 故有：

动态规划背包问题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背包模板题完全背包... 查看详情

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,... 查看详情

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( 查看详情

acwing（基础）---01背包和完全背包多重背包问题(代码片段)

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

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，完全，多重）(代码片段)

...的模板是套用了A.S.KirigiriKyouko的模板。请dalao见谅一、01背包有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和... 查看详情

动态规划多重背包问题(代码片段)

说明前面已经介绍完了01背包和完全背包，今天介绍最后一种背包问题——多重背包。这个背包，听起来就很麻烦的样子。别慌，只要你理解了前面的两种背包问题，拿下多重背包简直小菜一碟。如果没有看过前两篇01背包和完... 查看详情

背包问题：0-1背包完全背包和多重背包

背包问题泛指以下这一种问题：给定一组有固定价值和固定重量的物品，以及一个已知最大承重量的背包，求在不超过背包最大承重量的前提下，能放进背包里面的物品的最大总价值。这一类问题是典型的使用动态规划解决的问... 查看详情

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] 查看详情

动态规划问题3--多重背包(代码片段)

多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情

动态规划问题3--多重背包(代码片段)

多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情

模板背包

（死亡）本文部分参照背包九讲（链接点这里）先看三道题：01背包，完全背包，混合背包请记住这个题面：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。有... 查看详情

luogu1833樱花

背包问题小合集01背包完全背包多重背包混着来对于01背包：把它想象成最大物品数为1的多重背包对于完全背包：把它想象成最大物品数为m/w[i]的多重背包对于多重背包：把它想象成。。。等等这本来就是个多重背包数据比较水... 查看详情

混合背包（背包03）

将01背包，完全背包，和多重完全背包问题结合起来，那么就是混合三种背的问题根据三种背包的思想，那么可以得到混合三种背包的问题可以这样子求解　　for(inti=1;i<=N;++i) 　　　　if(第i件物品是01背包) 　　　　　　zeroOneP... 查看详情

01背包模板全然背包and多重背包（模板）

...g.com/tanky-woo/archive/2010/07/31/121803.html模版就直接贴代码：01背包模板：/*01背包问题01背包问题的特点是，">每种物品仅有一件。能够选择放或不放。01背包问题描写叙述：有N件物品和一个容量为V的背包 查看详情

混合背包问题(代码片段)

原题链接如果s为0，那么是完全背包问题，用完全背包的方法求解如果s为-1，那么是01背包问题，把它当做数量为1的特殊的多重背包（其实它就是特殊的多重背包问题）s为某个数，那么就是普通的多重... 查看详情