【DP】背包问题全解

一.简介

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

二.闫氏DP分析法

三.01背包

（1）概念

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

（2）状态转移方程

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

（3）经典例题

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

（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;
        else
            g[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;
}