背包动态规划

用于过水题的借鉴代码

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;
}

完全背包

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的状态转移的一般方程式

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