01背包经典例题： 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式 输出一个整数，表示最大价值。
数据范围 0<N,V≤1000 0<vi,wi≤1000 输入样例 4 5 1 2 2 4 3 4 4 5 输出样例： 8
朴素版解法：二维空间解法
**每件物品只能选一次，对于每种物品，我们有两种选择 1.不选 -> dp[i][j]=dp[i-1][j] 等于选前i-1个物品，空间为j情况下的最优解 2.选 -> dp[i][j]=dp[i-1][j-v[i]]+w[i] 如果选的话，前i-1个物品的体积最多为j-v[i] **
在这两种情况中取较大值即可，即为当前情况的最优解，我们的每一步都是从上一步的最优解转移过来，所以可以保证最后的结果一定是最优解
板子：
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int maxn = 1005; int dp[maxn][maxn];//dp[i][j]表示前i个商品，背包容量是j的情况下的最大价值 int w[maxn]; int v[maxn]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++) scanf("%d%d",&v[i],&w[i]); for(int i = 1;i <= n;i++){ for(int j = 0;j <= m;j++){ dp[i][j] = dp[i - 1][j]; if(j >= v[i]) dp[i][j] = max(dp[i][j],dp[i-1][j- v[i]] + w[i]); } } printf("%d\n",dp[n][m]); return 0; }解法二：滚动数组优化：（实际上只需要一个数组）
状态转移每次只与上一层有关，所以用一个一维数组就可以
转移方程：dp[i]=max(dp[i],dp[i-v[i]]+w[i]) 其实就相当于二维中的 dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i])
所以第二层循环需要从大到小循环， 因为若是继续从小到大循环，后面算的时候，用的是这一层已经算过的数据，就变成dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]) ，（这正好是完全背包一维的解法，每个物品可以选无限次）而从大到小算的话一定用的是上一层的状态
板子：
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int maxn = 1005; int dp[maxn]; int main(){ int n,m; scanf("%d%d",&n,&m); int v,w; for(int i = 1;i <= n;i++){ scanf("%d%d",&v,&w); for(int j = m;j >= v;j--){ dp[j] = max(dp[j],dp[j - v] + w); } } printf("%d\n",dp[m]); return 0; }注：这时的dp[i]表示空间<=i的最大价值，所以最后直接输出dp[m]即可，这与初始化有关，因为dp数组在主函数外定义，初始值均为0，所以如果存在一个k<m 使得空间最大为k的情况下dp[k]有最大价值，那么dp[m]一定可以从k这个状态转移过来—即dp[m]一定是最大值。
若题目要求装满背包，即将物品恰装入一个容量为m的背包中，只需要将初始化条件改一改即可，----将dp数组初始化为负无穷，dp[0]=0，即可确保状态一定是从0转移过来的。
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。 第 i 种物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些**物品的总体积不超过背包容量，且总价值最大。**输出最大价值。
输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式 输出一个整数，表示最大价值。
数据范围 0<N,V≤1000 0<vi,wi≤1000 输入样例 4 5 1 2 2 4 3 4 4 5 输出样例： 10
朴素版解法：二维空间解法
也是两种选择，选或不选，只不过每个物品可以选无限次，在01的基础上把 dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]) 改为 dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i])即可
板子：
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int maxn = 1005; int dp[maxn][maxn]; int w[maxn]; int v[maxn]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++) scanf("%d%d",&v[i],&w[i]); for(int i = 1;i <= n;i++){ for(int j = 0;j <= m;j++){ dp[i][j] = dp[i - 1][j]; if(j >= v[i]) dp[i][j] = max(dp[i][j],dp[i][j- v[i]] + w[i]); } } printf("%d\n",dp[n][m]); return 0; }优化空间版解法： 转移方程为dp[j]=max(dp[j],dp[j-v[i]]+w[i]) 第二层从小到大循环，原因参见01的一维
板子：
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int maxn = 1005; int dp[maxn]; int main(){ int n,m; scanf("%d%d",&n,&m); int v,w; for(int i = 1;i <= n;i++){ scanf("%d%d",&v,&w); for(int j = v;j <= m;j++){ dp[j] = max(dp[j],dp[j - v] + w); } } printf("%d\n",dp[m]); return 0; }有 N 种物品和一个容量是 V 的背包。 **第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。**求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。 接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。 数据范围 0<N,V≤100（小数据范围） 0<vi,wi,si≤100 输入样例 4 5 1 2 3 2 4 1 3 4 3 4 5 2 输出样例： 10
思路：是01背包的延伸，就不说二维做法了，跟上面差不多。直接贴一维做法。 01背包是选或不选 ： dp[j]=max(dp[j],dp[j-v[i]]+w[i]) 多重背包是选0个，1个，2个…s[i]个 即dp[j]=max(dp[j],dp[j - v[i] * k]+w[i] * k) k=1,2,3,…s[i] 那么再加一层循环表示选多少个就可以了 因为是01背包的扩展，所以第二层循环应从大到小循环
板子：
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int dp[maxn]; int main(){ int n,m; int v[maxn],w[maxn],s[maxn]; scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++){ scanf("%d%d%d",&v[i],&w[i],&s[i]); } memset(dp,0,sizeof(dp)); for(int i = 1;i <= n;i++){ for(int j = m;j >= v[i];j--){ for(int k = 1;k <= s[i];k++){ if(j >= k * v[i]) dp[j] = max(dp[j],dp[j - k * v[i]] + k * w[i]); else break; } } } printf("%d\n",dp[m]); return 0; }方法二：二进制优化做法：
有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。 输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。 接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。 输出格式 输出一个整数，表示最大价值。 数据范围 0<N≤1000（大数据范围） 0<V≤2000 0<vi,wi,si≤2000 提示： 本题考查多重背包的二进制优化方法。 输入样例 4 5 1 2 2 4 1 3 4 3 4 5 2 输出样例： 10
**思路：**这道题的数据范围如果用三层循环的话是达到了1e9，所以必须优化它。其实可以把它转化为一个01背包的问题。每个物品有s件，我们可以把它差分成s份，每份物品当做不同的个体，即只能选一次，这就转化为了01背包物品，但是这样的话，物品个数变成了1000*2000=2e6，再循环一层空间的话，还是1e9的复杂度。
那么继续优化，一个物品的数量是s的话，只要把s拆分成一些数字，使它们能够表示出1-s中任意一个数字，就可以，没必要把它拆成s个1。
那么这样的数字最少需要多少个呢？****最少需要log(s)个，向上取整。
比如7，它最少需要3个数字来表示：
即 1（2^0=1 ）， 2（2^1=2）， 4（2^2=4）。
原因：每个数字有2种可能选或不选，那么可以表示的不同数字个数就是 2 * 2 * 2 = 8。但是还需要注意一个问题，就是有些数字可能能够表示出来一些大于s的数字，但是这件物品最多只有s件，那么就需要特殊处理一下最后一个数。
比如10，若用1，2， 4， 8表示，可能会表示出来大于10的数字，例如：4+8=12。那么如果最后一个数字加上前面数的总和会大于s，就将它替换为剩下的物品个数，即将8替换为3，这时正好能表示出1-s所有的数，-> 1, 2，4可以表示7以内的所有数，这些数加上3就可以表示10以内的所有数啦。
注：如果拆分成log(s)个的话，时间复杂度就变为1000 * log(2000) * 2000 = 2e7，是可以通过的~
板子：
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int dp[maxn]; int v[maxn],w[maxn];//注意数据范围确定是int还是long long int main(){ int n,m; scanf("%d%d",&n,&m); int vv,ww,s; int k = 1; for(int i = 1;i <= n;i++){ scanf("%d%d%d",&vv,&ww,&s); for(int i = 1;i <= s;i = i * 2){ // 二进制每一位枚举. //注意要从小到大拆分 v[k] = vv * i;//合成一个大的物品的体积 w[k] = ww * i;//合成一个大的物品的价值 k++; s = s - i;//减去拆分出来的 } if(s){ /*判断是否会有余下的部分. 就好像我们某一件物品为13,显然拆成二进制为1,2,4. 我们余出来的部分为6,所以需要再来一份.*/ v[k] = vv * s; w[k] = ww * s; k++; } } for(int i = 1;i < k;i++){ for(int j = m;j >= v[i];j--){ dp[j] = max(dp[j],dp[j - v[i]] + w[i]); } } printf("%d\n",dp[m]); return 0; }题目三：多重背包终极版 所谓的look 哈哈哈！！
有 N 种物品和一个容量是 V 的背包。 物品一共有三类： 第一类物品只能用1次（01背包）； 第二类物品可以用无限次（完全背包）； 第三类物品最多只能用 si 次（多重背包）； 每种****体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。 输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。 接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。 si=−1 表示第 i 种物品只能用1次； si=0 表示第 i 种物品可以用无限次； si>0 表示第 i 种物品可以使用 si 次；
输出格式 输出一个整数，表示最大价值。 数据范围 0<N,V≤1000 0<vi,wi≤1000 −1≤si≤1000−1
输入样例 4 5 1 2 -1 2 4 1 3 4 0 4 5 2 输出样例： 8
**思路：**是一个前三种背包问题的综合，如果明白了前面的，就很简单了，只需要判断一下类型，如果是多重背包，将它转换为01背包插入数组当中，然后按着不同类型的处理方式去遍历空间大小即可。
板子：
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int dp[maxn]; int v[maxn],w[maxn],s[maxn];//注意数据范围确定是int还是long long int main(){ int n,m; scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++){ scanf("%d%d%d",&v[i],&w[i],&s[i]); if(s[i] == -1) s[i] = 1;01背包相当于物品件数为1的多重背包 } for(int i = 1;i <= n;i++){ if(s[i] == 0){//完全背包，按照完全背包的方式，从小到大枚举体积 for(int j = v[i];j <= m;j++){ dp[j] = max(dp[j],dp[j - v[i]] + w[i]); } } else{//多重背包进行二进制优化 for(int k = 1;k <= s[i];s[i] -= k,k *= 2){ for(int j = m;j >= k * v[i];j--){ dp[j] = max(dp[j],dp[j - k * v[i]] + k * w[i]); } } for(int j = m;j >= s[i] * v[i];j--){ dp[j] = max(dp[j],dp[j - s[i] * v[i]] + s[i] * w[i]); } } } printf("%d\n",dp[m]); return 0; }（升级版01背包）换句话说只是在01背包的基础上多了一层限制
有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。 每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。 输出最大价值。 输入格式 第一行两个整数，N，V, M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。 接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。 输出格式 输出一个整数，表示最大价值。 数据范围 0<N≤1000 0<V,M≤100 0<vi,mi≤100 0<wi≤1000 输入样例 4 5 6 1 2 3 2 4 4 3 4 5 4 5 6 输出样例： 8
**思路：**这个题也很简单，就是在01背包的基础上加了一维重量，枚举的时候多一层循环就行了。因为是01背包的变形，所以重量和体积枚举的时候都从大到小枚举。****(需要注意的是有时候并不是01背包，也有可能是完全背包)
题目中明确指出每种怪有无数个————>完全背包
板子：
#include<bits/stdc++.h> using namespace std; const int maxn = 1005; int dp[maxn][maxn]; int main(){ int n,V,M; int v,w,m; scanf("%d%d%d",&n,&V,&M); for(int i = 1;i <= n;i++){ scanf("%d%d%d",&v,&m,&w); for(int j = V;j >= v;j--){ for(int k = M;k >= m;k--){ dp[j][k] = max(dp[j][k],dp[j - v][k - m] + w); } } } printf("%d\n",dp[V][M]); return 0; }有 N 组物品和一个容量是 V 的背包。 每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。 输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。 接下来有 N 组数据： 每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量； 每组数据接下来有 Si行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。 数据范围 0<N,V≤100 0<Si≤100 0<vij,wij≤100 输入样例 3 5 2 1 2 2 4 1 3 4 1 4 5 输出样例： 8
思路：和多重背包有一些类似，多重背包是每个物品有si件，可以选0,1，2…si件。而分组背包是不选，选第1个，或第2个或第3个…或第si个，都有si+1种决策方式，即使用三层循环即可解决。没有优化方式。 板子：
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int dp[maxn]; int v[maxn],w[maxn]; int main(){ int n,m,s; scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++){ scanf("%d",&s); for(int k = 1;k <= s;k++) scanf("%d%d",&v[k],&w[k]); for(int j = m;j >= 0;j--){ for(int k = 1;k <= s;k++){ if(j >= v[k]) dp[j] = max(dp[j],dp[j - v[k]] + w[k]); } } } printf("%d\n",dp[m]); return 0; }有 N 个物品和一个容量是 V 的背包。 物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。 如下图所示：
如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。 每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N1…N。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式 第一行有两个整数 N，V用空格隔开，分别表示物品个数和背包容量。 接下来有 N 行数据，每行数据表示一个物品。 第 i行有三个整数 vi,wi,pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。 如果 pi=−1，表示根节点。 数据保证所有物品构成一棵树。
输出格式 输出一个整数，表示最大价值。
数据范围 1≤N,V≤100 1≤vi,wi≤100 父节点编号范围： 内部结点：1≤pi≤N; 根节点 pi=−1;
输入样例 5 7 2 3 -1 2 2 1 3 5 1 4 7 2 3 6 2 输出样例： 11
思路：其实有依赖的背包问题和树形dp很类似，它把树形dp和分组背包结合到了一起。
选一个物品必须要选择它的父节点，那么反过来，父节点选择子节点，一定会选择价值最大的那一分支。那么就可以先递归算出子树的每一个体积对应的最大价值，然后进行分组背包，求出最大值即可。
需要注意的是，我们选择了子节点，就必须选择当前节点，那么最后需要把父节点的位置空出来。（把所有已算完的体积更新一下，在里面加上父节点这一物品）
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。------>（01背包） 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最优选法的方案数。注意答案可能很大，请输出答案模 10^9+7 的结果。
输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i件物品的体积和价值。
输出格式 输出一个整数，表示方案数 模 10^9+7的结果。
数据范围 0<N,V≤1000 0<vi,wi≤1000
输入样例 4 5 1 2 2 4 3 4 4 6 输出样例： 2
思路：在原来01背包的基础上加一个表示方案数的数组即可。注意初始化，如果只把num[0]赋值成1，那么需要把对应的01背包转化为体积恰好是j的情况下的最大价值。最后找出最大价值，将此价值对应的所有体积的方案数加上即可。
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。-------->01背包 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出字典序最小的方案。这里的**字典序是指：所选物品的编号所构成的序列。**物品的编号范围是 1…N。
输入格式 第一行两个整数，N，V 用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式 输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。 物品编号范围是 1…N。
数据范围 0<N,V≤1000 0<vi,wi≤1000
输入样例 4 5 1 2 2 4 3 4 4 6
输出样例： 1 4 思路：因为方案可能有很多种，题目要求输出字典序最小的，那么就倒着枚举物品种类，贪心思想，确保序号小的能优先选择。最后输出一下可行的转移路径就行了。
