背包

类型

CPP

1.01背包
2.完全背包
3.多重背包
4.分组背包

01背包

出题形式

给定容量为m的背包有n个物品，第i个物品重量为w[i]价值为d[i],求该背包能放入的物品的最大价值之和

解题方法

四步法：

1.状态：dp[i][j]表示在前i个物品中选取物品，容量为j时，可以得到的最大价值

2.答案：dp[n][m]

3.转移：

CPP

if(j<w[i])dp[i][j]=max(dp[i][j],dp[i-1][j]+d[i]);
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+d[i]);

4.初始化： dp[0][j]=0;

实现代码如下

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,w[N],d[N],dp[3405][12885];
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i]>>d[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(j>=w[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+d[i]);
			else dp[i][j]=dp[i-1][j];
		}
	}
	cout<<dp[n][m];
	return 0;
}

可这个方法稍微数据大点，就会TLE和MLE

优化(滚动数组)

所以我们可以用滚动数组优化：优化空间复杂度，不改变时间复杂度;

也就是可以将dp从2维改成1维，具体实现代码如下

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int w[N],d[N],dp[N];
int n,m;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i]>>d[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=w[i];j--)
		{
			dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
		}
	}
	cout<<dp[m];
	return 0;
}

例题

1.P1802 5倍经验日

该题几乎都是板子，重量是打过要至少使用的药数量，代价是win[i]和llose[i]这个经验，但是要注意的就是即使装不下（题目里也就是打不过）也有代价（经验），最后输出要乘5即可

实现代码

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int lose[N],win[N],w[N],dp[N];
int n,m;
//价值-> 经验 
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>lose[i]>>win[i]>>w[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=0;j--)
		{
			if(j>=w[i])dp[j]=max(dp[j]+lose[i],dp[j-w[i]]+win[i]);
			else dp[j]=dp[j]+lose[i];
		}
	}
	cout<<5*dp[m];
	return 0;
}

重点题型

例题：CF577B

先读题，读完题后，可以按一下步骤思考

① 每个数可选可不选，且选择顺序不影响求和，考虑01背包

② 每次选一个数，和就会发生变化，而当和模m的余数为0代表整除，所以我们将研究对象转化为余数

③ 四步法

\Box \! \Box

(1).状态：dp[i][j]表示前i个数可选，且当前选的数的和模m的余数为j是是否有方案

\Box \! \Box

(2).答案：dp[n][0]==true输出YES,反之，输出NO

\Box \! \Box

(3).转移：

CPP

for(int i=1;i<=n;i++)
{
  for(int j=1;j<=n;j++)
  {
     if(dp[i-1][j]==true)
     {
        dp[i][j]=true;
        dp[i][(j+a[i])%m]=true;
     }
  }
}

\Box \! \Box

(4).初始化：dp[0][0]=true或dp[i][a[i]]=true,其余为false

④ 时间复杂度为O(nm),n<=1e6,m<=1e3会TLE且MLE

⑤ n个数的组合有

2^n

种，n不需太大，就可以得到远超m的方案数

⑥ 维护sum[i]表示前i个元素和模m的余数,sum[i]=(sum[i-1]+a[i])%m;

⑦ 若存在L<R,sum[L]==sum[R]则说明sum[R]-sum[L]==0,所以[L+1,R]相加是m的倍数

⑧ 根据抽屉原理，当位置大于等于m时，必然客户以选出两个位置同余，那么必然有区间和是m

思考完上面后，我们就可以开始写代码了