这里是gsx整理的背包大合集！！！

演讲大厅题目思路及题解^[1]

背包DP1课件下载 背包DP2课件下载

点击此处跳转至背包训练界面

首先是01背包

01背包的做题思路课堂摘抄如下:

一、分析三特性啊可参考gsx的博客

二、定义状态变量

问题：背着p的背包有n个物品选出最大价值是多少？ f(n)(p)=? f[n][p]=sij f[i][j]=sij;有i个物品选出最大价值找状态变量

三、状态转移方程(可用填表方法)

考虑我这个格子会从哪些地方来？

不选:f[i][j]=f[i-1][j];//加0

选第i件物品:f[i][j]=f[i-1][j-w[i]]+v[i];

取最大！！！

四、初始化和边界值

f[i][j]={0};

五、答案

f[n][p]

这个是01背包的代码模板

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

这个是01背包求方案数的代码模板其中//部分可删除，也就是取余部分

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int f[MAXN],g[MAXN],v[MAXN],w[MAXN],t,s,n,m;
int mod=1e9+7;//
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=0;i<=m;i++) g[i]=1;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            t=max(f[j],f[j-v[i]]+w[i]);
            s=0;
            if(t==f[j]) s=(s+g[j])%mod;//%mod
            if(t==f[j-v[i]]+w[i]) s=(s+g[j-v[i]])%mod;//%mod
            f[j]=t;
            g[j]=s;
        }
    }
    cout<<g[m];
    return 0;
}

接着是完全背包代码模板

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

然后这个是满背包代码模板

#include <bits/stdc++.h>
using namespace std;
int n,v[105],p;
bool f[10005];
int main(){
    cin>>p>>n;
    for(int i=1;i<=n;i++) cin>>v[i];
    f[0]=true;
    for(int i=1;i<=n;i++)
		for(int j=p;j>=v[i];j--) f[j]=f[j-v[i]];
	if(f[p]==true) cout<<"yes";
	else cout<<"no";
    return 0;
}

紧接着这是二维背包模板

#include <bits/stdc++.h>
using namespace std;
const int MAXN=55,MAXV=405;
int V,M,n,v[MAXN],m[MAXN],c[MAXN],f[MAXV][MAXV];
int main(){
    cin>>V>>M>>n;
    for(int i=1;i<=n;i++) cin>>v[i]>>m[i]>>c[i];
    for(int i=1;i<=n;i++)
		for(int j=V;j>=v[i];j--)
		    for(int k=M;k>=m[i];k--) f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+c[i]);
	cout<<f[V][M];
    return 0;
}

其次是多重背包代码模板

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

最后是分组背包代码模板

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

演讲大厅题目思路及题解

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
int n,dp[MAXN],ans;
struct stu{int s,e,t;}a[MAXN];
bool out(stu x,stu y){
    return x.e<y.e;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].s>>a[i].e;
        a[i].t=(a[i].e-a[i].s);
    }
    sort(a+1,a+n+1,out);
    for(int i=1;i<=n;i++){
        dp[i]=a[i].t;
        for(int j=1;j<i;j++){
            if(a[i].s>=a[j].e)dp[i]=max(dp[i],dp[j]+a[i].t);
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

回到题解库

---

1. 回到顶部 ↩︎