问题一：01背包
题目：
【题目描述】
一个旅行者有一个最多能装 M 公斤的背包，现在有 n件物品，它们的重量分别是W1，W2，...,Wn它们的价值分别为C1,C2,...,Cn求旅行者能获得最大总价值。
【输入】
第一行：两个整数，MM(背包容量，M≤200)和NN(物品数量，N≤30)；
第2..N+12..N+1行：每行二个整数Wi，CiWi，Ci，表示每个物品的重量和价值。
【输出】
仅一行，一个数，表示最大总价值。
【输入样例】
10 4 2 1 3 3 4 5 7 9
【输出样例】
12
这类问题就是01背包问题，是dp背包中的最简单的一种
状态转移方程：f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i])
即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
将前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]（来自百度）
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #include<map> #include<string> #include<cstring> using namespace std; const int maxn=999999999; const int minn=-999999999; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int f[1005][1050],c[1050],w[1050],m,n; int main() { cin>>m>>n; for(int i=1; i<=n; ++i) { cin>>w[i]>>c[i]; } for(int i=1; i<=n; ++i) { for(int v=m; v>0; v--) { if(w[i]<=v) { f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]); } else { f[i][v]=f[i-1][v]; } } } cout<<f[n][m]; return 0; }
问题来了开一个二维数组是不是有点浪费空间（想想蛇形填数那个题，二维数组开不到那么大，就GG了）所以只需要用f[v]表示重量不超过v的最大价值就OK了
f[i]=max(f[v],f[v-c[i]]+w[i])
为什么可以从二维变成一维的呢？
因为f[i][v]是从f[i-1][v],f[i-1][v-c[i]]+w[i])得出的，当我将v从m开始向前枚举时，每次都会更新当前的第i个物体的更新，只依赖于第i-1个的物体的结果所以可以用滚动数组，每次只存i和i-1时候的值 第i个物体在容积为j状态的更新，只依赖i-1物体容量里j-w[i]的状态的结果所以，从后面开始向前更新，则求j位置时候，j-w[i]的值依旧为i-1时候的值
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #include<map> #include<string> #include<cstring> using namespace std; const int maxn=999999999; const int minn=-999999999; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int f[1050],c[1050],w[1050],m,n; int main() { cin>>m>>n; for(int i=1; i<=n; ++i) { cin>>w[i]>>c[i]; } for(int i=1; i<=n; ++i) { for(int v=m; v>0; v--) { if(w[i]<=v) { f[v]=max(f[v],f[v-w[i]]+c[i]); } else { f[v]=f[v]; } } } cout<<f[m]; return 0; }
01背包为什么枚举v时要逆序？
为了避免要使用的子状态收到影响。（很重要!）
问题二：完全背包
【题目描述】
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
【输入】
第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；
第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。
【输出】
仅一行，一个数，表示最大总价值。
【输入样例】
10 4 2 1 3 3 4 5 7 9
【输出样例】
max=12
特点：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
[思路]：这个问题非常类似于01背包，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……。仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程:
f[i][j] = max{f[i][j],f[i-1][j - k * c[i]] + k * w[i]}(0<=k*c[i]<=v)
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #include<map> #include<string> #include<cstring> using namespace std; const int maxn=999999999; const int minn=-999999999; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int w[1005],c[1005],f[1005][1005],m,n; int main() { cin>>m>>n; for(int i=1; i<=n; ++i) { cin>>w[i]>>c[i]; } for(int i=1; i<=n; ++i) { for(int v=1; v<=m; ++v) { if(v<w[i]) { f[i][v]=f[i-1][v]; } else { if(f[i-1][v]>f[i][v-w[i]]+c[i]) { f[i][v]=f[i-1][v]; } else { f[i][v]=f[i][v-w[i]]+c[i]; } } } } cout<<"max="<<f[n][m]; return 0; }
同上，和01背包一样开二维数组浪费空间
注意v要从前往后枚举，为什么?
在01背包问题里面，我们逆序遍历V是为了保证f[i]始终是i-1物品推出的，从而保证每种物品只用一次。而完全背包问题里面我们就可以正序遍历，这样就可以在一次遍历f[V]中考虑第i种物品的所有拿法。至于为什么这样就能求出所有的，我会在明天做一个解释
解释开始：因为第i种物品一旦出现，原来没有第i种物品的情况下可能有一个最优解，现在第i种物品 出现了，而它的加入有可能得到更优解，所以之前的状态需要进行改变，故需要正序。
直接用一组例子来解释：
样例：
10 4 2 1 3 3 4 5 7 9
运行过程f数组内：
0
0 0
0 0 0
0 0 1 0
0 0 1 1 0
0 0 1 1 2 0
0 0 1 1 2 2 0
0 0 1 1 2 2 3 0
0 0 1 1 2 2 3 3 0
0 0 1 1 2 2 3 3 4 0
0 0 1 1 2 2 3 3 4 4 0
0 0 1 1 2 2 3 3 4 4 5 0
0 0 1 3 2 2 3 3 4 4 5 0
0 0 1 3 3 2 3 3 4 4 5 0
0 0 1 3 3 4 3 3 4 4 5 0
0 0 1 3 3 4 6 3 4 4 5 0
0 0 1 3 3 4 6 6 4 4 5 0
0 0 1 3 3 4 6 6 7 4 5 0
0 0 1 3 3 4 6 6 7 9 5 0
0 0 1 3 3 4 6 6 7 9 9 0
0 0 1 3 5 4 6 6 7 9 9 0
0 0 1 3 5 5 6 6 7 9 9 0
0 0 1 3 5 5 6 8 7 9 9 0
0 0 1 3 5 5 6 8 10 9 9 0
0 0 1 3 5 5 6 8 10 10 9 0
0 0 1 3 5 5 6 8 10 10 11 0
0 0 1 3 5 5 6 8 10 10 12 0
liuzitong大佬的解释：
背包容量为5
有1个物品,体积为2,价值为3(这么简单的例子不是因为我懒)
从5开始呢?
f[5]=f[5-2]+3;
f[4]=f[4-2]+3;
f[3]=f[3-2]+3;
f[2]=f[2-2]+3;
1和0不行
可以看出,从5到2,关系分别是
由3推5
由2推4
由1推3
由0推2
从一开始推出来的5开始没有被用过的再被利用
从1开始呢?
1和0不行
f[2]=f[2-2]+3;
f[3]=f[3-2]+3;
f[4]=f[4-2]+3;
f[5]=f[5-2]+3;
可以看出,从5到2,关系分别是
由0推2
由1推3
由2推4
由3推5
可以看出:
由0推出的2又在推4的时候用到了,这就实现了完全背包
最终答案就是12（wc写死我了，好多啊）
如有bug请评论指明。
优化代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #include<map> #include<string> #include<cstring> using namespace std; const int maxn=999999999; const int minn=-999999999; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int w[1005],c[1005],f[1005],m,n; int main() { cin>>m>>n; for(int i=1; i<=n; ++i) { cin>>w[i]>>c[i]; } for(int i=1; i<=n; ++i) { for(int v=w[i]; v<=m; ++v) {//注意v从w[i]开始枚举也可从1开始枚举 if(f[v-w[i]]+c[i]>f[v]) f[v]=f[v-w[i]]+c[i]; } } cout<<"max="<<f[m]; return 0; }
问题三：多重背包
【题目描述】
为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
【输入】
第一行二个数n(n≤500)，m(m≤6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。
接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可），其中v≤100，w≤1000，s≤10。
【输出】
一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。
【输入样例】
5 1000 80 20 4 40 50 9 30 50 7 40 30 6 20 20 1
【输出样例】
1040
特点：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
转化为01背包问题：
朴素方法：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度是O(V*Σn[i])。 Σ表示把n[i]加起来，就是说两层循环的复杂度
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #include<map> #include<string> #include<cstring> using namespace std; const int maxn=999999999; const int minn=-999999999; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int v[6666],w[6666],s[6666],f[6666],n,m; int main() { cin>>n>>m; for(int i=1; i<=n; ++i) { cin>>v[i]>>w[i]>>s[i]; } for(int i=1; i<=n; ++i) {//枚举i for(int j=m; j>=0; j--) {//枚举空间（容量） for(int k=1; k<=s[i]; ++k) {//枚举选的数量 if(j-k*v[i]<0) break;//装不下了就退出 else { f[j]=max(f[j],f[j-k*v[i]]+k*w[i]); } } } } cout<<f[m]; return 0; }
优化版：
利用二进制拆分。复杂度O(VΣlog n[i])
考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。（来自一本通）
拆分过程：
cin>>x>>y>>z; while(z>=sum) { //sum是指数 v[++len]=x*sum; w[len]=y*sum; z-=sum; sum*=2; } v[++len]=x*z; w[len]=y*z;
完整代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #include<map> #include<string> #include<cstring> using namespace std; const int maxn=999999999; const int minn=-999999999; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int v[6666],w[6666],s[6666],f[6666],n,m; int main() { cin>>n>>m; int len=0; for(int i=1; i<=n; ++i) { int x,y,z; int sum=1; /*x是价格，y是价值,z是数量*/ cin>>x>>y>>z; while(z>=sum) { //sum是指数 v[++len]=x*sum; w[len]=y*sum; z-=sum; sum*=2; } v[++len]=x*z; w[len]=y*z; } for(int i=1; i<=len; ++i) { for(int j=m; j>=v[i]; j--) { f[j]=max(f[j],f[j-v[i]]+w[i]); } } cout<<f[m]; return 0; }
问题四：分组背包
问题
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
思路
这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[v]表示前k组物品花费费用v能取得的最大价值
for 所有的组k for v=V..0 for 所有的i属于组k f[v]=max{f[v],f[v-w[i]]+c[i]}
注意这里的三层循环的顺序，“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。
题目
代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #include<map> #include<string> #include<cstring> #define ll long long int #define MAXN 1005 using namespace std; const int maxn=999999999; const int minn=-999999999; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int a[MAXN][MAXN],f[MAXN],c[MAXN],w[MAXN],sum[MAXN]; int main() { int n,m; cin>>m>>n; int zu=0; for(int i=1;i<=n;++i) { int p; cin>>w[i]>>c[i]>>p; sum[p]++; zu=max(zu,p); a[p][sum[p]]=i; } for(int i=1;i<=zu;++i) { for(int j=m;j>=0;--j) { for(int k=1;k<=sum[i];++k) { if(j>=w[a[i][k]]) f[j]=max(f[j],f[j-w[a[i][k]]]+c[a[i][k]]); } } } // cout<<f[m]; int ans=f[m]; cout<<ans;//ac return 0; }
问题五：有依赖的背包问题
例题：
思路：
这类问题是01背包的变形。所有的物品分为两类，一类是主件，另一类是附件，每一个附件都有它的主件，选取它的主件之后才能选取附件。
详见：我的另一篇博客