本文主要是介绍背包（5）Hdu 1561 The more, The Better（有限制的背包，分组背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//dp[i][j]表示当前访问节点序号是i，且在i所在主枝里停留j。
//dp[i][j]=max(dp[i][j],dp[i][j-r]+dp[t][r])， t为i的一个子节点。
//以i为根节点的所有节点组成的树看做整棵树的一个主枝。再在主枝的不同副枝里分配不同的份额，使获得收益最大。
//在副枝里分配份额，又可以看做是分组背包，因为在每个每个枝节中只选择一种方式。
#include<cstdio>
#include<vector>
#include<algorithm>
#define MAX 205
using namespace std;
int visit[205];
int ans[205][205];
vector<int>r[300];//存下级节点。
int m;
int max(int x,int y)
{return x>y?x:y;}
void dfs(int x)
{
visit[x] = 1;
int u;
for (int i = 0; i < r[x].size(); i++)
{
u = r[x][i];
if(!visit[u])
{
dfs(u);
for (int j = m; j >=1 ; j--)
{
for (int k = 1; k < j; k++)
{
if(ans[x][j-k]!=-1 && ans[u][k]!=-1)//保证前面的节点都被更新过。
ans[x][j] = max(ans[x][j],ans[x][j-k]+ans[u][k]);
//转移方程。ans[x][j]当前访问节点为x，并分配给x所在主枝j个城堡去占领可以获得的最大财宝。等于在x分配j-k，在分支u内分配k。所能达到的最大值。
}
}
}
}
}
int main()
{
int n;
int x;
while(~scanf("%d %d",&n,&m))
{
memset(ans,-1,sizeof(ans));
memset(visit,0,sizeof(visit));
if(n==0 && m==0) break;
for (int i = 0; i <= n; i++)
{
r[i].clear();
}
ans[0][0] = ans[0][1] = 0;//把零号节点初始化为0。
for (int i = 1; i <= n; i++)
{
ans[i][0] = ans[0][i] = 0;
scanf("%d %d",&x,&ans[i][1]);
r[x].push_back(i); //加上0号节点，原图就由森林变成了树，便于处理。
}
m++;
dfs(0); //从根节点开始递归。
printf("%d\n",ans[0][m]);
}
return 0;
}
这篇关于背包（5）Hdu 1561 The more, The Better（有限制的背包，分组背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
