这是背包问题的最后一个专题,我们先讲二维费用背包,
二维费用背包问题和01背包问题都是经典的背包问题的变体,其区别在于对于每个物品,是否考虑其费用。
在01背包问题中,每个物品要么选中(放入背包),要么不选中,每个物品只有一个对应的费用。目标是选取一些物品放入背包,使得背包的总容量不超过限定值,同时价值之和达到最大。
而在二维费用背包问题中,每个物品除了考虑是否选中外,还需要考虑该物品的两个费用(如重量和体积)。目标是选取一些物品放入背包,使得背包的总容量和总重量都不超过限定值,同时价值之和达到最大。那么相应的状态转移方程就会有所不同,我们一般设dp[i] [j]表示当前体积为i ,重量为 j 的情况下所能拿的物品的最大价值。状态转移方程为
dp[ i] [j] =max(dp[ i] [ j].dp[i - w] [j - m] + v);
这是一个大致的二维费用背包的模板
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义二维费用背包问题的函数
int twoDimensionalKnapsack(int n, int capacity1, int capacity2, vector<int>& cost1, vector<int>& cost2, vector<int>& value) {
vector<vector<int>> dp(capacity1 + 1, vector<int>(capacity2 + 1, 0));
for (int k = 0; k < n; ++k) {
for (int i = capacity1; i >= cost1[k]; --i) {
for (int j = capacity2; j >= cost2[k]; --j) {
dp[i][j] = max(dp[i][j], dp[i - cost1[k]][j - cost2[k]] + value[k]);
}
}
}
return dp[capacity1][capacity2];
}
int main() {
// 示例数据
int n = 3;
int capacity1 = 5, capacity2 = 6;
vector<int> cost1 = {2, 3, 4};
vector<int> cost2 = {1, 2, 3};
vector<int> value = {5, 7, 9};
// 调用二维费用背包函数,并输出结果
int result = twoDimensionalKnapsack(n, capacity1, capacity2, cost1, cost2, value);
cout << "The maximum value is: " << result << endl;
return 0;
}
为了加深对二维费用背包的思想的印象,我们通过一道例题来理解下,
小蓝是一名著名的探险家,他即将踏上一场寻宝的冒险旅程。他的目标是寻找和收集各种神秘的宝物。他有一个神秘的行囊,能够装载各种物品。然而,这个行囊有一个特殊的规定:它的最大容量是 V,并且它能承受的最大重量是 M。
小蓝来到一个古老的城堡,里面有 N件神秘的宝物,每件宝物只能被取走一次。每件宝物都有其特定的体积 vi,重量 mi,和价值 wi。
面对眼前的宝物,小蓝需要做出决定:将哪些宝物放入他的行囊,使得宝物的总体积不超过行囊的容量,总重量不超过行囊能承受的最大重量,且价值总和最大。
你的任务是帮助小蓝决定应该选择哪些宝物,并输出这些宝物的最大总价值。
这个题目可以完全套用以上代码,由于代码整体量比较小,现在给出完整代码。
#include <iostream>
using namespace std;
using ll = long long;
ll dp[105][105];
int main()
{
int n,V,M;cin>>n>>V>>M;
for(int i = 1; i<=n;i++)
{
int v,m,w;cin>> v >> m >> w;
for(int j = V ;j>=v ;j--)
{
for(int k = M ;k >=m;k--)
{
dp[j][k] = max (dp[j][k],dp[j - v][k - m] + w);
}
}
}
cout << dp[V][M] <<endl;
return 0;
}
接下来讲讲分组背包,,01背包问题是在一组物品中做选择,每个物品只能选一次;而分组背包问题是将物品分成若干组,每组内的物品只能选一个,不同组之间的选取可能相互影响。状态转移方程分为两种:
- 不选择第
k
个物品:dp[i][j] = dp[i-1][j]
- 选择第
k
个物品:dp[i][j] = max(dp[i][j], dp[i-1][j-volume[k]] + value[k])
我们同样根据一道例题来加深印象,
小明有一个容量为 VV 的背包。
这天他去商场购物,商场一共有 NN 组物品,第 ii 组里有 sisi 件物品,物品的体积为 ww,价值为 vv,对于每一组只能购买一件物品。
小明想知道在购买的物品总体积不超过 VV 的情况下所能获得的最大价值为多少,请你帮他算算。
大致思路:
首先通过输入获取了物品的组数和背包的容量,并利用二维数组 dp 存储动态规划的结果。然后通过循环遍历每一组物品,内层循环处理每个物品,并根据状态转移方程更新 dp 值。最后输出在给定背包容量下能够获得的最大价值。
这里给出完整解决代码(可作为相应 的分组背包的模板):
#include <iostream>
using namespace std;
using ll = long long;
const int N = 150;
ll dp[N][N];
int main()
{
int n,V;cin>> n >> V;
for(int i =1 ;i<=n;i++)
{
int s;cin>>s;
for(int j = 0;j <=V;j++)dp[i][j] = dp[i- 1][j];
while(s--)
{
ll w,v;cin>>w>>v;
for(int j = w;j<=V;j++)dp[i][j] = max(dp[i][j],dp[i - 1][j -w] + v);
}
}
cout << dp[n][V] << '\n';
return 0;
}
原二维费用背包题目链接:
https://www.lanqiao.cn/problems/3937/learning/?page=1&first_category_id=1&problem_id=3937
原分组背包题目链接:
https://www.lanqiao.cn/problems/1178/learning/?page=1&first_category_id=1&problem_id=1178