二维、多维费用的背包问题

多维费用的背包问题是指：对于每件物品，具有两种及以上不同的费用；选择这件物品必须同时付出这若干种代价（比如体积和重量）；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。

二维01背包

8. 二维费用的背包问题 - AcWing题库

P1910 L 国的战斗之间谍 - 洛谷

以二维为例，设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为w1[i]和w2[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为c[i]。

费用加了一维，只需在状态也加一维即可。

1. 状态定义

   设dp[i][j][k]表示前i件物品付出两种代价分别为j和k时可获得的最大价值。

2. 转移方程

相当于将两个01背包相结合。所以方程：

dp[i][j][k]=max{dp[i-1][j][k],dp[i-1][j-w1[i]][k-w2[i]]+v[i]}。

如前述方法，可以只使用二维的数组（二维的滚动数组）：当每件物品只可以取一次时变量j和k采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。

空间优化后的转移方程：
dp[j][k] = max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]);

3. 初始化&填表&最终答案

和01背包一样，若是求最大价值的同时不要求填满，则dp[i][j][k]或dp[j][k]初始化为0，否则需要根据实际意义去初始化。

除了第1层循环枚举物品，内层每一层都可以看成是01背包，将两层嵌套枚举即可。

物品总个数的限制：
有时，二维费用的条件是以这样一种隐含的方式给出的：
最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。

换句话说，设dp[i][j]表示付出费用i、最多选j件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，
最后在dp[0..i][0..j]范围内寻找答案。
另外，如果要求“恰取M件物品”，则在dp[0..i][M]范围内寻找答案。

8. 二维费用的背包问题 - AcWing题库参考程序：

#include <iostream>
using namespace std;

const int NUM = 1001;
int N, M, V;//数量，承重，体积
int v[NUM], m[NUM], w[NUM];//每件物品的体积，重量，价值
int dp[101][101];//dp[i][j]表在i体积，j重量下的最大价值

int main()
{
	cin >> N >> V >> M;
	for (int i = 1; i <= N; i++)
		cin >> v[i] >> m[i] >> w[i];
	for (int i = 1; i <= N; i++) 
		for (int j = V; j >= v[i]; j--) 
			for (int k = M; k >= m[i]; k--) 
				dp[j][k] = max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]);
	cout << dp[V][M];
	return 0;
}

P1910 L 国的战斗之间谍 - 洛谷

还是二维01背包。这次进行了流程优化。

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

int main() {
	int n, m, x;
	cin >> n >> m >> x;
	vector<vector<int> >dp(m + 1, vector<int>(x + 1, 0));
	for (int i = 1, a, b, c; i <= n; i++) {
		cin >> a >> b >> c;
		for (int i = m; i >= b; i--)
			for (int j = x; j >= c; j--)
				dp[i][j] = max(dp[i][j], dp[i - b][j - c] + a);
	}
	cout << dp[m][x];
	return 0;
}

多维不同种的背包没遇到过类似的题，遇到了再补充。

OJ题

宠物小精灵之收服 经过包装的二维01背包

1292：宠物小精灵之收服

这是一道经过包装的OJ题。

拿到陌生的和实际生活有联系的题，首先尝试拆解题干变成学过的模型。

在这题中，关键词精灵球的数量和皮卡丘的体力相当于两个容器的容量，每只小精灵可选择收服或不收服，类似01背包的选或不选。

他说目标是收服尽可能多的小精灵，相当于每只精灵的价值都为1。

到这里已经拆解完毕，是二维费用的背包问题，由两个01背包的容量约束。

最后还附加了要求：相同价值（或者说收服同样的小精灵数）的情况下皮卡丘的体力损耗最小，两个维度的损耗同时为最小不现实，题目也没说消耗的精灵球的数量也是最小的， 因此可以固定精灵球的最大消耗，看有没有更小的体力消耗的情况下，捕捉到的精灵数和皮卡丘拼尽全力捕捉到的精灵数相同，有的话那个情况下消耗的体力数就是答案。

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS 1
#endif

#include<iostream>
#include<vector>
using namespace std;

void ac1(){
	int N,M,K;
	cin>>N>>M>>K;
	vector<int>n(K+1,0),m(K+1,0);
	vector<vector<int> >dp(N+1,vector<int>(M+1,0));
	for(int i=1;i<=K;i++)
		cin>>n[i]>>m[i];
	for(int i=1;i<=K;i++)
		for(int j=N;j>=n[i];j--)
			for(int k=M;k>=m[i];k--)
				dp[j][k]=max(dp[j][k],dp[j-n[i]][k-m[i]]+1);
	for(int i=1;i<=M;i++)
		if(dp[N][i]==dp[N][M]){
			cout<<dp[N][M]<<' '<<M-i;
			return;
		}
}

int main() {
	ac1();
	return 0;
}

潜水员 求最小价值的二维01背包

1271：【例9.15】潜水员

这是一个特殊的二维费用的背包问题，特殊在他求的是“最小价值”。

1. 状态定义

记dp[i][j]表示已选的气缸，在氧气总量不小于需求的容量i和氮气不小于需求的容量j的情况下，这些气缸的最小重量。所以最终答案是dp[m][n]，m、n是潜水员对气体的最大需求量。

2. 转移方程

设要选的某个气缸的氧气、氮气和容量分别为O、N和W。

若不选，则继续使用已选的气缸。

若选了这个气缸，则求dp[i][j]这个大问题，变成了已经负重W的情况下，氧气总量不小于需求容量i-O和氮气不小于需求容量j-N的情况下，还需要选的气缸的最小重量这个子问题，也就是dp[i-O][j-N]+W。

对选择了这个气缸的决策，存在一种特殊情况：若这个新气缸满足i<O和j<N的同时，重量也比之前选的所有气缸的总重还要轻，正常情况应该抛弃之前选的所有气缸，选择这个新气缸。因为i-O和j-N都小于零，无法用数组表示状态，所以对这种特殊情况应该用
dp[0][0]+W表示。

可以设_O=O>i?i:O和_N=N>j?j:N，则子问题dp[i-_O][j-_N]可以表示所有情况。

所以最终的转移方程：

dp[i][j]=min(dp[i][j],dp[i-_O][j-_N]+W)。

3. 初始化&填表

因为求的是最小重量，所以dp[i][j]要初始化为无穷大。

同时dp[0][0]表示无需求的情况下，已选的气缸的重量，这个特殊情况需要初始化为零。

填表时第1层循环枚举气缸，第2层和第3层分别逆序枚举气体的需求量，因为这里的状态表示其实更像是空间优化的二维01背包。

参考程序：

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS 1
#endif

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

void ac1() {
	int m, n, kk;
	cin >> m >> n >> kk;
	vector<vector<int> >dp(m + 1, vector<int>(n + 1, 0x3f3f3f3f));
	dp[0][0] = 0;
	for (int cnt = 1, O, N, W; cnt <= kk; cnt++) {
		cin >> O >> N >> W;
		for (int i = m; i >= 0; i--)
			for (int j = n; j >= 0; j--) {
				int _O = O > i ? i : O;
				int _N = N > j ? j : N;
				dp[i][j] = min(dp[i][j], dp[i - _O][j - _N] + W);
			}
	}
	cout << dp[m][n];
}

int main() {
	ac1();
	return 0;
}

多维费用背包OJ汇总

1. 二维01背包模板题

8. 二维费用的背包问题 - AcWing题库

P1910 L 国的战斗之间谍 - 洛谷

2. 二维01背包的变种

1292：宠物小精灵之收服

1271：【例9.15】潜水员