一般的背包问题：
每种物品有一个价格W和体积V，你现在有一个容积为V的背包。问你怎么装使背包的价值和最大。
01背包
多种物品，每个物品只有一个，求能或得的最大总价值。
如果我们不选第i件物品，那我们就相当于用 i-1 件物品，填充了体积为V的背包所得到的最优解。
当我们选第i件物品时，就相当于用i-1的物品，填充v - c[i]/的背包所得到的最优解。
用f[i][v]表示用i件物品填充体积为V的背包所得到的价值。
那么方程式就是：
1 f[i][v] = max(f[i-1][v] , f[i-1][v-c[i]] + w[i])
一维的就是
1 f[j] = max(f[j],f[j-c[i] + w[i])
显而易见，我们f[j] 只会被以前的状态影响。
如果我们顺序枚举，就可能会被前面的状态影响掉。
那我们考虑倒叙枚举，这样f[j] 不会被之前的状态影响，且我们更新的话也不会影响其他位置的状态
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 using namespace std; 5 int f[1001],w[1001],v[1001]; 6 int main(){ 7 int n,m; 8 scanf("%d%d",&n,&m); 9 for(int i = 1;i <= n; i++){ 10 scanf("%d%d",&w[i],&c[i]); 11 } 12 for(int i = 1; i <= n; i++){ 13 for(int j = m; j >= w[i]; j--){ 14 f[j] = max(f[j],f[j-w[i]]+v[i]); 15 } 16 } 17 prinf("%d",f[m]); 18 return 0; 19 }
水题——>采药
完全背包
每个物品有无限个，可重复选取；
转移方程就是
1 f[i][v] = max(f[i-1][v] ,f[i-1][j-k*c[i]] + k * w[i])
跟01背包类似，我们可以把它给成一维的，只不过要正着枚举。
1 for(int i = 1;i <= n; i++){ 2 for(int j = w[i]; j <= m; j++){ 3 f[j] = max(f[j] , f[j-w[i]]+v[i]); 4 } 5 }
多重背包
跟01背包类似，只不过他每种物品有k个，而不是1个
1.转化为01背包
我们可以把每件物品选k次，转换为有k个相同的物品，每个物品选一次
然后就可以套用01背包
时间复杂度O(nwΣki)
2.二进制优化
我们仍考虑转化为01背包 ，我们可以对k的拆分入手
对于一个数k 可以根据二进制拆成2^j相加的形式。
但我们要保留1个物品，然后在对其他的k-1个进行拆分
例如
1 cnt = 0;//当前的物品数
2 for(int i = 1; i <= m; i++){
3 int c = 1;
4 scanf("%d%d",&p,&vv,&k);
5 while(k - c > 0){//打包k-1个物品
6 k -= c;
7 w[++cnt] = c * p;
8 v[cnt = c * vv;
9 c *= 2;
10 }
11 w[++cnt] = p * k；//打包剩下的那1个物品
12 v[cnt] = k * vv;
13 }
3.单调队列优化
我不会QAQ，但也不常考。
有兴趣的可以看一下链接
习题 ： P1776 宝物筛选
二维费用背包
很明显的01背包问题，但选一个物品会消耗两种价值。
我们可以考虑再开一维数组，同时转移两个价值（其他背包同理）
但不能够再开一维数组存物品编号，因为容易MLE
1 for (int k = 1; k <= n; k++) { 2 for (int i = m; i >= mi; i--) // 对经费进行一层枚举 3 for (int j = t; j >= ti; j--) // 对时间进行一层枚举 4 dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1); 5 }
三倍经验
分组背包
水题 ——> P1757 通天之分组背包
就是讲物品分组，每组物品只能选一个。
我们可以把在所有物品中选一件，变成从当前组中选一件，直接跑01背包就okk了
1 for (int k = 1; k <= ts; k++) // 循环每一组
2 for (int i = m; i >= 0; i--) // 循环背包容量
3 for (int j = 1; j <= cnt[k]; j++) // 循环该组的每一个物品
4 if (i >= w[t[k][j]])
5 dp[i] = max(dp[i], dp[i - w[t[k][j]]] + c[t[k][j]]); // 像0-1背包一样状态转移
进阶：P3961 黄金矿工
我们可以一次求出每条直线的斜率，在排个序（方便判断斜率是否相等）
相等的分在一组物品中，再跑一遍01背包就AC了
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 int n,T,cnt,maxn; 6 int t[210][210],v[210][210],num[210]; 7 int f[40010]; 8 struct node{ 9 int x,y,v,t; 10 double k; 11 }e[210]; 12 int comp(node a,node b){ 13 if(a.k == b.k) return a.y < b.y; 14 return a.k < b.k; 15 } 16 int main(){ 17 scanf("%d%d",&n,&T); 18 for(int i = 1; i <= n; i++){ 19 scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].t,&e[i].v); 20 e[i].k = e[i].y *(1.0) / e[i].x * (1.0);//求斜率 21 } 22 sort(e+1,e+n+1,comp);//排序 23 for(int i = 1; i <= n; i++){ 24 if(e[i].k != e[i-1].k || i == 1) {//找到一条斜率不同的直线 25 cnt++; 26 } 27 if(num[cnt] == 0){//第一件物品 28 num[cnt]++; 29 t[cnt][1] = e[i].t; 30 v[cnt][1] = e[i].v; 31 } 32 else{//其他物品 33 num[cnt]++; 34 t[cnt][num[cnt]] = t[cnt][num[cnt]-1] + e[i].t; 35 v[cnt][num[cnt]] = v[cnt][num[cnt]-1] + e[i].v; 36 } 37 } 38 f[0] = 0; 39 for(int i = 1; i <= cnt; i++){//分组背包 40 for(int j = T; j >= t[i][1]; j--){ 41 maxn = f[j]; 42 for(int k = 1; k <= num[i]; k++){ 43 if(j > t[i][k]){ 44 maxn = max(maxn,f[j-t[i][k]] + v[i][k]); 45 } 46 } 47 f[j] = maxn; 48 } 49 } 50 printf("%d",f[T]); 51 return 0; 52 }
有依赖的背包（树形背包）
例题——>金明的预算方案
我们称不依赖别的物品的为主件，依赖于于其他物品的为附件；
包含一个主件和若干个附件有一下可能；
可以将这几种可能性转换为一件物品，因为这几种可能性只能选一种，最后在跑一边分组背包
如果是多叉树的集合，先算子节点的集合，最后再算父亲节点的集合。
1 #include<algorithm> 2 #include<cstdio> 3 #include<iostream> 4 using namespace std; 5 int n,m,c,p,q,t; 6 int w[65][3],v[65][3],f[65][3200]; 7 int main(){ 8 scanf("%d%d",&n,&m); 9 n/=10; 10 for(int i = 1; i <= m; i++){ 11 scanf（“%d%d%d”,&c,&p,&q); 12 c = c/10; 13 if(q == 0){//主件 14 w[i][0] = c; 15 v[i][0] = c*p; 16 } 17 else if(w[q][1] == 0){//第一件附件 18 w[q][1] = c; 19 v[q][1] = c*p; 20 } 21 else {//第二件附件 22 w[q][2] = c; 23 v[q][2] = c*p; 24 } 25 } 26 for(int i = 1; i <= m; i++){ 27 for(int j = 0; j <= n; j++){ 28 f[i][j] = f[i-1][j];//一个都不选的情况 29 if(j >= w[i][0]){//选主件的情况 30 t = f[i-1][j-w[i][0]] + v[i][0]; 31 if(t > f[i][j]){ 32 f[i][j] = t; 33 } 34 } 35 if(j >= w[i][0]+w[i][1]){//选主件和第一个附件的情况 36 t = f[i-1][j-w[i][0]-w[i][1]] + v[i][0]+v[i][1]; 37 if(t > f[i][j]){ 38 f[i][j] = t; 39 } 40 } 41 if(j >= w[i][0]+w[i][2]){//选主件和第二个附件的情况 42 t = f[i-1][j-w[i][0]-w[i][2]] + v[i][0]+v[i][2]; 43 if(t > f[i][j]){ 44 f[i][j] = t; 45 } 46 } 47 if(j >= w[i][0]+w[i][1]+w[i][2]){//选主件和所有附件的情况 48 t = f[i-1][j-w[i][0]-w[i][1]-w[i][2]] + v[i][0]+v[i][1]+v[i][2]; 49 if(t > f[i][j]){ 50 f[i][j] = t; 51 } 52 } 53 } 54 } 55 cout<<f[m][n]*10<<endl; 56 return 0; 57 }
背包求方案数
给定一个背包容量，物品费用，和其他关系，求装到一定容量的方案数
这种问题把求最大值改为求和就ok了
1 dp[i] = Σ(dp[i] ,dp[i-c[i])
初值 dp[o] = 1;
因为 当容量为0时：一种方案为什么也不装。
例题 ——>P3983 赛斯石
这个题最大的难点在于物品可以拆开，但船不能拆
如载重7的船，可以装4si和3si 也可以装1si和6si
所以 1-10载重船的最大利益可以用背包求出来；
最后选一些船走，船的收益已固定，可以跑完全背包求质量为n的最大收益
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 long long n,b[15],v[15],w[15]; 6 long long ans[100010]; 7 long long a[12] = {0,1,3,5,7,9,10,11,14,15,17}; 8 int main(){ 9 scanf("%ld",&n); 10 for(int i = 1; i <= 10; i++){ 11 scanf("%ld",&b[i]); 12 v[i] = i; 13 } 14 for(int i = 1; i <= 10; i++){//每条船的收益 15 for(int j = i; j <= 10; j++){ 16 w[j] = max(w[j],w[j-i] + b[i]); 17 } 18 } 19 for(int i = 1; i <= 10; i++) w[i] -= a[i];//利润 20 ans[0] = 0; 21 for(int i = 1; i <= 10; i++){//怎样租船利润最大 22 for(int j = v[i]; j <= n; j++){ 23 ans[j] = max(ans[j] , ans[j- v[i]] + w[i]); 24 } 25 } 26 printf("%ld",ans[n]); 27 return 0; 28 }
原文：https://www.cnblogs.com/genshy/p/13287770.html