登录
← 返回首页 | 代码片段 › 5 动态规划 › 5.2 背包问题 › 背包问题 / 搜索
JSON MD

5.2 背包问题

01背包 采药
14 行
CPP JSON
【01背包(采药)】 01背包的算法实现模板。 适用场景:资源分配问题、物品选取的最优方案
C++ 13 行 CPP
#include<algorithm>
#include<cstdio>
int T,n,i,j,v[110],w[110],f[1010];
int main(){
    scanf("%d%d",&T,&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);
    for(i=1;i<=n;i++)
        for(j=T;j>=v[i];j--)
            f[j]=std::max(f[j],f[j-v[i]]+w[i]);
    printf("%d",f[T]);
    return 0;
}
二维费用 找啊找啊找GF
20 行
CPP JSON
【二维费用(找啊找啊找GF)】 二维费用的算法实现模板。 适用场景:资源分配问题、物品选取的最优方案
C++ 19 行 CPP
#include<algorithm>
#include<cstdio>
using namespace std;
int tmp,T1,T2,x,y,n,i,j,k,v1[105],v2[105],w[105],dp[105][105],ans[105][105];
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d%d%d",&v1[i],&v2[i],&w[i]);
    scanf("%d%d",&T1,&T2);
    for(i=1;i<=n;++i)
        for(j=T1;j>=v1[i];--j)
            for(k=T2;k>=v2[i];--k){
            	if(dp[j][k]<(tmp=dp[j-v1[i]][k-v2[i]]+1)){
            		dp[j][k]=tmp;
            		ans[j][k]=ans[j-v1[i]][k-v2[i]]+w[i];
				}
				else if(dp[j][k]==tmp)ans[j][k]=min(ans[j][k],ans[j-v1[i]][k-v2[i]]+w[i]);
            }
    printf("%d",ans[T1][T2]);
}
分组背包 金明的预算方案
22 行
CPP JSON
【分组背包(金明的预算方案)】 分组背包的算法实现模板。 适用场景:资源分配问题、物品选取的最优方案
C++ 21 行 CPP
#include<algorithm>
#include<cstdio>
using namespace std;
int T,n,i,j,a[65],s,t,r1,r2,r[65][3],v[65],w[65],f[32010];
int main(){
    scanf("%d%d",&T,&n);
    v[0]=0xfffffff;
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&v[i],&s,&a[i]);
        if(a[i])r[a[i]][++r[a[i]][0]]=i;w[i]=v[i]*s;
    }
    for(i=1;i<=n;i++)
        for(j=T;j>=v[i]&&(!a[i]);j--){
            t=j-v[i],r1=r[i][1],r2=r[i][2];
            f[j]=max(f[j],f[t]+w[i]);
            if(v[r1]<=t)f[j]=max(f[j],f[t-v[r1]]+w[i]+w[r1]);
            if(v[r2]<=t)f[j]=max(f[j],f[t-v[r2]]+w[i]+w[r2]);
            if(v[r1]+v[r2]<=t)f[j]=max(f[j],f[t-v[r1]-v[r2]]+w[i]+w[r1]+w[r2]);
        }
    printf("%d",f[T]);
}
多人背包 kth_knapsack
23 行
CPP JSON
【多人背包】 多人背包的算法实现模板。 适用场景:资源分配问题、物品选取的最优方案
C++ 22 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
int ans,T,n,i,j,k,K,a,b,t,re[45],v[210],w[210],f[5010][45];
int main(){
    scanf("%d%d%d",&K,&T,&n);
    memset(f,-127,sizeof(f));f[0][1]=0;
    for(i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);
    for(i=1;i<=n;i++)
        for(j=T;j>=v[i];j--){
            a=b=1,t=0;
            while(t<=K){
                if(f[j][a]>=f[j-v[i]][b]+w[i])re[++t]=f[j][a++];
                else re[++t]=f[j-v[i]][b++]+w[i];
            }
            for(k=1;k<=K;k++)f[j][k]=re[k];
        }
    for(i=1;i<=K;i++)ans+=f[T][i];
    printf("%d",ans);
    return 0;
}
多重背包 (宝物筛选) 二进制优化
29 行
CPP JSON
【多重背包 (宝物筛选)(二进制优化)】 代码包含 in 等核心函数,实现了 多重背包 (宝物筛选) 的算法逻辑。 核心函数: void in(Re &x) — 核心算法函数 关键配置: N=103,M=4e4+3 适用场景:资源分配问题、物品选取的最优方案
C++ 28 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=103,M=4e4+3;
int n,m,x,y,z,V,ans,v[N*17],w[N*17],dp[M];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
int main(){
	in(m),in(V);
	memset(dp,-127,sizeof(dp));
	dp[0]=0;
	while(m--){
		in(x),in(y),in(z);Re p=1;
		while(z>=p)v[++n]=y*p,w[n]=x*p,z-=p,p<<=1;
		if(z)v[++n]=y*z,w[n]=x*z;
	}
	for(Re i=1;i<=n;++i)
		for(Re j=V;j>=v[i];--j)	
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
	for(Re i=0;i<=V;++i)ans=max(ans,dp[i]);
	printf("%d\n",ans);
}
完全背包 货币系统
17 行
CPP JSON
【完全背包(货币系统)】 完全背包的算法实现模板。 适用场景:资源分配问题、物品选取的最优方案
C++ 16 行 CPP
#include<bits/stdc++.h>
using namespace std;
int T,n,ans,a[105],dp[30005];
int main(){
    scanf("%d",&T);
    while(T--){
    	memset(dp,-127,sizeof(dp));
    	scanf("%d",&n);dp[0]=ans=0;
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)
		    for(int j=a[i];j<=25000;j++)
		        dp[j]=max(dp[j],dp[j-a[i]]+1);
		for(int i=1;i<=n;++i)ans+=dp[a[i]]==1;
		printf("%d\n",ans);
	}
}
混合背包 樱花
25 行
CPP JSON
【混合背包(樱花)】 混合背包的算法实现模板。 适用场景:资源分配问题、物品选取的最优方案
C++ 24 行 CPP
#include<algorithm>
#include<cstdio>
using namespace std;
int x,a,b,c,d,T,n,i,j,t,f[1010],v[100010],w[100010];
int main(){
	scanf("%d:%d%d:%d%d",&a,&b,&c,&d,&n);
	T=c*60+d-a*60-b;
	for(i=1;i<=n;i++){
		scanf("%d%d%d",&a,&b,&c);
		if(!c){
			for(j=0;j+a<=T;j++)
				f[j+a]=max(f[j+a],f[j]+b);
			continue;
		}
		x=1;
		while(c>=x){v[++t]=x*a,w[t]=x*b,c-=x,x<<=1;}
		v[++t]=c*a,w[t]=c*b;
	}
	for(i=1;i<=t;i++)
		for(j=T;j>=v[i];j--)
			f[j]=max(f[j],f[j-v[i]]+w[i]);
	printf("%d",f[T]);
	return 0;
}
已复制