1、背包問(wèn)題思路問(wèn)題描述在M件物品取出若干件放在空間為W的背包里，每件物品的重量為W1, W2Wn,與之相對(duì)應(yīng)的價(jià)值為Pl,P2Pno求出獲得最大價(jià)值的方案。注意：在本題中，所有的重量值均為整數(shù)?？梢钥闯鋈绻ㄟ^(guò)第N次選擇得到的是一個(gè)最優(yōu)解的話，那么第N1次選 擇的結(jié)果一定也是一個(gè)最優(yōu)解。這符合動(dòng)態(tài)規(guī)劃中最優(yōu)子問(wèn)題的性質(zhì)?？紤]用動(dòng)態(tài)規(guī)劃的方法來(lái)解決，這里的：階段是：在前N件物品中，選取若干件物品放入背包中；狀態(tài)是：在前N件物品中，選取若干件物品放入所?？臻g為W的背包中的 所能獲得的最大價(jià)值；決策是：第N件物品放或者不放；由此可以寫出動(dòng)態(tài)轉(zhuǎn)移方程：我們用fi,j表示在前i件物品中選擇若干件放在所剩空

2、間為j的背包里所能 獲得的最大價(jià)值 fi,j=maxfi-lj-Wi+Pi (j>=Wi), fi-lj這樣，我們可以自底向上地得出在前M件物品中取出若干件放進(jìn)背包能獲 得的最大價(jià)值，也就是fm,w算法設(shè)計(jì)如下：for(i=l;i<=m;i+) /*m 是物品的個(gè)數(shù)*/for(j=0;j<=n;j+) /*n 是背包容量*/x=fi-lj-vi+pi;if(x>fij)fiD=x;采藥(medic.pas/c/cpp)【問(wèn)題描述】辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此， 他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難 題。醫(yī)師

3、把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說(shuō)：“孩子，這個(gè)山洞里有一 些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給 你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩 子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大。”如果你是辰辰，你能完成這個(gè)任務(wù)嗎？【輸入文件】輸入文件medic.in的第一行有兩個(gè)整數(shù)T (1<=T<= 1000)和M (1<=M<= 100),用一個(gè)空格隔開(kāi)，T代表總共能夠用來(lái)采藥的時(shí)間，M代表山洞里的草 藥的數(shù)目。接下來(lái)的M行每行包括兩個(gè)在1到100之間(包括1和100)的整 數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)

4、值?！据敵鑫募枯敵鑫募edic.out包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間 內(nèi)，可以采到的草藥的最大總價(jià)值?！緲永斎搿?0 3A1003int f100 100=07110069 112Fi0=0;f0U=0【樣例輸出】31、首先初始化f數(shù)組，全變成02、當(dāng) j>=物品重量時(shí),fij=maxfi-lULfi-lU-ail+ai2Ail是物品的重量，ai2是物品的價(jià)值3、當(dāng) j<ailfiU=fi-lU【數(shù)據(jù)規(guī)?！繉?duì)于30%的數(shù)據(jù)，Mv=10；對(duì)于全部的數(shù)據(jù)，M<= 100o動(dòng)態(tài)規(guī)劃：記f(t, m)是如果只采前m株草藥，在時(shí)間t里能夠得到的最大 價(jià)值。可以得

5、到f(t, m) = maxf(t, m-1), f(t-采第m株草藥需要的時(shí)間,m-1) +第m株草藥的 價(jià)值時(shí)間復(fù)雜度O(T*M)。#inc-udesfdio.hvinf maino(FFE-SEfoat f【101 一【loolJrobp【lolli(oh intLm、w(101nsm fpHfopen=twl.irr=r=j fscanf(fp、=%>dfd=、8lt、8lm)j for7l7-HmT+) fscanf(fp、=%>d%>feow=L0p【ej fcose(fp)jfpHfopen=twlout<wv for7rl=AHmT+) for(li-l

6、;A-3j+) f三URfvl三ifuvHWsapu+fvlwmvfns) sullpn+vlsw 亙 fprintf(fp=決ofjf【m=twfclose(fp);return 0;2 開(kāi)心的金明（happy.pas/c/cpp）【問(wèn)題描述】金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專 用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說(shuō)：你的房間需要購(gòu)買哪 些物品，怎么布置，你說(shuō)了算，只要不超過(guò)N元錢就行。今天一早金明就開(kāi)始 做預(yù)算，但是他想買的東西太多了，肯定會(huì)超過(guò)媽媽限定的N元。于是，他把 每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù)L5表示，第5等最重要。他 還從因特

7、網(wǎng)上查到了每件物品的價(jià)格（都是整數(shù)元）。他希望在不超過(guò)N元 （可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。設(shè)第j件物品的價(jià)格為vj,重要度為wj,共選中了 k件物品，編號(hào)依次 為jk,則所求的總和為:vjl*wj1 +vj2 *wj2+vjk*wjko (其中*為乘號(hào))請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單?！据斎胛募枯斎胛募appy.in的第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：N m(其中N (<30000)表示總錢數(shù)，m (<25)為希望購(gòu)買物品的個(gè)數(shù)。)從第2行到第m+1行，第j行給出了編號(hào)為卜1的物品的基本數(shù)據(jù)，每行有2個(gè)非負(fù)整數(shù)v P(其中v表示該

8、物品的價(jià)格(v<=10000), p表示該物品的重要度(15)【輸出文件】輸出文件happy.out只有一個(gè)正整數(shù)，為不超過(guò)總錢數(shù)的物品的價(jià)格與重要度乘積的總和的最大值(<100000000) o【輸入樣例】1000 5800 2400 5300 5400 3200 23900專4±inc-udestdio.hvfoat f-26=3ooolvoh int maino(FFE-JP;foat p【26vo)j intt、m、w【26vs、LjjfpHfopen=tw2i3<h fscanf(fp=fdfd=、8d>0m)j for7lxHmT+) fscanf

9、(fp、連 d 卑veow 三eop 三)-fcose(fp)j fpHfopen=tw2out<ww for7lxHmT+) for(li-l-A-Htj+)(f 三 uufvl 三axwEi協(xié)(purwu+fvlw巨vf=s)fiU=pi*wi+fi-lU-wi；fprintf(fp/%0化 fmt);fclose(fp);return 0;合唱隊(duì)形解題報(bào)告v問(wèn)題描述N位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的(NK)位同學(xué)出列，使得剩下的K 位同學(xué)排成合唱隊(duì)形。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1, 2., K,他們的身高分別為Tl, T2, TK,則他們的身高滿足T

10、K.<Ti>Ti+l>.>TK(l<=i<=K)o你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可 以使得剩下的同學(xué)排成合唱隊(duì)形。輸入文件輸入文件chorus.in的第一行是一個(gè)整數(shù)N(2v二Nv=100),表示同學(xué)的總數(shù)。 第一行有n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)Ti(130<=Ti<=230)是第i位同學(xué)的 身高(厘米)。輸出文件輸出文件chorus.out包括一行，這一行只包含一個(gè)整數(shù)，就是最少需要幾 位同學(xué)出列。樣例輸入186 186 150 200 160 130 197 220Al al樣例輸出4數(shù)據(jù)規(guī)模對(duì)于50%的數(shù)

11、據(jù)，保證有n<=20；對(duì)于全部的數(shù)據(jù)，保證有n<=100ov算法分析動(dòng)態(tài)規(guī)劃。最基本的想法是：枚舉中間最高的一個(gè)人，接著對(duì)它的左邊求 最長(zhǎng)上升序列（注意序列中最高的同學(xué)不應(yīng)高過(guò)基準(zhǔn)），對(duì)右邊求最長(zhǎng)下降序 列（同樣的，序列中最高的同學(xué)不應(yīng)高過(guò)基準(zhǔn)）。時(shí)間復(fù)雜度為0（23）,算法 實(shí)現(xiàn)起來(lái)也很簡(jiǎn)單。接著對(duì)這個(gè)算法進(jìn)行分析，我們不難發(fā)現(xiàn)，假如還是基于枚舉一個(gè)同學(xué)的 話，設(shè)bi表示了 li的最長(zhǎng)上升序列，ci表示了 in的最長(zhǎng)下降序列，那 么，di = bi +ci-l （兩個(gè)數(shù)組中i被重復(fù)計(jì)算了）那么，我們只需要先求好最長(zhǎng)上升和下降序列，然后枚舉中間最高的同學(xué) 就可以了。v算法優(yōu)化（在寫

12、狀態(tài)轉(zhuǎn)移方程時(shí)要滿足無(wú)后效性）求最長(zhǎng)遞增序列的經(jīng)典狀態(tài)轉(zhuǎn)移方程為：最初時(shí):bi=l;狀態(tài)轉(zhuǎn)移方程為bi = maxbi,bj+l,其中jviv二n,且listj<listi寫出最長(zhǎng)遞減序列的經(jīng)典狀 態(tài)轉(zhuǎn)移方程為：ci = maxci,cj+l,其中 l<=i<j<=n,且 listj<listik=sum=max（bl+cl）-l3.Jam 的計(jì)數(shù)法（count.pas/c/cpp）*題目部分【問(wèn)題描述】Jam是個(gè)喜歡標(biāo)新立異的科學(xué)怪人。他不使用阿拉伯?dāng)?shù)字計(jì)數(shù)，而是使用 小寫英文字母計(jì)數(shù)，他覺(jué)得這樣做，會(huì)使世界更加豐富多彩。在他的計(jì)數(shù)法 中，每個(gè)數(shù)字的位數(shù)都是相同

13、的（使用相同個(gè)數(shù)的字母），英文字母按原先的 順序，排在前面的字母小于排在它后面的字母。我們把這樣的"數(shù)字稱為Jam 數(shù)字。在Jam數(shù)字中，每個(gè)字母互不相同，而且從左到右是嚴(yán)格遞增的。每 次，Jam還指定使用字母的范圍，例如，從2到10,表示只能使用 b,c,d,e,f,g,h,ij這些字母。如果再規(guī)定位數(shù)為5,那么，緊接在Jam數(shù)字“bdfij 之后的數(shù)字應(yīng)該是"bdghi。（如果我們用U、V依次表示Jam數(shù)字“bdfij與 "bdghi，則UvV,且不存在Jam數(shù)字P,使UvPvV）。你的任務(wù)是：對(duì)于從文 件讀入的一個(gè)Jam數(shù)字，按順序輸出緊接在后面的5個(gè)Jam數(shù)字，如果后面沒(méi) 有那么多Jam數(shù)字，那么有幾個(gè)就輸出幾個(gè)。【輸入文件】輸入文件counting.in有2行，第1行為3個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：S t W（其中S為所使用的最小的字母的序號(hào)，t為所使用的最大的字母的序號(hào)。 w為數(shù)字的位數(shù)，這3個(gè)數(shù)滿足：l<s<t<26, 2<w<t-s