亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        貪吃的九頭龍問題

        2019-10-21 19:31:20王偉業(yè)路宇李曉寒
        青年生活 2019年14期
        關(guān)鍵詞:樹結(jié)構(gòu)樹形大頭

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

        摘要:貪吃的九頭蛇是樹形動(dòng)態(tài)規(guī)劃的經(jīng)典問題,是基于樹結(jié)構(gòu)的動(dòng)態(tài)規(guī)劃問題。

        關(guān)鍵詞:樹形 動(dòng)態(tài)規(guī)劃

        一、問題描述

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

        二、例題求解

        例:果樹包含 8 個(gè)果子,7 段樹枝,各段樹枝的“難受值”標(biāo)記在了樹枝的旁邊。九頭龍有三個(gè)腦袋,大頭需要吃掉 6 個(gè)果子,其中必須包含最大的果子。

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

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

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

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

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

        設(shè)DP[u][sum][0]表示u結(jié)點(diǎn),它以及它的兒子中,大頭吃了sum個(gè)果子,并且當(dāng)前這個(gè)沒有被大頭吃。

        那么DP[u][sum][1]就是表示u結(jié)點(diǎn),它以及它的兒子中,大頭吃了sum個(gè)果子,并且當(dāng)前這個(gè)被大頭吃了。

        可得遞推關(guān)系式:

        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;

        問題歸結(jié)于求解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

        最終目標(biāo):

        DP[1][6][1]=min{55,42,13,24, 37}=13(分別對(duì)應(yīng)3 1 1;3 0 2;2 1 2;2 0 3;1 1 3)

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

        三、小結(jié)

        貪吃的九頭龍問題是典型的樹形動(dòng)態(tài)規(guī)劃問題,在樹結(jié)構(gòu)上進(jìn)行動(dòng)態(tài)規(guī)劃,求解時(shí)關(guān)鍵是找出遞推關(guān)系,逐步計(jì)算,最終即可得到答案。

        猜你喜歡
        樹結(jié)構(gòu)樹形大頭
        花光卉影
        花卉(2024年1期)2024-01-16 11:29:12
        蘋果高光效樹形改造綜合配套技術(shù)
        河北果樹(2022年1期)2022-02-16 00:41:10
        獼猴桃樹形培養(yǎng)和修剪技術(shù)
        休眠季榆葉梅自然開心樹形的整形修剪
        四維余代數(shù)的分類
        大頭蔥(5)
        大頭蔥(3)
        大頭蔥(4)
        大頭蔥(1)
        大數(shù)據(jù)背景下基于B—樹結(jié)構(gòu)的SQL Server數(shù)據(jù)優(yōu)化策略研究
        亚洲国产av综合一区| 日韩高清毛片| 亚洲AV无码成人精品区日韩密殿| 自拍情爱视频在线观看| 亚洲精品无码不卡| 欧美肥胖老妇做爰videos| 老色鬼永久精品网站| 国产在线观看免费不卡视频| 久久精品国产亚洲av超清| 女人高潮被爽到呻吟在线观看| 国产三级欧美| 熟女乱乱熟女乱乱亚洲| 国产自拍视频在线观看网站| 野狼第一精品社区| 国产福利片无码区在线观看| 中文字幕日韩精品亚洲精品| 日本添下边视频全过程| 18成人片黄网站www| 免费一级国产大片| 爱爱免费视频一区二区三区| 成年站免费网站看v片在线| 精品亚洲aⅴ在线观看| 日本一区二区在线资源 | 亚洲精品成人无百码中文毛片| 麻豆精品国产精华精华液好用吗| 日韩高清毛片| 日本熟女视频一区二区三区| 黑人大群体交免费视频| 无码国产一区二区三区四区| 日本一道dvd在线中文字幕| 日本一区二区三区经典视频| 日本艳妓bbw高潮一19| 国产第一草草影院| 国产精品亚洲一区二区三区妖精| 精品无码av无码专区| 1区2区3区高清视频| 欧美综合区自拍亚洲综合| 国产精品一区二区熟女不卡| 中文字幕人妻中文| 午夜亚洲国产理论片亚洲2020| 亚洲中文字幕免费精品|