前端之家收集整理的这篇文章主要介绍了
HDU 1561 依赖背包,
前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int N = 210;
int n,m;
int head[N],son[N];
int w[N];
int dp[N][N];
int max(int a,int b) {return a > b ? a : b;}
int dfs(int fa)
{
int i,j,k;
int tot = 1;
dp[fa][1] = w[fa];
for(i = son[fa]; i != -1; i = head[i])
{
tot += dfs(i); //剪枝,每次只用循环到当前能达到的最大值。
for(j = tot; j >= 1; j--)
for(k = 1; k+j <= tot+1; k++)
dp[fa][j+k] = max(dp[fa][j+k],dp[fa][j]+dp[i][k]);
}
return tot;
}
int main()
{
int i,k;
while(scanf("%d%d",&n,&m),n+m)
{
memset(son,-1,sizeof(son));
w[0] = 0;
for(i = 1; i <= n; i++)
{
scanf("%d%d",&j,w+i);
head[i] = son[j];
son[j] = i;
}
memset(dp,sizeof(dp));
dfs(0);
printf("%d\n",dp[0][m+1]);
}
return 0;
}
#include <stdio.h>
#include <string.h>
#define MAX 210
#define max(a,b) (a)>(b) ? (a) : (b)
struct node {
int v;
node *next;
}*head[MAX],tree[MAX];
int n,m,money[MAX];
int ptr,dp[MAX][MAX];
void Initial() {
ptr = 1;
memset(dp,sizeof(dp));
memset(head,NULL,sizeof(head));
}
void AddEdge(int fa,int son) {
tree[ptr].v = son;
tree[ptr].next = head[fa];
head[fa] = &tree[ptr++];
}
int Tree_DP(int v) {
int i,k,tot = 1;
node *p = head[v];
while (p != NULL) {
tot += Tree_DP(p->v);
int tp = tot < m ? tot : m; //加个剪枝,这个到目前为止能到达最大容量
for (j = tp; j >= 1; --j) //分组背包
for (i = 1; i <= j; ++i)
dp[v][j] = max(dp[v][j],dp[p->v][i]+dp[v][j-i]);
p = p->next;
}
if (v != 0) {
for (j = m; j >= 1; --j)
dp[v][j] = dp[v][j-1] + money[v]; //必选当前节点自己
}
return tot;
}
int main()
{
int i,a,b;
while (scanf("%d%d",n+m) {
Initial();
for (i = 1; i <= n; ++i) {
scanf("%d%d",&a,&b);
money[i] = b;
AddEdge(a,i);
}
Tree_DP(0);
printf("%d\n",dp[0][m]);
}
}