[計(jì)算機(jī)]動態(tài)規(guī)劃的模型構(gòu)建-資料下載頁
2024-10-16 23:00本頁面
【正文】 ? 1=i=k==j=n ? 時間復(fù)雜度 O(n3) ? 要構(gòu)造這個樹，只需記錄每次的決策值，令 b(i,j)=k，表示中序遍歷為 i,i+1,…,j的二叉樹的取最優(yōu)決策時的根結(jié)點(diǎn)為 k ? 最后前序遍歷這個樹即可。 思考題：選課 ? 大學(xué)里實(shí)行學(xué)分 。 每門課程都有一定的學(xué)分 ， 學(xué)生只要選修了這門課并考核通過就能獲得相應(yīng)的學(xué)分 。 學(xué)生最后的學(xué)分是他選修的各門課的學(xué)分的總和 。 ? 每個學(xué)生都要選擇規(guī)定數(shù)量的課程。其中有些課程可以直接選修，有些課程需要一定的基礎(chǔ)知識，必須在選了其它的一些課程的基礎(chǔ)上才能選修。例如， 《 數(shù)據(jù)結(jié)構(gòu) 》 必須在選修了 《 高級語言程序設(shè)計(jì) 》 之后才能選修。我們稱 《高級語言程序設(shè)計(jì) 》 是 《 數(shù)據(jù)結(jié)構(gòu) 》 的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。為便于表述每門課都有一個課號，課號依次為 1， 2， 3， …… 。 ? 每個學(xué)生可選課程的總數(shù)是給定的?，F(xiàn)在請你找出一種選課方案，使得你能得到學(xué)分最多，并且必須滿足先修課優(yōu)先的原則。假定課程之間不存在時間上的沖突。 ? 輸入 輸入文件的第一行包括兩個正整數(shù) M、 N（ 中間用一個空格隔開 ） 其中 M表示待選課程總數(shù) （ 1≤M≤ 1000)， N表示學(xué)生可以選的課程總數(shù) （ 1≤N≤M) 。 以下 M行每行代表一門課 ， 課號依次為 1， 2?? M。 每行有兩個數(shù) （ 用一個空格隔開 ） ， 第一個數(shù)為這門課的先修課的課號 （ 若不存在先修課則該項(xiàng)為 0） ， 第二個數(shù)為這門課的學(xué)分 。 學(xué)分是不超過 10的正整數(shù) 。 ? 輸出 輸出文件第一行只有一個數(shù) ， 即實(shí)際所選課程的學(xué)分總數(shù) 。 以下 N行每行有一個數(shù) ， 表示學(xué)生所選課程的課號 。 問題 7：聚會的快樂 ? 你要組織一個由你公司的人參加的聚會。你希望聚會非常愉快，盡可能多地找些有趣的熱鬧。但是勸你不要同時邀請某個人和他的上司，因?yàn)檫@可能帶來爭吵。給定 N個人(姓名，他幽默的系數(shù)，以及他上司的名字 )，編程找到能使幽默系數(shù)和最大的若干個人。 【 輸入 】 第一行一個整數(shù) N(N100)。接下來有 N行，每一行描述一個人的信息，信息之間用空格隔開。姓名是長度不超過 20的字符串，幽默系數(shù)是在 0到 100之間的整數(shù)。 【 輸出 】 所邀請的人最大的幽默系數(shù)和。 樣例 【 樣例 】 5 8 BART 1 HOMER HOMER 2 MONTGOMERY MONTGOMERY 1 NOBODY LISA 3 HOMER SMITHERS 4 MONTGOMERY 分析 ? 首先，很顯然公司的人員關(guān)系構(gòu)成了一棵樹。設(shè) f[a]為 a參加會議的情況下，以他為根的子樹取得的最大幽默值； g[a]為 a不參加會議的情況下，以他為根的子樹取得的最大幽默值。那么，狀態(tài)轉(zhuǎn)移方程就是： f[a]=g[b1]+g[b2++…+g*bk]+1 g[a]=max(f[b1], g[b1])+max(f[b2], g[b2+)+…+max(f*bk], g[bk]) 其中 b1, b2, …, bk為 a的子結(jié)點(diǎn)。 ? 最后的答案就是 max(f[root], g[root])， root是樹 思考題：警衛(wèi)安排 ? 一個有 N個區(qū)域的樹結(jié)構(gòu)上需要安排若干個警衛(wèi)； ? 每個區(qū)域安排警衛(wèi)所需要的費(fèi)用是不同的； ? 每個區(qū)域的警衛(wèi)都可以望見其相鄰的區(qū)域，只要一個區(qū)域被一個警衛(wèi)望見或者是安排有警衛(wèi)，這個區(qū)域就是安全的； ? 任務(wù)：在確保所有區(qū)域都是安全的情況下，找到安排警衛(wèi)的最小費(fèi)用； ? 0n=720； 聯(lián)系方式 ? ? 長沙市雅禮中學(xué) 朱全民 410007
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1