2024-04-08竞赛笔记

2024/4/8

混合背包

代码框架

框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
int dp[100001],v,n[1000001],vl[1000001],ct[1000001];
void lingyi(int cost,int value){
	for(i=v;i>=cost;i--){
		dp[i]=max(dp[i],dp[i-cost]+value);
	}
} 
void wanquan(int cost,int value){
	for(i=cost;i<=v;i++){
		dp[i]=max(dp[i],dp[i-cost]+value);
	}
}
void duochong(int cost,int value,int num){
	int k;
	if(num*cost>=v){//物品个数随便取，完全背包 
		wanquan(cost,value);
	}
	else{
		k=1;
		while(num>k){//二进制优化 
			lingyi(k*cost,k*value);
			num-=k;
			k*=2;
		}
		lingyi(num*cost,num*value);
	}
}
int main(){
	int c,m,i;
	cin>>c;//测试数据总数
	while(c--){
		cin>>v>>m;
		for(i=1;i<=m;i++){
			cin>>vl[i]>>ct[i]>>n[i];
		}
		memset(dp,0,sizeof(dp));
		for(i=1;i<=m;i++){
			duochong(vl[i],ct[i],n[i]);
		}
		cout<<dp[v]<<endl;
	} 
	return 0;
}

例一:混合背包(YBT1270)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int dp[100001],v,n[1000001],vl[1000001],ct[1000001],n1;
void lingyi(int cost,int value){
	for(int i=v;i>=cost;i--){
		dp[i]=max(dp[i],dp[i-cost]+value);
	}
} 
void wanquan(int cost,int value){
	for(int i=cost;i<=v;i++){
		dp[i]=max(dp[i],dp[i-cost]+value);
	}
}
void duochong(int cost,int value,int num){
	int k;
	if(num*cost>=v){//物品个数随便取，完全背包 
		wanquan(cost,value);
	}
	else{
		k=1;
		while(num>k){//二进制优化 
			lingyi(k*cost,k*value);
			num-=k;
			k*=2;
		}
		lingyi(num*cost,num*value);
	}
}
int main(){
	cin>>v>>n1;
	for(int i=1;i<=n1;i++) cin>>vl[i]>>ct[i]>>n[i];
	for(int i=1;i<=n1;i++)
	{
		if(n[i]==0) wanquan(vl[i],ct[i]);
		else if(n[i]==1) lingyi(vl[i],ct[i]);
		else if(n[i]>1) duochong(vl[i],ct[i],n[i]);
	}
	cout<<dp[v];	
}

二维费用的背包问题

简介

jj

例题:(ACW8)二维费用的背包问题

a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int n,v1,m1,f[110][110],m[10010],v[10010],w[10010];
int main(){
	cin>>n>>v1>>m1;
	for(int i=1;i<=n;i++){
		cin>>v[i]>>m[i]>>w[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=v1;j>=v[i];j--){
			for(int k=m1;k>=m[i];k--){
				f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);
			}
			
		}
	}
	cout<<f[v1][m1];
	return 0;
}