【DP】背包问题全解

编程入门行业动态更新时间:2024-10-20 01:42:27

【DP】<a href=https://www.elefans.com/category/jswz/34/1767487.html style= 背包问题全解"/>

【DP】背包问题全解

一.简介

DP（动态规划）背包问题是一个经典的组合优化问题，通常用来解决资源分配的问题，如货物装载、投资组合优化等。问题的核心思想是在有限的资源约束下，选择一组物品以最大化某种价值指标，通常是总价值或总利润。

二.闫氏DP分析法

三.01背包

（1）概念

每个物品只有一个，要么选，要么不选

（2）状态转移方程

f[i][j] = max(f[i-1][j] , f[i-1][j-v]+w)

（3）经典例题

P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu)

（4)代码

#include<bits/stdc++.h>
#define N 1010
using namespace std;
int f[N][N];
int w[N],c[N];
int bag,n;
int main(){scanf("%d%d",&bag,&n);for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);for(int i=1;i<=n;i++){for(int j=0;j<=bag;j++){f[i][j]=f[i-1][j];if(j>=w[i]){f[i][j]=max(f[i][j],f[i-1][j-w[i]]+c[i]);}}}printf("%d",f[n][bag]);return 0;
}

（5）滚动数组优化

#include<bits/stdc++.h>
#define N 1010
using namespace std;
int f[N];
int n,m;
int main()
{scanf("%d%d", &m, &n);for(int i = 1; i <= n; i ++ ){int w,c;scanf("%d%d", &w, &c);for(int j = m; j >=w ; j -- ){ f[j] = max(f[j], f[j-w] + c);}}printf("%d", f[m]);return 0;
}

四.完全背包

（1）概念

每个物品有无限个

（2）例题

1023. 买书 - AcWing题库

（3）闫氏DP分析法

（4）状态转移方程推导

f[i][j] = f[i - 1][j] + f[i - 1][j - v * 1] + f[i - 1][j - v * 2] + ...... + f[i -1][j - v * k];

f[i][j - v] = f[i - 1][j - v * 1] + f[i - 1][j - v * 2] + ...... + f[i - 1][j - v * k];

所以推出：f[i][j] = f[i - 1][j] + f[i][j - v];

再使用滚动数组简化，就得出结论，其实就是01背包，内循环从大到小变成了从小到大！

（5）参考代码

#include<bits/stdc++.h>
#define N 1010
using namespace std;
int f[N];
int n;
int a[5] = {0, 10, 20, 50, 100};int main(){scanf("%d", &n);f[0] = 1; for(int i = 1; i <= 4; i ++ ){for(int j = a[i]; j <= n; j ++ ){f[j] += f[j - a[i]];}}	printf("%d", f[n]);return 0;
}

五.多重背包

（1）概念

物品有一定的数量

（2）实现方式

1.朴素版（易） 2.二进制优化版（中） 3.单调队列优化版（难）

（3）经典例题

1019. 庆功会 - AcWing题库

（3）朴素版

#include<bits/stdc++.h>
#define N 6010
using namespace std;
int f[N];
int n, m;
int main(){scanf("%d%d", &n, &m); //n个物品，m容量 for(int i = 1;i <= n; i ++ ){int v, w, s; //容量，价值，数量 scanf("%d%d%d", &v, &w, &s);for(int j = m; j >= v; j -- ){ //枚举容量 for(int k = 1;k <= s && k * v <= j; k ++ ){ //再枚举数量 f[j] = max(f[j], f[j - k * v] + w * k);}}}printf("%d", f[m]);return 0;
}

（4）二进制优化版

#include<bits/stdc++.h>
#define N 6010
using namespace std;
int f[N];
int n,m;
int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n ; i ++ ){int v, w, s;scanf("%d%d%d", &v, &w, &s);for(int k = 1; k <= s; k *= 2) //二进制分解{for(int j = m; j >= k * v; j --)f[j] = max(f[j], f[j - k * v] + k * w);s -= k;}if(s) //余下的{for(int j = m; j >= s * v; j --)f[j] = max(f[j], f[j - s * v] + s * w);}}printf("%d", f[m]);return 0;
}

六.分组背包

（1）概念

每组物品有若干个，同一组内的物品最多只能选一个。

和多重背包十分相似，也简单。难得写了，copy一下，哈哈。

七.混合背包

（1）概念

就是把完全背包，多重背包，01背包混合起来，分类讨论即可，代码很好看懂。

（2）例题

7. 混合背包问题 - AcWing题库

（3）参考代码

#include<bits/stdc++.h>
#define N 1010
using namespace std;
int f[N];
int n,m;
int main()
{scanf("%d%d", &n, &m);int v, w, s;for(int i = 1; i <= n; i ++ ){scanf("%d%d%d", &v, &w, &s);if(s == 0){for(int j = v; j <= m; j ++ )f[j] = max(f[j], f[j - v]);}else{if(s == -1) s = 1;for(int k = 1; k <= s; k *= 2){for(int j = m; j >= k * v; j --)f[j] = max(f[j], f[j - k * v] + k * w);s -= k;}if(s){for(int j = m; j >= s * v; j --)f[j] = max(f[j], f[j - s * v] + s * w);}}}printf("%d", f[m]);return 0;
}

八.有依赖的背包

（1）例题

10. 有依赖的背包问题 - AcWing题库

（2）参考代码

#include<iostream>
#include<vector>
using namespace std;
int f[110][110];//f[x][v]表达选择以x为子树的物品，在容量不超过v时所获得的最大价值
vector<int> g[110];
int v[110],w[110];
int n,m,root;int dfs(int x)
{for(int i=v[x];i<=m;i++) f[x][i]=w[x];//点x必须选，所以初始化f[x][v[x] ~ m]= w[x]for(int i=0;i<g[x].size();i++){int y=g[x][i];dfs(y);for(int j=m;j>=v[x];j--)//j的范围为v[x]~m, 小于v[x]无法选择以x为子树的物品{for(int k=0;k<=j-v[x];k++)//分给子树y的空间不能大于j-v[x],不然都无法选根物品x{f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);}}}
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++){int fa;cin>>v[i]>>w[i]>>fa;if(fa==-1)root=i;elseg[fa].push_back(i);}dfs(root);cout<<f[root][m];return 0;
}

九.二维费用背包

（1）简介

其实就是多了一维，和一维费用没啥区别

二维背包可以结合上述所有背包！

（2）例题

8. 二维费用的背包问题 - AcWing题库

（3）参考代码

#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
int f[maxn][maxn];
int n,V,M;
int main(){scanf("%d%d%d",&n,&V,&M);for(int i=1;i<=n;i++){int v,m,w;scanf("%d%d%d",&v,&m,&w);//就是这里多了一维，多了一个循环，很好理解for(int j=V;j>=v;j--){for(int k=M;k>=m;k--){f[j][k]=max(f[j][k],f[j-v][k-m]+w);}}}printf("%d",f[V][M]);return 0;
}