背包

P1048采药

01背包板子

[f[i][j] = max egin{cases} f[i-1][j] \ f[i-1][j-V_{k}]+W_{k} end{cases} ]


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

#define int long long 

const int p=1e5+6;

template<typename _T>
void read(_T &x)
{
	x=0;char s=getchar();int f=1;
	while(s<'0'||s>'9'){f=1;if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<1)+(x<<3)+s-'0';s=getchar();}
	x*=f;
}

int f[2333][2333];
int v[2333],w[2333];

signed main()
{
	int T,M;

	read(T);
	read(M);
	
	for(int i=1;i<=M;i++)
	{
		read(w[i]);
		read(v[i]);
	}
	
	for(int i=1;i<=M;i++)
		for(int j=1;j<=T;j++)
	{
		if(j-w[i] >=0)
		f[i][j] = max(f[i-1][j] , f[i-1][j-w[i]]+v[i]);
		else f[i][j] = f[i-1][j];
	}
	
	cout<<f[M][T];
}

P1757分组背包

[f[i][j] = max egin{cases} f[i-1][j]\ max_{1≤k≤C_i}f[i-1][j-V_{ik}]+W_{ik} end{cases} ]

有一点需要注意，分组背包的阶段是组数
状态是体积
决策是组中物品
所以体积要放在物品之外

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

template<typename _T>
inline void read(_T &x)
{
	x=0;char s=getchar();int f=1;
	while(s<'0'||s>'9'){f=1;if(s =='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<1)+(x<<3)+s-'0';s=getchar();}
	x*=f;
}

int w[2333],v[2333];
vector<int>c[2333];
int f[2223][2333];

signed main()
{
	int n,m;
	
	read(m);
	read(n);
	
	int maxn = 1;
	
	for(int i=1,a,b,g;i<=n;i++)
	{
		read(v[i]);
		read(w[i]);
		read(g);
		c[g].push_back(i);
		maxn = max(g,maxn);
	}
	
	memset(f,0xcf,sizeof(f));
	
	for(int j=0;j<=m;j++) f[0][j]=0;

	for(int i=1;i<=maxn;i++)
		for(int j=0;j<=m;j++)
		{
			
			f[i&1][j] =f[(i-1)&1][j];
			
			for(int k=0,id;k!=c[i].size();k++)
			{
				id = c[i][k];
				if(j>=v[id])
				f[i&1][j] = max(f[i&1][j] , f[(i-1)&1][j-v[id]]+w[id]);
			}
		}
		
	cout<<f[maxn&1][m];
}

P1616完全背包

[f[i][j] = max egin{cases} f[i-1][j]\ f[i][j-V_{i}]+W_{i} end{cases} ]

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int p=1e5+5;
#define int long long 

template<typename _T>
void read(_T &x)
{
	x =0;char s=getchar();int f=1;
	while(s<'0'||s>'9'){f=1;if(f=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
	x*=f;
}

int v[p],w[p];
int f[233333333];

signed main()
{
	int t,m;
	
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	read(t);read(m);
	
	for(int i=1;i<=m;i++)
	{
		read(w[i]);
		read(v[i]);
	}
	
	for(int i=1;i<=m;i++)
		for(int j=1;j<=t;j++)
	{
		if(j-w[i] >= 0)
		f[j] = max(f[j],f[j-w[i]]+v[i]);
	}
	
	cout<<f[t];

}

P1776多重背包

暴力复杂度(O(M*sum_{i=1}^{N}C_i))

所以采用二进制拆分法
主要思想:
把数量为Ci的第i种物品拆成p+2个物品，他们的体积分别为

[2^0*V_i,2^1*V_i cdots ,2^p*V_i,R_i*V_i ]

这p+2个物品可以凑成0~Ci任意物品数目组合
复杂度(O(M*sum_{i=1}^NlogC_i))

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

#define int long long 

const int p=5e5+5;

template<typename _T>
void read(_T &x)
{
	x=0;char s=getchar();int f=1;
	while('0'>s||s>'9'){f=1;if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
	x*=f;
}

int v[p];
int w[p];
int tit = 0;
int f[3][p];

signed main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	int n,m;
	
	read(n);
	read(m);
	
	for(int i=1,a,b,c;i<=n;i++)	
	{
		read(a);
		read(b);
		read(c);
		
		for(int j=1;j<=c;j<<=1)
		{
			v[++tit] = j*a;
			w[tit] = j* b;
			c-=j;
		}
		if(c)
		{
			v[++tit] = c*a,w[tit] = c*b;
		 } 
	}

	for(int i=1;i<=tit;i++)
	{
		memset(f[i&1],0,sizeof(f[i&1]));
		
		for(int j=1;j<=m;j++)
		{
			if(j-w[i] >=0)
			f[i&1][j] = max(f[i-1&1][j] , f[i-1&1][j-w[i]]+v[i]);
			else f[i&1][j] = f[i-1&1][j];
		}
		
	}
		
	cout<<f[tit&1][m];
	
}

(O(NM))的单调队列法我并不会，如果有一天我还在这里，再补上吧

树形背包

设(f[now][j][k])为在以(now)为根的子树中，选前(j)个子节点，修(k)门课的最大收益

[f[now][j][k] = max egin{cases} f[now][j-1][k]\ f[now][j-1][k-l]+f[son(j)][num(son(j))][l] end{cases} +score[now] ]

显然我们可以把(j)的那一维压掉
可以发现(k)是必然的大于(k-l)的，所以对于(k)我们需要倒序循环

#include<iostream>
#include<cstdio>

using namespace std;

int head[2333];
int next[2333],ver[2333];
int f[2333][233];
int tot;
int n,m;

inline void add(int x,int y)
{
	ver[++tot]=y;
	next[tot]=head[x];
	head[x]=tot;
}

inline void dtgh(int now)
{
	for(int i=head[now];i;i=next[i])
	{
		dtgh(ver[i]);
		
		for(int j=m+1;j>1;j--)
			for(int k=0;k<j;k++)
			f[now][j]=max(f[now][j],f[now][j-k]+f[ver[i]][k]);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	cin>>n>>m;
	
	for(int i=1,k,s;i<=n;i++)
	{
		cin>>k>>s;
		f[i][1]=s;//因为选择这个点就必定花费1，所以直接处理1的情况
		add(k,i);
	}
	
	dtgh(0);
	
	cout<<f[0][m+1];
 }

背包规划集合

背包

P1048采药

P1757分组背包

P1616完全背包

P1776多重背包

树形背包

(End)