背包动态规划

用于借鉴的代码

01背包

单个量答案和限制都是一个

1最大的存储容量是$s$单位不定

2有$n$种存储方式

3$a$表示每个存储的大小

#include <bits/stdc++.h>
using namespace std;
int s,n,dp[45678],a[567];
int main(){
	cin>>s>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		for(int j=s;j>=a[i];j--){
			dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
		}
	}	
	int sum=0;
	for(int i=1;i<=s;i++){
		sum=max(sum,dp[i]);
	}
	cout<<sum;
	
	return 0;
}

一个未知量背包

1最大的存储容量是$s$单位不定

2有$n$种存储方式

3$t$表示每个存储的大小

4$v$表示每个存储的价值

#include <bits/stdc++.h>

using namespace std;
int n,t[100],v[100],s;
int dp[100000];
int main(){
	cin>>s>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>v[i];
		
	}
	for(int i=1;i<=n;i++){
		for(int j=s;j>=t[i];j--){
			dp[j]=max(dp[j],dp[j-t[i]]+v[i]);
		}
	}

  int sum=0;
	for(int i=1;i<=s;i++){
      sum=max(sum,dp[i]);
	}
	cout<<sum;
	
	
	return 0;
}

两个未知量背包

1最大的存储容量是$s$单位不定

2有$n$种存储方式

3$t,w$表示每个存储的大小

4$g$表示每个存储的价值

#include <bits/stdc++.h>

using namespace std;
int n,v[567],w[567],g[567],vMax,wMax;
int dp[12345][12345];
int main(){
	cin>>vMax>>wMax;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i]>>g[i]; 
    }
    for(int i=1;i<=n;i++){
        for(int j=vMax;j>=v[i];j--){
            for(int k=wMax;k>=w[i];k--){
                dp[j][k]=max(dp[j][k],dp[j-v[i]][k-w[i]]+g[i]);
            }
        }
    }
    
	cout<<dp[vMax][wMax];
	
	return 0;
}

完全背包

2025年2月23日：更新思路

若代价a[i]=3,价值为c[i]

$∵dp[i][8]=max(dp[i-1][8],dp[i-1][5]+c[i],dp[i-1][2]+c[i]\times2);$

$又∵dp[i][5]=max(dp[i-1][5],dp[i-1][2]+c[i])$

$∴dp[i][8]=max(dp[i-1][8],dp[i-1][5]+c[i])$

#include<bits/stdc++.h>

using namespace std;
int dp[12345];
int n,v,a[12345],c[12345];
int main(){
	cin>>v>>n;
	for(int i=1;i<=n;i++)cin>>a[i]>>c[i];
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		for(int j=a[i];j<=v;j++){
			dp[j]=max(dp[j],dp[j-a[i]]+c[i]);
		}
	}
	cout<<dp[v];
	return 0;
}

分组背包

每一组只能选择一个数

for(int i=1;i<=n;i++) 
for(int j=0;j<=m;j++)
for(int k=1;k<=s[i];k++)//s[i]表示第i组物品的个数
  if(j>=v[i][k]){//剩余的背包容量j大于第i组的第k个物品的体积
    f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}

区间dp

石子合并

#include <bits/stdc++.h>

using namespace std;
int n,a[500];
//设置一个记忆数组（前缀和）
int s[500][500]={};
int f(int l,int r){	//l到r堆石子的代价
	if(s[l][r]!=-1)return s[l][r];
	if(l==r){	//只剩一堆，代价为0
		return 0;
	}int Min=INT_MAX;
	for(int i=l;i<r;i++){
		if(Min>f(l,i)+f(i+1,r)+a[r]-a[l-1]){
			Min=f(l,i)+f(i+1,r)+a[r]-a[l-1];
		}
	}
	
	return s[l][r]= Min;
}
int main() {
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]+=a[i-1];
	}
	
	memset(s,-1,sizeof s);
	
	
	cout<<f(1,n);
	
	return 0;
}

分组模板

#include <bits/stdc++.h>

using namespace std;
int m,n,t;
int dp[123456],cnt[123456],w[1234][1234],v[1234][1234];

int main(){
	cin>>m>>n>>t;
	int a,b,group;
	for(int i=1;i<=n;i++){
		cin>>a>>b>>group;
		int x=cnt[group];
		w[group][x]=a;
		v[group][x]=b;
		cnt[group]++;
	}
	//遍历每一个组别
	for(int i=1;i<=t;i++){
		for(int j=m;j>=0;j--){
			for(int l=0;l<cnt[i];l++){
				if(j>=w[i][l]){
					dp[j]=max(dp[j],dp[j-w[i][l]]+v[i][l]);
				}
			}
		}
	}
	cout<<dp[m];
	
	
	
	
	return 0;
}

树形DP

模板

#include <bits/stdc++.h>

using namespace std;
int n,m,root,v[123],w[123];
int a[123][123],b[123],dp[123][123];
void dfs(int x){
	for(int i=v[x];i<-m;i++){
		dp[x][i]=w[x];
	}
	for(int i=0;i<b[x];i++){
		int s=a[x][i];
		dfs(s);
		for(int j=m;j>=v[x];j--){
			for(int k=0;k<=j-v[x];j++){
				dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[s][k]);
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int p;
		cin>>v[i]>>w[i]>>p;
		if(p==-1){
			root=i;
		}else{
			a[p][b[p]++]=i;
		}
	}
	dfs(root);
	cout<<dp[root][m];
	
	
	
	
	
	return 0;
}

二叉苹果树

#include<bits/stdc++.h>

using namespace std;

const int N = 110, M = N * 2;  //双向边

int n, m;
int h[N],  e[M], ne[M], w[M],  idx;
int f[N][N];  // TODO  f(i,j)  以 i 作为根节点 保留 j 条边的 最大收益 max  

void add( int a, int b, int c ){
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx++;
}

void dfs( int u, int fa ){
	for( int i = h[u]; ~i ; i = ne[i] ){
		int s = e[i];  //根据 u 找到 儿子 j
		// 儿子有可能回流，所以需要判别是否fa
		if( s == fa )  continue;
		// 基于 j 继续深搜
		dfs( s, u );
		// dp 求max
		
		for( int j = m; j >= 0; j-- ){  //爸爸有多少个数字
			// 决策爸爸要分出多少数字给儿子做规划
			for( int k = 0; k <= j - 1; k++ ){
				f[u][j] = max( f[u][j], f[u][j-k-1] + f[s][k] + w[i] );  //w[i] 是链接儿子与爸爸的最必要的边权值
			}
		}
		
	}
}

int main(){
	
	memset( h, -1, sizeof h );
	cin >> n >> m;
	for( int i = 1; i <= n - 1; i++ ){
		int a, b, c;
		cin >> a >> b >> c;
		add( a, b, c ); 
		add( b, a, c );
	}
	dfs( 1, -1 );
	cout << f[1][m];
	
	return 0;
}

区间dp的状态转移的一般方程式

f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+做这件事情的代价)