背包问题是指把一定数量的物体放在一定容量的背包中，物品通常有价值和体积两种属性，求能装下背包的最大价值。

01背包

每个物体只有取与不取两种状态，对应二进制的0和1，故被称为01背包。

状态转移方程

若已知第\(i\)个物品的价值为\(w_i\)，体积为\(v_i\)，设\(dp_{i,j}\)为前\(i\)个物品，容量为\(j\)的背包所能达到的最大价值。

当\(j\)小于\(v_i\)时，即当前容量无法装下该物品，得出\(dp_{i,j}=dp_{i-1,j}\) 。

当\(j\)不小于\(v_i\)时，即当前容量装得下该物品，得出\(dp_{i,j}=max(dp_{i,j},dp_{i-1,j-v_i}+w_i)\)

综上可得
​$$dp_{i,j}=\begin{cases}dp_{i-1,j}&j<v_i\\max(dp_{i,j},dp_{i-1,j-v_i}+w_i) &j>=v_i \end{cases}$$

优化

由二维形式递推方程可知数据不断从上一行传到下一行，所以上一行之前的数据是没用的。

则可以用一维数组记录每一行的状态，用下一行的新数据覆盖上一行的旧数据。

​\(dp_j=max(dp_j,dp_{j-v_i}+w_i)\)

不同于二维，一维形式下的\(j\)维度是逆序的，因为在一行中，每个数据是由前面的数据推得的。

如果是正序，前面的数据的就会被新数据覆盖，导致无法推出后面的的数据，但逆序就不存在这样的问题。

​

代码实现

二维

for(int i=1;i<=n;i++) //n为物品数量，m为背包容量
	for(int j=1;j<=m;j++) {
		dp[i][j]=dp[i-1][j];
		if(v[i]=<j) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
	}

一维

for(int i=1;i<=n;i++)
	for(int j=m;j>=v[i];j--) 
		dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

完全背包

完全背包模型与 01 背包类似，与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

转态转移方程

完全背包的状态转移方程以01背包的状态转移方程十分类似，其仅有一处\(dp_{i-1,j-v_i}\)和\(dp_{i,j-v_i}\)区别，而且也是通过01背包状态转移方程推导得来，具体过程略。

优化

完全背包的一维状态转移方程与01背包的一维状态转移方程完全相同，但是01背包的\(j\)维度是逆序的，而完全背包是正序的。

代码实现

二维

for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++) {
		dp[i][j]=dp[i-1][j];
		if(v[i]<=j) dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
	}

一维

for(int i=1;i<=n;i++)
	for(int j=v[i];j<=m;j++)
		dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

暴力二维

for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		for(int k=0;k*v[i]<=j;k++)
			dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i])

暴力二维的做法容易超时，通常使用优化二维和一维。

多重背包

多重背包也是 01 背包的一个变式。与 01 背包的区别在于每种物品有\(k_i\)个，而非一个。

转态转移方程

通常把多重背包拆成01背包，所以多重背包的状态转移方程和01背包一样。

优化

当数据太大时，普通做法会超时，所以可以采用二进制优化。把原来每个物品进行二进制拆分，通过这种拆分方式，可以表示任意\(\leq k\)个

物品的等效选择方式。然后使用 01 背包的方法解决即可。

代码实现

直接给出一维

for(int i=1;i<=n;i++) {
	int a,b,c; //c为数量
	cin>>a>>b>>c;
	for(int j=1;j<=c;j++) {
		v[cnt]=a;
		w[cnt]=b;
		cnt++;
	}
} //拆成01背包

for(int i=1;i<=cnt;i++)
	for(int j=m;j>=v[i];j--)
		dp[j]=max(dp[j],dp[j-v[i]]+w[i]); //转态转移方程

二进制优化

for(int i=1;i<=n;i++) {
	int a,b,c;
	cin>>a>>b>>c;

    int k=1;
	while(k<=c) {
		v[cnt]=a*k;
		w[cnt]=b*k;
		c-=k;k*=2;
		cnt++;
	}

	if(c>0) {
		v[cnt]=a*c;
		w[cnt]=b*c;
		cnt++;
	} //二进制拆分
}

for(int i=1;i<=cnt;i++) 
	for(int j=m;j>=v[i];j--)
		dp[j]=max(dp[j],dp[j-v[i]]+w[i]); //状态转移方程

分组背包

分组背包指在每一组中选一个物品。

状态转移方程

设\(dp_{i,j}\)为前\(i\)组中选，且总体积不超过\(j\)的所有方案的最大值，\(v_{i,k}\)表示第\(i\)组的第\(k\)个物品的体积，\(w_{i,k}\)表示第\(i\)组的第\(k\)个物体的价值。则有

​$$dp_{i,j}=\begin{cases}dp_{i-1,j}&j<v_{i,k}\\max(dp_{i,j},dp_{i-1,j-v_{i,k}}+w_{i,k}) &j\geq v_{i,k} \end{cases}$$

优化

因为只用到两列，所以也可已仿造01背包的套路优化。

代码实现

二维

for(int i=1;i<=n;i++) { //n为组数
	cin>>s[i];
	for(int j=1;j<=s[i];j++) 
		cin>>v[i][j]>>w[i][j];
} //s[i]为第i组的物品个数

for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++) {
		dp[i][j]=dp[i-1][j];
		for(int k=1;k<=s[i];k++)
			if(v[i][k]<=j) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i][k]]+w[i][k]); //状态转移方程
	}

一维

for(int i=1;i<=n;i++) {
	cin>>s[i];
	for(int j=1;j<=s[i];j++)
		cin>>v[i][j]>>w[i][j];
}

for(int i=1;i<=n;i++)
	for(int j=m;j>0;j--) //j维度逆序，枚举到0
		for(int k=1;k<=s[i];k++) 
			if(v[i][k]<=j) dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]); //要判条件，因为j是枚举到0

背包的变形

在实际使用中，通常要对背包进行变形。主要思想就是找出“容量”，“价值”和“体积”三大属性。

1.装箱问题

有一个箱子容量为 \(V\)，同时有 \(n\) 个物品，每个物品有一个体积。

现在从 \(n\) 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 \(V\)，表示箱子容量。

第二行共一个整数 \(n\)，表示物品总数。

接下来 \(n\) 行，每行有一个正整数，表示第 \(i\) 个物品的体积。

输出格式

共一行一个整数，表示箱子最小剩余空间。

样例输入

24
6
8
3
12
7
9
7

样例输出

0

提示

对于 \(100\%\) 数据，满足 \(0<n \le 30\)，\(1 \le V \le 20000\)。

思路

这道题每个物品的价值就是它的体积。

代码

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int dp[40][20010];
int w[40];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);

	int v,n;
	cin>>v>>n;

	for(int i=1;i<=n;i++)
		cin>>w[i];

	for(int i=1;i<=n;i++) 
		for(int j=1;j<=v;j++) {
			dp[i][j]=dp[i-1][j];
			if(w[i]<=j) dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+w[i]);
		}

	cout<<v-dp[n][v]<<"\n";

	return 0;
}

2.小A点菜

uim 由于买了一些书，口袋里只剩 \(M\) 元 \((M \le 10000)\)。

餐馆虽低端，但是菜品种类不少，有 \(N\) 种 \((N \le 100)\)，第 \(i\) 种卖 \(a_i\) 元 \((a_i \le 1000)\)。由于是很低端的餐馆，所以每种菜只有一份。

小 A 奉行“不把钱吃光不罢休”，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。

由于小 A 肚子太饿，所以最多只能等待 \(1\) 秒。

输入格式

第一行是两个数字，表示 \(N\) 和 \(M\)。

第二行起 \(N\) 个正数 \(a_i\)（可以有相同的数字，每个数字均在 \(1000\) 以内）。

输出格式

一个正整数，表示点菜方案数，保证答案的范围在 int 之内。

样例输入

4 4
1 1 2 2

样例输出

3

思路

这道题的价值是刚好把钱花完的点菜方法。

可得出转态转移方程

代码

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int dp[110][10010];
int v[110];

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);

	int n,m;
	cin>>n>>m;

	for(int i=1;i<=n;i++)
		cin>>v[i];

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

	cout<<dp[n][m]<<"\n";

	return 0;
}

3.五倍经验日

现在乐斗有活动了！每打一个人可以获得 5 倍经验！absi2011 却无奈的看着那一些比他等级高的好友，想着能否把他们干掉。干掉能拿不少经验的。

现在 absi2011 拿出了 \(x\) 个迷你装药物（嗑药打人可耻…），准备开始与那些人打了。

由于迷你装药物每个只能用一次，所以 absi2011 要谨慎的使用这些药。悲剧的是，用药量没达到最少打败该人所需的属性药药量，则打这个人必输。例如他用 \(2\) 个药去打别人，别人却表明 \(3\) 个药才能打过，那么相当于你输了并且这两个属性药浪费了。

现在有 \(n\) 个好友，给定失败时可获得的经验、胜利时可获得的经验，打败他至少需要的药量。

要求求出最大经验 \(s\)，输出 \(5s\)。

输入格式

第一行两个数，\(n\) 和 \(x\)。

后面 \(n\) 行每行三个数，分别表示失败时获得的经验 \(\mathit{lose}_i\)，胜利时获得的经验 \(\mathit{win}_i\) 和打过要至少使用的药数量 \(\mathit{use}_i\)。

输出格式

一个整数，最多获得的经验的五倍。

样例输入

6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2

样例输出

1060

提示

【数据范围】

• 对于 \(10\%\) 的数据，保证 \(x=0\)。
• 对于 \(30\%\) 的数据，保证 \(0\le n\le 10\)，\(0\le x\le 20\)。
• 对于 \(60\%\) 的数据，保证 \(0\le n,x\le 100\)， \(10<lose_i,win_i\le 100\)，\(0\le use_i\le 5\)。
• 对于 \(100\%\) 的数据，保证 \(0\le n,x\le 10^3\)，\(0<lose_i\le win_i\le 10^6\)，\(0\le use_i\le 10^3\)。

思路

这道题的问题在于没打过也有“价值”可加，所以在基本的状态转移方程后，还要加一个不能打过的状态转移方程。

代码

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int dp[1010];
int l[1010],w[1010],u[1010];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);

	int n,x;
	cin>>n>>x;

	for(int i=1;i<=n;i++)
		cin>>l[i]>>w[i]>>u[i];

	for(int i=1;i<=n;i++) {
		for(int j=x;j>=u[i];j--)
			dp[j]=max(dp[j]+l[i],dp[j-u[i]]+w[i]);
		for(int j=u[i]-1;j>=0;j--)
			dp[j]+=l[i]; //没打过的状态转移方程
	}

	cout<<5ll*dp[x]<<"\n";

	return 0;
}

4.L国的战斗之间谍

L国即将与I国发动战争！！

俗话说的好：“知己知彼，百战不殆”。L国的指挥官想派出间谍前往I国，于是，选人工作就落到了你身上。

你现在有N个人选，每个人都有这样一些数据：A（能得到多少资料）、B（伪装能力有多差）、C（要多少工资）。已知敌人的探查间谍能力为M（即去的所有人B的和要小于等于M）和手头有X元钱，请问能拿到多少资料？

输入格式

\(N\) \(M\) \(X\)

\(A_1\) \(B_1\) \(C_1\)

\(A_2\) \(B_2\) \(C_2\)

………………

\(A_n\) \(B_n\) \(C_n\)

输出格式

能得到的资料总数

样例输入

3 10 12
10 1 11
1 9 1
7 10 12

样例输出

11

提示

【数据范围】

1≤n≤100,1≤m≤1000, 1≤x≤1000

思路

这道题有两个“价值”，因此也要多一个维度。

代码

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int dp[1010][1010];
int a[110],b[110],c[110];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);

	int n,m,x;
	cin>>n>>m>>x;

	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i]>>c[i];

	for(int i=1;i<=n;i++) 
		for(int j=m;j>=b[i];j--)
			for(int k=x;k>=c[i];k--)
				dp[j][k]=max(dp[j][k],dp[j-b[i]][k-c[i]]+a[i]);

	cout<<dp[m][x]<<"\n";

	return 0;
}

5.A+B Problem plus

给定一个正整数 \(n\)，求将其分解成若干个素数之和的方案总数。

输入格式

一行一个正整数 \(n\)。

输出格式

一行一个整数表示方案总数。

样例输入

7

样例输出

3

提示

【样例解释】存在如下三种方案：

• \(7=7\)。
• \(7=2+5\)。
• \(7=2+2+3\)。

【数据范围】

• 对于 \(30\%\) 的数据 \(1\le n\le 10\)。
• 对于 \(100\%\) 的数据，\(1\le n\le 10^3\)。

思路

这道题的物品数量为\(n\)以前的质数的数量，体积为\(n\)，价值为\(dp_j\)

代码

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e6+10;

ll dp[1010];
int p[N],vis[N];

int eular_sieve(int n) {
	int cnt=0;
	for(int i=2;i<=n;i++) {
		if(!vis[i]) p[cnt++]=i;
		for(int j=0;j<cnt&&p[j]<=n;j++) {
			vis[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);

	int n;
	cin>>n;
	int cnt=eular_sieve(n);

	dp[0]=1;
	for(int i=0;i<cnt;i++)
		for(int j=p[i];j<=n;j++) {
			dp[j]=max(dp[j],dp[j-p[i]]+dp[j]);
		}

	cout<<dp[n]<<"\n";

	return 0;
}