树形依赖背包的两种实现形式

这里选取 洛谷 P2014 选课作为背景

第一种代码复杂度为O（N*V^2)

第二种代码复杂度为O(N*V)

代码

第一种代码转载至：https://blog.csdn.net/sdz20172133/article/details/82954419

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=310;
struct node
{
int v;///终端点
int next;///下一条同样起点的边号
int w;///权值
}edge[N*2];///无向边，2倍
int head[N];///head[u]=i表示以u为起点的所有边中的第一条边是 i号边
int tot;
///总边数
int minn;
void add(int u,int v)
{
edge[tot].v=v;
//edge[tot].w=w;
edge[tot].next=head[u];
head[u]=tot++;
}
int n,m;
int dp[N][N],val[N];
void dfs(int u,int fa)
{
dp[u][1]=val[u];///选一个肯定选自己这个结点
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v= edge[i].v;
///if(fa==v) continue;
///如果下一个相邻节点就是父节点，则证明到底层了，开始递归父节点的兄弟节点
dfs(v,u);
///分组背包
for(int j=m;j>0;j--)
///背包容量，倒叙，保证没有重复的物品
for(int k=0;k<j;k++)
///选择用户
{
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
}
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==0&&m==0) break;
memset(head,-1,sizeof(head));
memset(dp,0,sizeof(dp));
tot=0;
for(int i=1;i<=n;i++)
{
int w,v;
scanf("%d%d",&v,&w);
add(v,i);
val[i]=w;///题目直接给出第i节课的值
}
m++;
///我们可以0当作根节点，因为有的课可能没有先修课
val[0]=0;///虚拟构造了结点0
dfs(0,-1);
printf("%dn",dp[0][m]);
}
return 0;
}

第二种优化算法

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
#define maxn 400
struct Edge{
int v, next;
}edge[maxn];
int head[maxn], cnt, n, m;
int c[maxn];
int F[maxn][maxn];
void init(){
memset(head, -1, sizeof(head));
}
void add_edge(int u, int v){
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void Dp(int now, int iV)
{
if (iV <= 0) return ;
for (int i = head[now]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
for (int k = 0; k < iV; k ++) F[v][k] = F[now][k] + c[v];
Dp(v, iV - 1);
for (int k = 1; k <= iV; k ++) F[now][k] = max(F[now][k], F[v][k - 1]);
}
}
int main(){
int i, j, k, u, w;
scanf("%d%d",&n,&m);
init();
for(i = 1; i <= n; i++){
scanf("%d%d",&u,&w);
add_edge(u, i);
c[i] = w;
}
Dp(0,m);
printf("%dn",F[0][m]);
}

最后

以上就是粗暴口红为你收集整理的树形依赖背包的两种实现形式的全部内容，希望文章能够帮你解决树形依赖背包的两种实现形式所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。