首页 > ACM题库 > HDU-杭电 > HDU 3593-The most powerful force-背包问题-[解题报告]HOJ
2014
11-27

HDU 3593-The most powerful force-背包问题-[解题报告]HOJ

The most powerful force

问题描述 :

The leaders of AC country made a decision to regain the TW Island. But they have to face the powerful force from USB. So the leaders have to hire some excellent soldiers from the training base called ALPC to format the most powerful force.
The followings are the consists of ALPC:
1.  There are more than one alpcs who are generals, like alpc04.
2.  Every alpc has a direct superior, except the generals.
3.  The alpc who has underling is an officer (Every officer’ number is no more than 500, like alpc21, alpc32).
4.  If send one alpc to the war, so will his direct superior. Of course the general’s direct superior is himself.
5.  Every alpc has two values. Vi is the fighting strength and Ci is the cost that the leader have to pay for the soldier.

Due to the AC country has limited financial resources, the leaders want to format the most powerful force with the cost not exceed G. Obviously, it is an uphill task! Therefore, the leaders of the AC country have assigned the task to alpc72 because of the outstanding behavior he had done at the ACM/ICPC. But alpc72 has been lost in hunting PLMM nowadays, so that he has no time to deal with this problem. What’s more, he left it to you.

输入:

There will have several test cases.
The first line has two integers N and G, which stand for the total number of soldiers and the maximum cost. Soldiers numbered consequently from 1 to N. (1<=N<=100000, 1<=G<=10000)
The next N lines, each has three integers Ci, Vi and Fi. They are the cost, the measure of power and the direct superior of the ith soldier. (0<=Ci<=1000000, 0<=Vi<=1000000)

输出:

There will have several test cases.
The first line has two integers N and G, which stand for the total number of soldiers and the maximum cost. Soldiers numbered consequently from 1 to N. (1<=N<=100000, 1<=G<=10000)
The next N lines, each has three integers Ci, Vi and Fi. They are the cost, the measure of power and the direct superior of the ith soldier. (0<=Ci<=1000000, 0<=Vi<=1000000)

样例输入:

5 10
1 2 1
10 5 2
1 1 1 
1 1 1
1 1 3
5 10
1 2 1
2 4 2
1 1 1 
1 1 1
1 1 3

样例输出:

5
9

Hint
Special Thanks to alpc30.

   根据题意我们可以判断出很明显是一个树形的DP,但是从何入手呢。

  显然我们还是可以按照对于某一个点分取和不取两种状态,那么由于闲置费用的引入我们很容易就想到了背包问题(体积限制)。我们不妨假设0为根节点。显然对于每一个非叶子节点 i 以他为根的子树在费用dp[ i ][ v ]的最大收益就可以通过其儿子节点来求:如果他的儿子是个叶子节点,那么要么取要么不取,就是0、1背包的问题了;如果儿子不是叶子节点那么再把它的儿子节点形成的子树“打包”(实际上就是乡下递归),只不过这个“子树包”可不能就当成0、1背包处理了,因为他的v’是随着你给出的c改变的,其实就是类似泛化物品,按照类似方法处理即可。

#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;

int head[100050];
int N,G;
int c[100050],v[100050],dp[505][10005];

struct NODE
{
    int to,next;
}edge[300000];

void dfs(int x,int V)
{
    int i,j,k,to;
    for(i=head[x];i!=-1;i=edge[i].next)
    {
        to=edge[i].to;
        if(head[to] == -1)
        {
            for(j=V;j>=c[to];j--)
            {
                dp[x][j]=max(dp[x][j],dp[x][j-c[to]]+v[to]);
            }
        }
        else
        {
            if(V >= c[to])
            {
                for(j=0;j<=V-c[to];j++) dp[to][j]=dp[x][j];
                dfs(to,V-c[to]);
                for(j=V;j>=c[to];j--)
                {
                    dp[x][j]=max(dp[x][j],dp[to][j-c[to]]+v[to]);
                }
            }
        }
    }
}

int main()
{
    while(~scanf("%d %d",&N,&G))
    {
        int i,j,k;
        memset(head,-1,sizeof(head));
        memset(dp,0,sizeof(dp));
        for(i=1;i<=N;i++)
        {
            scanf("%d %d %d",&c[i],&v[i],&j);
            if(i == j) edge[i].to=i,edge[i].next=head[0],head[0]=i;
            else edge[i].to=i,edge[i].next=head[j],head[j]=i;
        }
        c[0]=v[0]=0;
        dfs(0,G);
        int ans=0;
        printf("%d\n",dp[0][G]);
    }
}

参考:http://blog.csdn.net/alone_l/article/details/20246795


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n