pascal-采藥-金明的預(yù)算方案詳解

動態(tài)規(guī)劃相關(guān)算法及資料背包九講二．動歸經(jīng)典例題詳解（標(biāo)色說明：0題目0類型0重要條件0解析）例題1.noip2005普及組采藥（01背包）描述Description辰辰是個天資聰穎的孩子，他的幻想是成為世界上最宏大的醫(yī)師。為此，他想拜旁邊最有威望的醫(yī)師為師。醫(yī)師為了推斷他的資質(zhì)，給他出了一個難題。醫(yī)師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都須要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。假如你是一個聰慧的孩子，你應(yīng)當(dāng)可以讓采到的草藥的總價值最大?！奔偃缒闶浅匠剑隳芡瓿蛇@個任務(wù)嗎？輸入格式InputFormat輸入的第一行有兩個整數(shù)T（1<=T<=1000）和M（1<=M<=100），用一個空格隔開，T代表總共能夠用來采藥的時間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時間和這株草藥的價值。輸出格式OutputFormat輸出包括一行，這一行只包含一個整數(shù)，表示在規(guī)定的時間內(nèi)，可以采到的草藥的最大總價值。樣例輸入SampleInput7037110069112樣例輸出SampleOutput3Analysis：這是一道很裸的01背包入門題，用f[j]表示花費(fèi)時間j所能得到的最大價值，s[i]表示第i個物品所花費(fèi)的時間，w[i]表示第i個物品的價值，狀態(tài)轉(zhuǎn)移方程為：f[j]=max{f[j-1],f[j-s[i]]+w[i]}Fori:=1tomdoForj:=tdowntos[i]doF[j]:=ma(f[j-1],f[j-s[i]]+w[i]);最終，干脆輸出f[t]即可。varf:array[0..1000+10]oflongint;{典型的01背包；f[i]表示時刻i所能得到的最大價值,枚舉時必需從大往小。}procedureinit;beginassign(input,'noip2005.in');assign(output,'noip2005.out');reset(input);rewrite(output);end;procedureterminate;beginclose(input);close(output);halt;end;functionmax(a,b,c:longint):longint;beginif(a>b)and(a>c)thenexit(c);if(b>a)and(b>c)thenexit(b);exit(c);end;proceduremain;vari,j,si,zi,t,m:longint;beginfillchar(f,sizeof(i),0);read(t,m);fori:=1tomdobeginread(si,zi);forj:=tdowntosidof[j]:=max(f[j],f[j-si]+zi,f[j-1]);end;writeln(f[t]);end;begininit;main;terminate;end.例題2noip2006提高組金明的預(yù)算方案（有依靠的背包or分組背包）描述Description金明今日很快樂，家里購置的新居就要領(lǐng)鑰匙了，新居里有一間金明自己專用的很寬敞的房間。更讓他興奮的是，媽媽昨天對他說：“你的房間須要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今日一早，金明就起先做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子：主件附件電腦打印機(jī)，掃描儀書柜圖書書桌臺燈，文具工作椅無假如要買歸類為附件的物品，必需先買該附件所屬的主件。每個主件可以有0個、1個或2個附件。附件不再有從屬于自己的附件。金明想買的東西許多，確定會超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)1~5表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是10元的整數(shù)倍）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設(shè)第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1，j2，……，jk，則所求的總和為：v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。（其中*為乘號）請你幫助金明設(shè)計一個滿意要求的購物單。輸入格式InputFormat輸入文件的第1行，為兩個正整數(shù)，用一個空格隔開：Nm其中N（<32000）表示總錢數(shù)，m（<60）為希望購買物品的個數(shù)。）從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數(shù)據(jù)，每行有3個非負(fù)整數(shù)vpq（其中v表示該物品的價格（v<10000），p表示該物品的重要度（1~5），q表示該物品是主件還是附件。假如q=0，表示該物品為主件，假如q>0，表示該物品為附件，q是所屬主件的編號）輸出格式OutputFormat輸出文件只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（<200000）。樣例輸入SampleInput100058002040051300514003050020樣例輸出SampleOutput2200時間限制TimeLimitation1sAnasisi：這道題是一道典型的有依靠的背包問題，把一個主件看作是一個物品組，主件所屬的附件為物品組中的物品，當(dāng)枚舉到每一組時，就有這樣三種選擇：①：這個物品組中一個物品都不要，即f[j]=max{f[j-1],f[j]}.②:只要一個主件，不要附件，即f[j]=max{f[j],f[j-v[k]]+w[k]}.(k為主件號)③要附件，即f[j]=max{f[j-v[b]]+w[b],f[j-v[b]-v[k]]+w[k]+w[b]},(b主件k的一個附件，f[j-v[b]]+w[b]代表從一個已經(jīng)買了主件的f值，再買附件b,得到f[j]的值；f[j-v[k]-v[b]]+v[k]+v[b],表示從一個未用未買主件k的f值，買主件k及附件b，得到f[j]的值。我們再為f[j]附加一個屬性，用一個flag[0..60+10,0..3200+10]的數(shù)組，記錄當(dāng)價值為j時，是否買了主件k)主題代碼：for全部的組kfor全部的i屬于組kbegin//處理是否要主件forj:=ndowntov[k]doiff[j]<f[j-v[k]]+w[k]thenbeginf[j]:=f[j-v[k]]+w[k];flag[k,j]:=true;end;//處理附件iff[j]<f[j-1]thenf[j]:=f[j-1];{這一句放在前面，可以避開出錯。假如三種狀況得到的f值相等，就要選這一種}F[j]:=max{f[j],f[j-v[b]]+w[b],f[j-v[b]-v[k]]+w[k]+w[b]};end;最終輸出f[n]即可。varn,m:longint;v,w:array[0..60+10]oflongint;//記錄每個物品的價格，價值c:array[0..60+10,0..60+10]oflongint;//用偽鏈表記錄每個主件的附件，c[i,0]=-1代表這是附件，c[i,0]>=0,代表這是主件f:array[0..3200+10]oflongint;//花費(fèi)j元，可以得到的最大價值flag:array[0..60+10,0..3200+10]ofboolean;//花費(fèi)j元得到最大價值，是否買了主件kprocedureinit;beginassign(input,'budget.in');assign(output,'budget.out');reset(input);rewrite(output);end;procedureterminate;beginclose(input);close(output);halt;end;procedurereaddata;vari,q:longint;beginread(n,m);n:=ndiv10;//全部的錢都整除10fillchar(c,sizeof(c),0);fori:=1tomdobeginread(v[i],w[i],q);w[i]:=v[i]*w[i];v[i]:=v[i]div10;ifq<>0thenbegininc(c[q,0]);c[q,c[q,0]]:=i;c[i,0]:=-1;end;end;end;proceduremain;vari,j,k:longint;beginfillchar(f,sizeof(f),0);fillchar(flag,sizeof(flag),0);fork:=1tomdoifc[k,0]>=0thenbegin//處理只要主件的狀況forj:=ndowntov[k]doiff[j]<f[j-v[k]]+w[k]thenbeginf[j]:=f[j-v[k]]+w[k];flag[k,j]:=true;end;//處理買入附件的狀況fori:=1toc[k,0]doforj:=ndowntov[c[k,i]]+v[k]dobeginiff[j]<f[j-1]thenf[j]:=f[j-1];{這一句放在前面，可以避開出錯。假如這三種狀況得到的f值相等，就要選第一種}if(notflag[k,j-v[k]-v[c[k,i]]])and(f[j]<f[j-v[k]-v[c[k,i]]]+w[k]+w[c[k,i]])thenbeginf[j]:=f[j-v[k]-v[c[k,i]]]+w[k]+w[c[k,i]];flag[k,j]:=true;end;if(flag[k,j-v[c[k,i