动态规划背包问题（01、二维、完全背包）

背包问题

01背包

dfs

#include <bits/stdc++.h>
using namespace std;
const int N=1009;
int n,m,v[N],w[N];
int dfs(int x,int spV){//当前枚举到哪个物品，背包剩余容量
	if(x>n)return 0;
	else if(spV<v[x]) return dfs(x+1,spV);
	else return max(dfs(x+1,spV),dfs(x+1,spV-v[x])+w[x]);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
	int ans=dfs(1,m);
	cout<<ans;
	return 0;
}

dfs+记忆化

#include <bits/stdc++.h>
using namespace std;
const int N=1009;
int n,m,v[N],w[N];
int mem[N][N];
int dfs(int x,int spV){
	if(mem[x][spV])return mem[x][spV];
	int sum=0;
	if(x>n)sum= 0;
	else if(spV<v[x]) sum= dfs(x+1,spV);
	else sum= max(dfs(x+1,spV),dfs(x+1,spV-v[x])+w[x]);
	mem[x][spV]=sum;
	return sum;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
	int ans=dfs(1,m);
	cout<<ans;
	return 0;
}

dp (copy dfs)

#include <bits/stdc++.h>
using namespace std;
const int N=1009;
int n,m,v[N],w[N];
int f[N][N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
	for(int i=n;i>=1;i--)
		for(int j=0;j<=m;j++)
		{
			if(j<v[i])f[i][j]=f[i+1][j];
			else f[i][j]=max(f[i+1][j],f[i+1][j-v[i]]+w[i]);
		}
	cout<<f[1][m];
	return 0;
}

二维背包

dfs

#include<bits/stdc++.h>
using namespace std;
const int N=1009;
int n,V,M;
int v[N],w[N],m[N];
int dfs(int x,int spV,int spM){
	if(x>n)return 0;
	else{
		if(spV<v[x]||spM<m[x])return dfs(x+1,spV,spM);
		else return max(dfs(x+1,spV,spM),dfs(x+1,spV-v[x],spM-m[x])+w[x]);
	}
}
int main(){
	cin>>n>>V>>M;
	for(int i=1;i<=n;i++)cin>>v[i]>>m[i]>>w[i];
	int res=dfs(1,V,M);
	cout<<res;
}

dp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1009;
ll n,V,M,v[N],w[N],m[N],f[N][110][110];
int main(){
	cin>>n>>V>>M;
	for(int i=1;i<=n;i++)cin>>v[i]>>m[i]>>w[i];
	for(int i=n;i>=1;i--)
		for(int j=0;j<=V;j++)
			for(int k=0;k<=M;k++){
				if(v[i]>j||m[i]>k)f[i][j][k]=f[i+1][j][k];
				else f[i][j][k]=max(f[i+1][j][k],f[i+1][j-v[i]][k-m[i]]+w[i]);
			}
	cout<<f[1][V][M];
}

完全背包

dfs

#include <bits/stdc++.h>
using namespace std;
const int N=1009;
int n,m,v[N],w[N];
int dfs(int x,int spV){
	if(x>n)return 0;
	if(spV<v[x])return dfs(x+1,spV);
	else return max(dfs(x+1,spV),dfs(x,spV-v[x])+w[x]);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
	int res=dfs(1,m);
	cout<<res;
}

dp

#include <bits/stdc++.h>
using namespace std;
const int N=1009;
int n,m,v[N],w[N],f[N][N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
	for(int i=n;i>=1;i--)
		for(int j=0;j<=m;j++){
			if(j<v[i])f[i][j]=f[i+1][j];
			else f[i][j]=max(f[i+1][j],f[i][j-v[i]]+w[i]);
		}
	cout<<f[1][m];
}