Skip to main content

背包 DP

Summary

背包 DP（Knapsack DP）在总重量不超过容量的前提下最大化所选物品的总价值，分 0-1、完全、多重三种基本模型。0-1 背包中每件物品至多取一次，倒序枚举容量，转移取选与不选的较大值；完全背包中每种物品可取任意多次，改为正序枚举容量即可复用同一状态；多重背包中每种物品有固定件数，借助二进制分组把它拆成不超过 log k 个「捆绑」物品，再当作 0-1 背包处理。三种模型均给出转移方程与参考代码。

参考资料​

0-1 背包​

有 nn 个物品和一个容量为 mm 的背包，每个物品有重量 wiw_i 和价值 viv_i 两种属性。

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

fj=max⁡(fj,fj−wi+vi)f_j=\max{(f_j,f_{j-w_i}+v_i)}
385 Bcpp
#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;
}

完全背包​

有 nn 种物品和一个容量为 mm 的背包，每种物品有重量 wiw_i 和价值 viv_i 两种属性。

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

fj=max⁡(fj,fj−wi+vi)f_j=\max{(f_j,f_{j-w_i}+v_i)}
385 Bcpp
#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;
}

多重背包​

有 nn 种物品和一个容量为 mm 的背包，每种物品有重量 wiw_i、价值 viv_i、数量 kik_i 三种属性。

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

tip

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

539 Bcpp
#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 w1,v1,k;
		cin>>w1>>v1>>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 普及组] 采药

在 TT 时间内采药，有 nn 株草药，第 ii 株采摘耗时 tit_i、价值 viv_i。每株至多采一次，求时间内能采到的最大总价值。