算法竞赛备赛——【背包DP】二维费用背包、分组背包
二维费用背包
有一个体积为V的背包，商店有n种物品，每种物品有一个价值v、体积w、重量m，每种物品仅有1个，问能够装下物品的最大价值。
这里每一种物品只有2种状态即“拿0个、1个”，但是需要同时考虑体积和重量的限制。
只需要在01背包的基础上稍加改动，将状态转移方程修改为二维的即可，同样是倒着更新
dp[i][j]表示当前体积为i，重量为j的情况下所能拿的物品的最大价值。
状态转移方程为dp[i][j]=max(dp[i][j],dp[i-w][j-m]+v)
例题
小蓝的神秘行囊
蓝桥 知识点：DP——二维费用背包
问题描述
小蓝是一名著名的探险家，他即将踏上一场寻宝的冒险旅程。他的目标是寻找和收集各种神秘的宝物。他有一个神秘的行囊，能够装载各种物品。然而，这个行囊有一个特殊的规定：它的最大容量是 V，并且它能承受的最大重量是 M。
小蓝来到一个古老的城堡，里面有 NN 件神秘的宝物，每件宝物只能被取走一次。每件宝物都有其特定的体积 vi，重量 mi，和价值 wi。
面对眼前的宝物，小蓝需要做出决定：将哪些宝物放入他的行囊，使得宝物的总体积不超过行囊的容量，总重量不超过行囊能承受的最大重量，且价值总和最大。
你的任务是帮助小蓝决定应该选择哪些宝物，并输出这些宝物的最大总价值。
输入格式
第一行是三个整数 N，V，M，用空格隔开，分别表示宝物的数量、行囊的容量和行囊能承受的最大重量。
接下来的 NN 行，每行有三个整数 vi，mi，wi，用空格隔开，分别表示每一件宝物的体积、重量和价值。
数据范围保证：
0<N≤1000，0<V,M≤100，0<vi,mi≤100，0<wi≤1000。
输出格式
输出一个整数，表示可以装入行囊的宝物的最大总价值。
样例输入
10 50 50
10 10 60
20 20 100
30 30 120
40 40 160
50 50 200
60 60 240
70 70 280
80 80 320
90 90 360
100 100 400
样例输出
220
#include<bits/stdc++.h>
using namespace std;
const int N=100+5;
using ll=long long;
ll dp[N][N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
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];
return 0;
}
分组背包
有一个体积为V的背包，商店有n组物品，每组物品有若干个价值v、体积w，每组物品中最多选1个，问能够装下物品的最大价值。
设状态dp[i][j]表示到第i组为止，体积为j的最大价值，在这里不能忽略第一维，否则可能导致状态转移错误! 与顺序无关可倒可正
状态转移方程为:dp[i][j]=dp[i-1]][j] dp[i][j]=max(dp[i][j],dp[i-1][j-w]+v);
例题
小明的背包5
蓝桥 知识点：DP——分组背包
题目描述
小明有一个容量为 V的背包。
这天他去商场购物，商场一共有 N 组物品，第 i 组里有 si件物品，物品的体积为 w，价值为 v，对于每一组只能购买一件物品。
小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 1 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
接下来有 N 组数据，对于每组数据的输入如下：
- 第一行输入一个整数 s，表示该组的物品个数。
- 接下来 s 行每行包含两个整数 w,v，表示物品的体积和价值。
1≤N,V≤10^2，1≤s≤10^2，1≤w,v≤10^3。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
3 58
2
1 4
1 6
1
4 9
2
5 5
4 5
输出
20
#include<bits/stdc++.h>
using namespace std;
const int N=100+5;
using ll=long long;
//dp[i][j]表示到第i组为止，体积为j的最大价值
int 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--){
int 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];
return 0;
}