動態(tài)規(guī)劃測試

1、動態(tài)規(guī)劃測試打包（pack.pas ）【問題描述】你現(xiàn)在拿到了許多的禮物，你要把這些禮物放進(jìn)袋子里。你只有一個最多裝下v體積 物品的袋子，你不能全部放進(jìn)去。你也拿不動那么重的東西。你估計你能拿的最大重量為G。 現(xiàn)在你了解了每一個物品的完美值、重量和體積，你當(dāng)然想讓袋子中裝的物品的完美值總和 最大，你又得計劃一下了。【輸入格式】第一行：V和G表示最大重量和體積。第二行：N表示拿到N件禮物。第三到N+2行：每行3個數(shù)T. V. G.表示各禮物的完美值、重量和體積【輸出格式】1 1 1輸出共一個數(shù)，表示可能獲得的最大完美值?！据斎胼敵鰳永俊緮?shù)據(jù)范圍】對于 20%的數(shù)據(jù) N，V，G，T.，V.，G.

2、W10對于 50%的數(shù)據(jù) N，V，G，T.，V.，G.W100對于 80%的數(shù)據(jù) N，V，G，T.，V.，G.W30080%到100%的數(shù)據(jù)是N，V，G，T.，V.，G.W380的離散隨機(jī)數(shù)據(jù)。2口，心：52乂（2口頊.,心.+七.,2口，蚓）機(jī)器人搬重物（ROBOT.PAS）【問題描敘】機(jī)器人移動學(xué)會（RMI）現(xiàn)在正嘗試用機(jī)器人搬運物品。機(jī)器人的形狀是一個直徑1.6 米的球。在試驗階段，機(jī)器人被用于在一個儲藏室中搬運貨物。儲藏室是一個N*M的網(wǎng)格， 有些格子為不可移動的障礙。機(jī)器人的中心總是在格點上，當(dāng)然，機(jī)器人必須在最短的時間 內(nèi)把物品搬運到指定的地方。機(jī)器人接受的指令有：先前移動1步（C

3、reep）；向前移動2 步（Walk）；向前移動3步（Run）；向左轉(zhuǎn)（Left）；向右轉(zhuǎn)（Right）。每個指令所需要的時 間為1秒。請你計算一下機(jī)器人完成任務(wù)所需的最少時間?！据斎敫袷健枯斎氲牡谝恍袨閮蓚€正整數(shù)N,M （N,M=50），下面N行是儲藏室的構(gòu)造，0表示無障礙，1表示有障礙，數(shù)字之間用一個空格隔開。接著一行有四個整數(shù)和一個大寫字母，分別為起始點和目標(biāo)點左上角網(wǎng)格的行與列，起始時的面對方向(東E,南S,西W,北N),數(shù)與數(shù)， 數(shù)與字母之間均用一個空格隔開。終點的面向方向是任意的?！据敵龈袷健恳粋€整數(shù)，表示機(jī)器人完成任務(wù)所需的最少時間。如果無法到達(dá)，輸出-1?！据斎霕永縍OBOT

4、.IN91000 0 0 0 0 1 0 0 000 0 0 0 0 0 0 1 000 0 1 0 0 0 0 0 000 1 0 0 0 0 0 0 000 0 0 0 0 1 0 0 000 0 0 0 1 0 0 0 000 0 1 1 0 0 0 0 000 0 0 0 0 0 0 0 010 0 0 0 0 0 0 1 072 2 7 S【輸出樣例】ROBOT.OUT12尼克的任務(wù)(LIGNJA.pas)【問題描述】尼克每天上班之前都連接上英特網(wǎng)，接受他的上司發(fā)來的郵件，這些郵件包含了尼克主管 的部門當(dāng)天要完成的全部任務(wù)，每個任務(wù)由一個開始時刻與一個持續(xù)時間構(gòu)成。尼克的一個工作日為

5、N分鐘，從第一分鐘開始到第N分鐘結(jié)束。當(dāng)尼克到達(dá)單位后他就 開始干活。如果在同一時刻有多個任務(wù)需要完成，尼克可以任選其中的一個來做，而其余的 則由他的同事完成，反之如果只有一個任務(wù)，則該任務(wù)必須由尼克去完成，假如某些任務(wù)開 始時刻尼克正在工作，則這些任務(wù)也由尼克的同事完成。如果某任務(wù)于第P分鐘開始，持 續(xù)時間為T分鐘，則該任務(wù)完成需要P+T-1分鐘?！据斎敫袷健枯斎霐?shù)據(jù)第一行為整數(shù)N和K，范圍都是1到1萬。N表示尼克的工作時間單位為分鐘， K表示任務(wù)總數(shù)。接下來共有K行，每一行有兩個用空格隔開的整數(shù)P和T，表示該任務(wù)從第P分鐘開始， 持續(xù)時間為T分鐘，其中1=P=N，1=P+T-1=N?！据敵龈?/p>