貪吃的九頭龍問題

王偉業(yè) 路宇 李曉寒

摘要：貪吃的九頭蛇是樹形動態(tài)規(guī)劃的經典問題，是基于樹結構的動態(tài)規(guī)劃問題。

關鍵詞：樹形 動態(tài)規(guī)劃

一、問題描述

傳說中的九頭龍是一種特別貪吃的動物。雖然名字叫“九頭龍”，但這只是說它出生的時候有九個頭，而在成長的過程中，它有時會長出很多的新頭，也會有舊頭因衰老而自己脫落。 有一天，有 M（M≥3） 個腦袋的九頭龍看到一棵長有 N 個果子的果樹，喜出望外，恨不得一口把它全部吃掉。 可是必須照顧到每個頭，因此它需要把 N 個果子分成 M 組，每組至少有一個果子，讓每個頭吃一組。 這 M 個腦袋中有一個最大，稱為“大頭”，是眾頭之首，它要吃掉恰好 K 個果子，而且 K 個果子中理所當然地應該包括唯一的一個最大的果子。 果子由 N-1 根樹枝連接起來，由于果樹是一個整體，因此可以從任意一個果子出發(fā)沿著樹枝“走到”任何一個其他的果子。對于每段樹枝，如果它所連接的兩個果子需要由不同的頭來吃掉，那么兩個頭會共同把樹枝弄斷而把果子分開;如果這兩個果子是由同一個頭來吃掉，那么這個頭會懶得把它弄斷而直接把果子連同樹枝一起吃掉。當然，吃樹枝并不是很舒服的，因此每段樹枝都有一個吃下去的“難受值”，而九頭龍的難受值就是所有頭吃掉的樹枝的“難受值”之和。九頭龍希望它的“難受值”盡量小，你能幫它算算嗎？

二、例題求解

例：果樹包含 8 個果子，7 段樹枝，各段樹枝的“難受值”標記在了樹枝的旁邊。九頭龍有三個腦袋，大頭需要吃掉 6 個果子，其中必須包含最大的果子。

即 N=8 ?，M=3 ，K=6。

首先，判斷問題是否有解。判斷是否有解是十分簡單的。我們只需要看在給每個小頭分配1個，大頭分配K個的情況下，所需要的果子的數量是否大于了果子的總數，即若M+K-1>N，則無解，此題M+K-1=8=N，故有解。

接下來就是有解的情況了。

首先我們需要知道，再分配好大頭之后，剩下的果子必然存在一種分配方式，使得九頭龍的難受值不會再增加?？紤]樹的結構，每一條線都連接相鄰兩層的果子，故只需由第一層到最后一層讓小頭依次吃，如果層數多于小頭數量，則循環(huán)進行。

解決了這個問題之后，我們就只需要考慮大頭了。對于每一個果子來說，它要么是被大頭吃，要么是不被。于是，我們便可以用樹形DP來解決。

設DP[u][sum][0]表示u結點，它以及它的兒子中，大頭吃了sum個果子，并且當前這個沒有被大頭吃。

那么DP[u][sum][1]就是表示u結點，它以及它的兒子中，大頭吃了sum個果子，并且當前這個被大頭吃了。

可得遞推關系式：

DP[u][sum][0]=min{sigma{min（DP[v][j][0]，DP[v][j][1]）}} sigma{j}=sum;

DP[u][sum][1]=min{sigma{min（DP[v][j][0]，DP[v][j][1]+len）}} sigma{j}=sum-1;

DP[u][1][1]=DP[u][0][0]=0;

問題歸結于求解DP[1][K][1]

DP[8][0][0]=0 ? ? DP[8][1][1]=0 ? ? DP[7][0][0]=0 ? ? DP[7][1][1]=0

DP[6][0][0]=0 ? ? DP[6][1][1]=0 ? ? DP[5][0][0]=0 ? ? DP[5][1][1]=0

DP[4][0][0]=0 ? ? DP[4][1][0]=0 ? ? DP[4][2][0]=0 ? ? DP[4][1][1]=0

DP[4][2][1]=5 ? ? DP[4][3][1]=20 ? ?DP[3][0][0]=0 ? ? DP[3][1][1]=0

DP[2][0][0]=0 ? ? DP[2][1][1]=1 ? ? DP[2][2][0]=0 ? ? DP[2][2][1]=10

DP[2][1][0]=0 ? ? DP[2][3][1]=22

最終目標：

DP[1][6][1]=min{55，42，13，24， 37}=13（分別對應3 1 1;3 0 2;2 1 2;2 0 3;1 1 3）

即取2 1 2，大頭吃1 3 5 6 7 8，得解。

三、小結

貪吃的九頭龍問題是典型的樹形動態(tài)規(guī)劃問題，在樹結構上進行動態(tài)規(guī)劃，求解時關鍵是找出遞推關系，逐步計算，最終即可得到答案。