有依赖的背包问题
有 N 个物品和一个容量是 V 的背包。
物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点。
如下图所示:
如果选择物品5,则必须选择物品1和2。这是因为2是5的父节点,1是2的父节点。
每件物品的编号是 i,体积是 v~i~,价值是 w~i~,依赖的父节点编号是 p~i~。物品的下标范围是 1…N。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N,V,用空格隔开,分别表示物品个数和背包容量。
接下来有 N 行数据,每行数据表示一个物品。
第 i 行有三个整数 v~i~,w~i~,p~i~,用空格隔开,分别表示物品的体积、价值和依赖的物品编号。
如果 p~i~=−1,表示根节点。 数据保证所有物品构成一棵树。
输出格式
输出一个整数,表示最大价值。
数据范围
1≤N,V≤100
1≤v~i~,w~i~≤100
父节点编号范围:
- 内部结点:1≤p~i~≤N;
- 根节点 p~i~=−1;
输入样例
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2
输出样例:
11
思路
这道题是树形dp,老样子,闫式dp分析法
状态表示f[x][i][j]:表示以x为根的子树的前i个子节点子树中选,总体积不超过j的所有集合,属性:max
状态计算f[x][i][j]:
通过递归的方式求出最终解,所以每层dfs是为了,求出当前以x为根的子树的的子节点子树中,每颗子树到底分配
多少体积的所有情况,把一个子树看做成一个组,一组内不同方案,相当于给改组分配不同体积,只看后面两个[i]
[j]代表的是在前i个组中选,总体积不超过j的所有集合,属性max,就相当于分组背包问题
f[x][i][j]=max(f[x][i][j],f[x][i-1][j-k]+f[u][u_son][k])
(u是x的子节点,u_son是u这个节点的子节点个数),代码如下,有优化版和未优化版
好多人表示看不懂y总的代码,y总代码其实就是优化版,y总在做分组背包的时候,直接写的是一维dp,所以很多人
看不懂,优化的时候,发现,我们最终只会用到当前节点x的上一层状态,和子节点的最终状态,所以可以减少一维
,枚举体积的时候,倒着枚举即可
代码(未优化版)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N=110;
vector<int> son[N]; //用来存储每个节点的子节点
int v[N],w[N];
int f[N][N][N];
int n,m;
void dfs(int x){
//进行初始化,当体积小于v[x]的时候是0,大于等于v[x]的时候是w[x]
for(int j=v[x];j<=m;j++) f[x][0][j]=w[x];
//下面进行分组背包,从前i个子树中选,总体积不超过j的所有集合,属性max
for(int i=1;i<son[x].size();i++){
int u=son[x][i];
int u_son=son[u].size()-1;
dfs(u);
for(int j=v[x];j<=m;j++){ //这里从v[x]开始,因为至少要包含x根节点
for(int k=0;k<=j-v[x];k++){ //这里要k<=j-v[x]是因为根节点必须包含,要给根节点留空间
f[x][i][j]=max(f[x][i][j],f[x][i-1][j-k]+f[u][u_son][k]);
}
}
}
}
int main(){
cin>>n>>m;
int root;
for(int i=1;i<=n;i++) son[i].push_back(0); //将下标改成从1开始,方便后面运算
for(int i=1;i<=n;i++){
int p;
cin>>v[i]>>w[i]>>p;
if(p==-1) root=i;
else son[p].push_back(i);
}
dfs(root);
cout<<f[root][son[root].size()-1][m]<<endl;
return 0;
}
代码(优化版)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N=110;
vector<int> son[N]; //用来存储每个节点的子节点
int v[N],w[N];
int f[N][N];
int n,m;
void dfs(int x){
//进行初始化,当体积小于v[x]的时候是0,大于等于v[x]的时候是w[x]
for(int j=v[x];j<=m;j++) f[x][j]=w[x];
//下面进行分组背包,从前i个子树中选,总体积不超过j的所有集合,属性max
for(int i=1;i<son[x].size();i++){
int u=son[x][i];
//int u_son=son[u].size()-1;
dfs(u);
for(int j=m;j>=v[x];j--){ //这里从v[x]开始,因为至少要包含x根节点,这里需要倒着枚举,因为减少了一维
for(int k=0;k<=j-v[x];k++){ //这里要k<=j-v[x]是因为根节点必须包含,要给根节点留空间
f[x][j]=max(f[x][j],f[x][j-k]+f[u][k]);
}
}
}
}
int main(){
cin>>n>>m;
int root;
for(int i=1;i<=n;i++) son[i].push_back(0); //将下标改成从1开始,方便后面运算
for(int i=1;i<=n;i++){
int p;
cin>>v[i]>>w[i]>>p;
if(p==-1) root=i;
else son[p].push_back(i);
}
dfs(root);
cout<<f[root][m]<<endl;
return 0;
}
# Or2
非常优秀
终于看懂了!
非常优秀,好帖,顶顶
真的好棒!!
这个解析 最牛逼
解答了一部分我不懂的地方