背包 DP

参考资料

• 背包 DP - OI Wiki

0-1 背包

有 $n$ 个物品和一个容量为 $m$ 的背包，每个物品有重量 $w_i$ 和价值 $v_i$ 两种属性。

要求选若干物品放入背包使背包中物品的总价值最大，且背包中物品的总重量不超过背包的容量。

$$f_j=\max{(f_j,f_{j-w_i}+v_i)}$$

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=1005;
const int M=10005;
int w[N],v[N],f[M];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=w[i];j--)
		{
			f[j]=max(f[j],f[j-w[i]]+v[i]);
		}
	}
	cout<<f[m]<<'\n';
	return 0;
}

完全背包

有 $n$ 种物品和一个容量为 $m$ 的背包，每种物品有重量 $w_i$ 和价值 $v_i$ 两种属。

要求选若干个物品放入背包使背包中物品的总价值最大，且背包中物品的总重量不超过背包的容量。

$$f_j=\max{(f_j,f_{j-w_i}+v_i)}$$

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=1005;
const int M=10005;
int w[N],v[N],f[M];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=w[i];j<=m;j++)
		{
			f[j]=max(f[j],f[j-w[i]]+v[i]);
		}
	}
	cout<<f[m]<<'\n';
	return 0;
}

多重背包

有 $n$ 种物品和一个容量为 $m$ 的背包，每种物品有重量 $w_i$、价值 $v_i$、数量 $k_i$ 三种属性。

要求选若干个物品放入背包使背包中物品的总价值最大，且背包中物品的总重量不超过背包的容量。

提示

二进制分组：将每种物品拆分成不超过 $\log{k}$ 个由 $2^i$ 个物品「捆绑」而成的大物品。

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=10005;
const int M=1000005;
int w[N],v[N],f[M];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		int v1,w1,k;
		cin>>v1>>w1>>k;
		int b=1;
		while(b<k)
		{
			k-=b;
			v[++cnt]=v1*b;
			w[cnt]=w1*b;
			b<<=1;
		}
		v[++cnt]=v1*k;
		w[cnt]=w1*k;
	}
	n=cnt;
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=w[i];j--)
		{
			f[j]=max(f[j],f[j-w[i]]+v[i]);
		}
	}
	cout<<f[m]<<'\n';
	return 0;
}

例题

洛谷 P1048 [NOIP 2005 普及组] 采药

洛谷 P1048 [NOIP 2005 普及组] 采药

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

代码（2）

启发式搜索

#include <bits/stdc++.h>
using namespace std;

const int N=105;
struct Node
{
	int a,b;
	double f;
	bool operator<(const Node &rhs){return f>rhs.f;}
}a[N];
int n,m,ans=0;
int f(int t,int v)
{
	int res=0;
	for(int i=1;t+i<=n;i++)
	{
		if(v<a[t+i].a)return res+v*a[t+i].f;
		v-=a[t+i].a;
		res+=a[t+i].b;
	}
	return res;
}
void work(int t,int p,int v)
{
	ans=max(ans,v);
	if(t>n)return;
	if(f(t,p)+v>ans)work(t+1,p,v);
	if(a[t].a<=p)work(t+1,p-a[t].a,v+a[t].b);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].a>>a[i].b;
		a[i].f=a[i].b*1.0/a[i].a;
	}
	sort(a+1,a+n+1);
	work(1,m,0);
	cout<<ans<<'\n';
	return 0;
}

背包DP

#include <bits/stdc++.h>
using namespace std;

const int N=105;
const int T=1005;
int a[N],b[N],f[T];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t,m;
	cin>>t>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i]>>b[i];
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=t;j>=a[i];j--)
		{
			f[j]=max(f[j],f[j-a[i]]+b[i]);
		}
	}
	cout<<f[t]<<'\n';
	return 0;
}