分组背包
1.定义
分组背包，通俗的讲就是，给你N组物品，然后每一组你至多选择一个物品(也可以不选),每个物品都有自己的体积和价值，现在给你一个容里为M的背包，让你用这个背包装物品，使得物品价值总和最大.
2.讲解
其实就类似于01背包，对于一个物品有两种决策选或不选，但是分组背包是在01背包的基础上对物品进行了分组，并且每一组只能最多选择一个物品，所以我们不妨用01背包的思想去思考分组背包.
分析：我们设f[i][j]为当前考虑到了第i组物品，剩余容里为j的背包能装物品的最大价值，那么很容易想到我们需要去枚举第i组物品，考虑选哪一个物品时最优的(或者不选)，状态转移方程就是
i
f
(
j
>
=
v
[
i
]
[
k
]
)
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
]
[
j
]
,
f
[
i
−
1
]
[
j
−
v
[
i
]
[
k
]
]
+
w
[
i
]
[
k
]
)
if(j>=v[i][k]) f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k])
if(j>=v[i][k])f[i][j]=max(f[i][j],f[i−1][j−v[i][k]]+w[i][k]),v[i][k]和w[i][k]分别表示第i组物品中第k个物品的体积和价值
代码：
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=1;k<=s[i];k++)
if(j>=v[i][k])
{
f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
这里我们还可以对空间进行优化，我们可以观察到，f[i][…]只会用到f[i-1][…]的值，所以数组的第一维的空间完全可以用滚动数组的方式处理掉，但是如何不影响状态转移呢，我们来看滚掉之后的状态转移方程，
f
[
j
]
=
m
a
x
(
f
[
j
]
,
f
[
j
−
v
[
i
]
[
k
]
]
+
w
[
i
]
[
k
]
)
f[j] = max(f[j],f[j-v[i][k]]+w[i][k])
f[j]=max(f[j],f[j−v[i][k]]+w[i][k]),这里的max里面的
f
[
j
]
和
f
[
j
−
v
[
i
]
[
k
]
]
f[j]和f[j-v[i][k]]
f[j]和f[j−v[i][k]]其实是
f
[
i
−
1
]
[
j
]
和
f
[
i
−
1
]
[
j
−
v
[
i
]
[
k
]
]
f[i-1][j]和f[i-1][j-v[i][k]]
f[i−1][j]和f[i−1][j−v[i][k]],而不是
f
[
i
]
[
j
]
和
f
[
i
]
[
j
−
v
[
i
]
[
k
]
]
f[i][j]和f[i][j-v[i][k]]
f[i][j]和f[i][j−v[i][k]]，所以我们需要对体积的遍历做一些修改，从大到小循环，如果还是从小到大循环的话，那么这里的
f
[
j
]
和
f
[
j
−
v
[
i
]
[
k
]
]
f[j]和f[j-v[i][k]]
f[j]和f[j−v[i][k]]的含义就有可能是
f
[
i
]
[
j
]
和
f
[
i
]
[
j
−
v
[
i
]
[
k
]
]
f[i][j]和f[i][j-v[i][k]]
f[i][j]和f[i][j−v[i][k]]，而不是我们需要的
f
[
i
−
1
]
[
j
]
和
f
[
i
−
1
]
[
j
−
v
[
i
]
[
k
]
]
f[i-1][j]和f[i-1][j-v[i][k]]
f[i−1][j]和f[i−1][j−v[i][k]]，可以模拟一下就明白了，只靠想的话有点抽象.
3.练习题
下面给大家一道经典分组背包的练习题(练手)
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1712
AC代码：
#include<bits/stdc++.h>
using namespace std;
int w[105][105];
int f[105]={0};
int main()
{
int n,m;
while(cin>>n>>m)
{
if(!n&&!m) break;
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>w[i][j];
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
for(int k=1;k<=m;k++)
if(j>=k)
{
f[j] = max(f[j],f[j-k]+w[i][k]);
}
cout<<f[m]<<'\n';
}
return 0;
}
依赖背包
1.定义
什么是依赖背包，顾名思义就是具有依赖属性，这种背包常见于树形结构上面，例如：一棵树有N个节点，每一个节点放有一个物品，这些物品有自己的体积和价值，但是如果你要选择v好节点的物品，那么必须先选择v的父亲节点上的物品(所谓的依赖关系)，现在你有容里为M的背包，问你选择物品的最大权值和是多少.
2.讲解
我们这里设dp[u][j]表示以u为根节点，背包剩余容里为j能够选择的物品的最大权值和，那么可想而知dp[u][j]这个值一定是由子节点更新来的，状态转移方程如下，用到了滚动数组优化
for(int i=m;i>=v[u];i--)
for(int k=0;k<=i-v[u];i++)
f[u][i] = max(f[u][i],f[u][i-k]+f[s][k]);
那么很显然答案就是f[root][m],root是我们的根节点
3.练习题
题目链接
https://www.luogu.com.cn/problem/P1273
这道题就是分组背包+依赖背包的结合体型，一道很经典的树形dp
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int Maxn = 3010;
struct Edge
{
int v;
int next;
int w;
}edge[10000];
int head[Maxn];
int val[Maxn];
int f[Maxn][Maxn];
int cnt = 0;
void build(int u,int v,int w)
{
edge[++cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt;
return ;
}
int n,m;
int dfs(int u)
{
if(u>(n-m))
{
f[u][1] = val[u];
return 1;
}
int sum = 0,now;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v = edge[i].v;
now = dfs(v);
sum+=now;
for(int j=sum;j>=0;j--)
for(int k=1;k<=now;k++)
{
if(j>=k)
f[u][j] = max(f[u][j],f[u][j-k]+f[v][k]-edge[i].w);
}
}
return sum;
}
int main()
{
memset(f,~0x7f,sizeof(f));
memset(head,-1,sizeof(head));
cin>>n>>m;
for(int i=1;i<=n;i++) f[i][0] = 0;
for(int i=1;i<=(n-m);i++)
{
int k;
cin>>k;
for(int j=1;j<=k;j++)
{
int A,C;
cin>>A>>C;
build(i,A,C);
}
}
for(int i=n-m+1;i<=n;i++) cin>>val[i];
dfs(1);
for(int i=m;i>=0;i--)
{
if(f[1][i]>=0)
{
cout<<i<<'\n';
break;
}
}
return 0;
}
题目连接
https://www.luogu.com.cn/problem/P2014
这是一道基于分组背包的模板题
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int Maxn = 400;
struct Edge
{
int v;
int next;
}edge[Maxn];
int cnt = 0;
int head[Maxn];
int w[Maxn];
int sz[Maxn];
int f[Maxn][Maxn];
void dfs(int u)
{
f[u][1] = w[u];
sz[u] = 1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v =edge[i].v;
dfs(v);
sz[u]+=sz[v];
for(int j=sz[u];j>=0;j--)
for(int k = 0;k<=sz[v];k++)
{
if(j>k) f[u][j] = max(f[u][j],f[u][j-k]+f[v][k]);
}
}
return ;
}
void build(int u,int v)
{
edge[++cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt;
return ;
}
int main()
{
memset(f,~0x7f,sizeof(f));
memset(head,-1,sizeof(head));
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) f[i][0] = 0;
for(int i=1;i<=n;i++)
{
int u;
cin>>u>>w[i];
build(u,i);
}
w[0] = 0;
dfs(0);
cout<<f[0][m+1]<<'\n';
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
