hdu【1561】The more, The Better

The more, The Better
Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6922    Accepted Submission(s): 4059
Problem Description
ACboyは戦略ゲームが大好きで、1つの地図の上で、Nつの城があって、すべての城はすべて一定の宝物があって、毎回ゲームの中でACboyはMつの城を攻略して中の宝物を得ることを許可します.しかし、地理的な理由で、直接攻略できない城もあります.これらの城を攻略するには、まず他の特定の城を攻略しなければなりません.できるだけ多くの宝物を手に入れるにはどのM城を攻略すべきか、ACboyに計算してもらえますか?
 
Input
各試験例は、まず、2つの整数、N、M.(1<=M<=N<=200)を含む.次のN行では、各行に2つの整数が含まれ、a,b.i行目では、aはi番目の城を攻略するにはまずa番目の城を攻略しなければならないことを表し、a=0であればi番目の城を直接攻略することができることを表す.bはi番目の城の宝物の数を表し、b>=0である.N=0でM=0入力が終了します.
 
Output
各試験例について、ACboyがM個の城を攻略して得た最も多くの宝物の数を表す整数を出力する.
 
Sample Input

   
   
   
   

    
    
    
    3 2
0 1
0 2
0 3
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
0 0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    5
13
   
   
   
   

 
Author
8600

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 205;
int n,m;

struct Edge //    
{
    int to,next;
}edge[maxn];
int pre[maxn];
int value[maxn];
int dp[maxn][maxn];

void dfs(int u)
{
    dp[u][1] = value[u];
    for(int i = pre[u] ; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        dfs(v);
        for(int k = m; k >= 1; k--)             
            for(int j = 1; j < k; j++)
                dp[u][k] = max(dp[u][k],dp[u][k-j]+dp[v][j]);
    }
}

int main()
{
    while(scanf("%d%d",&n,&m) != EOF)
    {
        if(!n&&!m) break;
        memset(dp,0,sizeof(dp));
        memset(pre,-1,sizeof(pre));
        int a,b,tot = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d%d",&a,&b);
            edge[tot].to = i;
            edge[tot].next = pre[a];
            pre[a] = tot++;
            value[i] = b;
        }
        ++m;
        value[0] = 0;
        dfs(0);
        printf("%d
",dp[0][m]);
    }
    return 0;
}

P 06:グループのリュックの問題
に質問
N個の品物とV容量のリュックサックがあります.i番目の品物の費用はc[i]、価値はw[i]です.これらのアイテムはいくつかのグループに分けられ、各グループのアイテムは互いに衝突し、最大1つを選択します.リュックサックにどのアイテムを入れるかを解くと、これらのアイテムの費用の合計がリュックサックの容量を超えず、価値の合計が最大になります.
アルゴリズム#アルゴリズム#
この問題は、各グループのアイテムにはいくつかの戦略があります.このグループのいずれかを選択するか、それとも1つも選択しないかです.すなわち、f[k][v]が前k組の物品費費用vが取得できる最大の権利値を示すとすると、f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]| i k}
1 D配列を使用する疑似コードは次のとおりです.

for     k

    for v=V..0

        for    i   k

            f[v]=max{f[v],f[v-c[i]]+w[i]}

ここの3層ループの順序に注意して、本文の最初のbeta版の中で私自身も書き間違えました.「for v=V..0」というレイヤループは、「forのすべてのiがグループkに属する」以外でなければならない.これにより、各グループ内のアイテムがリュックサックに追加されるのは最大1つだけであることが保証されます.
この問題はリュックサックをグループ化していると言われていますが、私はどうしてそんな感じがしませんか.後ろから絶えず発売される前に最大値を求めているような気がします.この問題の面白いところはルートノードを増やして、すべての点がつながって、木になりました.