北京大學(xué)解題報(bào)告與代碼(DP)

PKU解題報(bào)告與代碼動態(tài)規(guī)劃袁輝勇整理2009年11月27日目錄TOC\o"1-5"\h\z\o"CurrentDocument"ー、背包問題 3\o"CurrentDocument"PKU1874: TradeonVerweggistan 3\o"CurrentDocument"PKU1775: SumofFactorials 5\o"CurrentDocument"PKU1837: Balance 8PKU1014: Dividing 10\o"CurrentDocument"PKU3624: CharmBracelet 15\o"CurrentDocument"PKU2063: Investment 17\o"CurrentDocument"PKU1787: Charlie'sChange 19PKU2581: ExactChangeOnly 20\o"CurrentDocument"PKU2184: CowExhibition 22PKU1636: Prisonrearrangement 24\o"CurrentDocument"PKU1276: CashMachine 26PKU1745: Divisibility 34\o"CurrentDocument"PKU1742: Coins 35PKU3211: WashingClothes 37PKU2392: SpaceElevator 38PKU 2486:AppleTree 40\o"CurrentDocument"PKU1947: RebuildingRoads 43\o"CurrentDocument"PKU1155: TELE 44ハ經(jīng)叫題丨I 47\o"CurrentDocument"PKU2479: Maximumsum 47PKU2593: MaxSequence 48\o"CurrentDocument"PKU1015: JuryCompromise 49\o"CurrentDocument"PKU1050: TotheMax 52\o"CurrentDocument"PKU1080: HumanGeneFunctions 53\o"CurrentDocument"PKU1221: UNIMODALPALINDROMICDECOMPOSITIONS 56\o"CurrentDocument"PKU1260: Pearls 58\o"CurrentDocument"PKU2411: Mondriaan'sDream 60\o"CurrentDocument"PKU1159: Palindrome 62\o"CurrentDocument"PKU1157: LITTLESHOPOFFLOWERS 62PKU1692: CrossedMatchings 65PKU2042: Lagrange'sFour-Square'Theorem 68PKU1432: DecodingMorseSequences 69\o"CurrentDocument"三、普通DP 72\o"CurrentDocument"PKU1014: Dividing 72PKU1015: JuryCompromise 75PKU1036: Gangsters 78\o"CurrentDocument"PKU 1088:滑雪 84PKU 1112:TeamThemUp! 85\o"CurrentDocument"PKU1160 :PostOffice 88\o"CurrentDocument"PKU1170 :ShoppingOffers 90\o"CurrentDocument"PKU1179:Polygon 92\o"CurrentDocument"PKU1390:Blocks 94\o"CurrentDocument"PKU1485:FastFood 96\o"CurrentDocument"PKU1579:FunctionRunFun 98PKU1631:Bridgingsignals 100\o"CurrentDocument"PKU1732:Phonenumbers 104PKU1887:TestingtheCATCHER 106PKU1925:Spiderman 108PKU1946:CowCycling 110\o"CurrentDocument"PKU1949:Chores 112PKU1953:WorldCupNoise 113\o"CurrentDocument"PKU1976:AMiniLocomotive 114\o"CurrentDocument"PKU2033:Alphacode 116PKU2127:GreatestCommonIncreasingSubsequence 117\o"CurrentDocument"PKU2137:Cowties 118\o"CurrentDocument"PKU2192:Zipper 120PKU2228:Naptime 122\o"CurrentDocument"PKU2250:Compromise 123\o"CurrentDocument"PKU2264:AdvancedFruits 126PKU2342:Anniversaryparty 127PKU2378:TreeCutting 129\o"CurrentDocument"PKU2948:MartianMining 132\o"CurrentDocument"PKU3034:Whac-a-Mole 135\o"CurrentDocument"PKU3254:CornFields 139PKU3280:CheapestPalindrome 140\o"CurrentDocument"PKU3356:AGTC 142ー、背包問題PKU1874:TradeonVerweggistanDescription：SincethedaysofPeterStuyvesantandAbelTasman,Dutchmerchantshavebeentravelingallovertheworldtobuyandsellgoods.OncetherewassometradeonVerweggistan,butitendedafterashorttime.Afterreadingthisstoryyouwillunderstandwhy.AtthattimeVerweggistanwasquitepopular,becauseitwastheonlyplaceintheworldwherepeopleknewhowtomakea'prul'.TheendofthetradeonVerweggistanmeanttheendofthetradeinpruls(or'prullen',astheDutchpluralsaid),andveryfewpeoplenowadaysknowwhataprulactuallyis.Prulsweremanufacturedinworkyards.Wheneveraprulwasfinisheditwaspackedinabox,whichwasthenplacedontopofthepileofpreviouslyproducedpruls.Onthesideofeachboxthepricewaswritten.Thepricedependedonthetimeittooktomanufacturetheprul.Ifallwentwell,aprulwouldcostoneortwoflorins,butonabaddaythepricecouldeasilyriseto15florinsormore.Thishadnothingtodowithquality;allprulshadthesamevalue.Inthosedaysprulssoldfor10florinseachinHolland.Transportationcostswerenegligiblesincetheprulsweretakenasextraonshipsthatwouldsailanyway.WhenaDutchmerchantwenttoVerweggistan,hehadaclearpurpose:buypruls,selltheminHolland,andmaximizehisprofits.Unfortunately,theVerweggistanwayoftradingprulsmadethismorecomplicatedthanonewouldthink.Onewouldexpectthatmerchantswouldsimplybuythecheapestpruls,andtheprulsthatcostmorethan10florinswouldremainunsold.Unfortunately,allworkyardsonVerweggistansoldtheirprulsinaparticularorder.Theboxontopofthepilewassoldfirst,thenthesecondonefromthetop,andsoon.Soevenifthefifthboxfromthetopwasthecheapestone,amerchantwouldhavetobuytheotherfourboxesabovetoobtainit.Asyoucanimagine,thismadeitquitedifficultforthemerchantstomaximizetheirprofitsbybuyingtherightsetofpruls.Nothavingcomputerstohelpwithoptimization,theyquicklylostinterestintradingprulsatall.Inthisproblem,youaregiventhedescriptionofseveralworkyardpiles.Youhavetocalculatethemaximumprofitamerchantcanobtainbybuyingprulsfromthepilesaccordingtotherestrictionsgivenabove.Inaddition,youhavetodeterminethenumberofprulshehastobuytoachievethisprofit.Input：Theinputdescribesseveraltestcases.Thefirstlineofinputforeachtestcasecontainsasingleintegerw,thenumberofworkyardsinthetestcase(1<=w<=50).Thisisfollowedbywlines,eachdescribingapileofpruls.Thefirstnumberineachlineisthenumberbofboxesinthepile(0<=b<=20).Followingitarebpositiveintegers,indicatingtheprices(inflorins)oftheprulsinthestack,givenfromtoptobottom.Theinputisterminatedbyadescriptionstartingwithw=0.Thisdescriptionshouldnotbeprocessed.Output：Foreachtestcase,printthecasenumber(1,2,...).Thenprinttwolines,thefirstcontainingthemaximumprofitthemerchantcanachieve.Thesecondlineshouldspecifythenumberofprulsthemerchanthastobuytoobtainthisprofit.Ifthisnumberisnotuniquelydetermined,printthepossiblevaluesinincreasingorder.Iftherearemorethantenpossiblevalues,printonlythe10smallest.Displayablanklinebetweentestcases.SampleInput16123107165257311910912341016104160SampleOutputWorkyards1Maximumprofitis8.Numberofprulstobuy:4Workyards2Maximumprofitis40.Numberofprulstobuy:6789101213參考代碼:#include<stdio.h>#include<memory.h>#include<algorithm>usingnamespacestd;booldp[2][1050];intprofit[25],cnt[55];intmain(){intp,no=0;while(scanf("％d”,&p),p){intn,i,j,price,maxNum,pre=0,now=1,res=0;memset(dp,0,sizeof(dp));dp[pre][0]=true;for(i=0;i<p;++i){scanf("％d“，&n);maxNum=-1;for(j=0；j<n;++j){scanf("％d”,&price);if(j==0)profit[0]=10-price;elseprofit[j]=profit[j-1]+(10-price);if(profit[j]>maxNum)maxNum=profit[j];}if(maxNum>=0){res+=maxNum;intloc=0;if(maxNum==0)cnt[loc++]=0;for(j=0;j<n;++j)if(profit[j]==maxNum)cnt[loc++]=j+1;memset(dp[now],0,sizeof(dp[now]));forG=0；j<1050;++j)if(dp[pre][j])for(intk=0;k<loc;++k)dp[now][j+cnt[k]]=true;swap(now,pre);)}if(no)printf("\n");printf("Workyards%d\n",++no);printf("Maximumprofitis%d.\n",res);printf("Numberofprulstobuy:")；intinc=0;for(i=0;i<1050;++i){if(dp[pre][i]){inc++;printf("%d",i); }if(inc==10)break;}printf("\n");}return0;PKU1775:SumofFactorialsDescription：JohnvonNeumann,b.Dec.28,1903,d.Feb.8,1957,wasaHungarian-Americanmathematicianwhomadeimportantcontributionstothefoundationsofmathematics,logic,quantumphysics,meteorology,science,computers,andgametheory.Hewasnotedforaphenomenalmemoryandthespeedwithwhichheabsorbedideasandsolvedproblems.In1925hereceivedaB.S.diplomainchemicalengineeringfromZurichInstituteandin1926aPh.D.inmathematicsfromtheUniversityofBudapest.HisPh.D.dissertationonsettheorywasanimportantcontributiontothesubject.Attheageof20,vonNeumannproposedanewdefinitionofordinalnumbersthatwasuniversallyadopted.Whilestillinhistwenties,hemademanycontributionsinbothpureandappliedmathematicsthatestablishedhimasamathematicianofunusualdepth.HisMathematicalFoundationsofQuantumMechanics(1932)builtasolidframeworkforthenewscientificdiscipline.Duringthistimehealsoprovedthemini-maxtheoremofGAMETHEORY.Hegraduallyexpandedhisworkingametheory,andwithcoauthorOskarMorgensternhewroteTheoryofGamesandEconomicBehavior(1944).Therearesomenumberswhichcanbeexpressedbythesumoffactorials.Forexample9,9=1!+2!+3!Dr.vonNeumannwasveryinterestedinsuchnumbers.So,hegivesyouanumbern,andwantsyoutotellhimwhetherornotthenumbercanbeexpressedbythesumofsomefactorials.Well,it'sjustapieceofcake.Foragivenn,you'llcheckiftherearesomexi,andletnequaltoZ1<=j<=txi!.(t>=11,xi>=0,xi=xjiff.i=j).Iftheanswerisyes,say"YESM;otherwise,printout"NO".Input：Youwillgetseveralnon-negativeintegern(n<=1,000,000)frominputfile.Eachoneisinalinebyitself.Theinputisterminatedbyalinewithanegativeinteger.Output：Foreachn,youshouldprintexactlyoneword("YES"or"NO")inasingleline.Noextraspacesareallowed.SampleInput9-1SampleOutputYES題意意思:給出ー個數(shù),要求判斷這個數(shù)能否等于?些階乘的和k=a1!+a2!+..+an!(a1,a2..an都不相等,n不確定)如果等式可以成立,輸出YES,永遠(yuǎn)不能成立輸出N〇,注意幾點(diǎn):0!=1,輸入〇時候輸出NO參考代碼:01背包#include<iostream>intd[20];usingnamespacestd;voidc(){ d[1]=1;d[0]=1;inti;for(i=2;d[i-1]<=1000000;i++) d[i]=d[i-1]*i;)intmain(){c();intb,i,j;boolv[1000001]：memset(v,0,sizeof(v));v[0]=true：for(i=0;i<=9;i++)for(j=1000000;j>=1;j-) if(!v[j]&&j>=d[i])v[j]=v[j-d叩;while(scanf(,,%dH,&b)!=EOF&&b>=0)if(b==0)printfC'NO\nH);elseif(v[b])printf("YES\nw);elseprintf(HNO\n");return0;}PKU1948:TriangularPasturesDescription：Likeeveryone,cowsenjoyvariety.Theircurrentfancyisnewshapesforpastures.Theoldrectangularshapesareoutoffavor;newgeometriesarethefavorite.I.M.Hei,theleadcowpasturearchitect,isinchargeofcreatingatriangularpasturesurroundedbynicewhitefencerails.SheissuppliedwithN(3<=N<=40)fencesegments(eachofintegerlengthLi(1<=Li<=40)andmustarrangethemintoatriangularpasturewiththelargestgrazingarea.Ms.Heimustusealltherailstocreatethreesidesofnon-zerolength.HelpMs.Heiconvincetherestoftheherdthatplentyofgrazinglandwillbeavailable.Calculatethelargestareathatmaybeenclosedwithasuppliedsetoffencesegments.Input：*Line1:AsingleintegerN*Lines2..N+1:Nlines,eachwithasingleintegerrepresentingonefencesegment'slength.Thelengthsarenotnecessarilyunique.Output：Asinglelinewiththeintegerthatisthetruncatedintegerrepresentationofthelargestpossibleenclosedareamultipliedby100.Output-1ifnotriangleofpositiveareamaybeconstructed.SampleInput511334SampleOutput692解題思路:首先ー個想法是,盡量湊出三條長度差不多的邊,然后計(jì)算面積。但是這樣不對,我們并不能保證那就是最優(yōu)解。最終覺得,還是枚舉比較合適。枚舉第一條邊的長度,我們需要快速知道第二條邊和第三條邊的取值的可能的組合。因?yàn)槿绻赖诙l邊的長度,我們可以根據(jù)周長求到第三條邊的長度,所以問題就變成了已知一條邊,如何快速求另外一條邊長度可能的取值,其實(shí)也就是子集和的問題。解答方式很簡單,就是在傳統(tǒng)的背包問題上,多給它增加一個背包。DP[i][j]図表示使用前i個木棍，能否湊出長度為j和k的兩根木棍。DP方程是DP[i][j][k]=DP[i-1]0-length[i]][k]=DP[i-1][j][k-length[i]]參考代碼:枚舉+01背包#include"math.h”#include<iostream>usingnamespacestd;boolDP[1605][1605];intlength[41],sum;;doubleL,tmp;intmain(){intN;scanf("％d”,&N);sum=O;for(inti=O;i<N;i++){scanf("％cT,&length[i]);sum+=length[i];}L=(double)sum/2;intmaxFirst=0,maxSecond=0,maxFirstNext=0,maxSecondNext=0;;memset(DP,0,sizeof(DP));DP[maxFirst][maxSecond]=true;for(inti=O;i<N;i++){maxFirst=maxFirstNext;maxSecond=maxSecondNext;for(intj=maxFirst;j>=O;j-)for(intk=maxSecond;k>=0;k-)if(DP咽){DPO+length[i]][k]=DPO][k+length[i]]=true;maxFirstNext=max(maxFirstNext,j+length[i]);maxSecondNext=max(maxSecondNext,k+length[i]);))doubleans=0;for(intj=1;j<=maxFirstNext;j++){for(intk=j;k<=maxSecondNext;k++){if(sum-j-k<k)break;if(DP皿k]){ tmp=L*(L-j)*(L-k)*0+k-L);if(tmp<=0)continue;ans=max(ans,sqrt(tmp));})}if(ans>0)printf("%d\n",(int)(ans*100));elseprintf("-1\n");return0;)解題思路2:從三角形的兩邊出發(fā),設(shè)dp[i][j][k]表示用前i根木棍能否組成一邊長度為j,另ー邊長度為k的邊,容易發(fā)現(xiàn)該狀態(tài)具有最優(yōu)子結(jié)構(gòu)性質(zhì),遞推關(guān)系為:dp[i]0][k]=dp[i-1]0][k]|dp[i-1]0-len[i]][k]|dp[i-1]0][k-len[i]];參考代碼2：#include<cstdio>#include<cstring>#include<cmath>usingnamespacestd;intlen[45],n;booldp[45][1000][1000];doublecul(inta,intb,intc){doublep=(a+b+c)/2.0;returnsqrt(p*(p-a)*(p-b)*(p-c));}intmain(){inti,j,k,s;intbound,sum=0;doubletmp,area=0;scanf("%d",&n);for(i=1;i<=n;i++){scanf(M%dM,&len[i]);sum+=len[i];}bound=sum/2; dp[0][0][0]=true;for(i=1;i<=n;i++)for(j=0;j<=bound;j++)for(k=0;k<=bound;k++)dp[i]D][k]=dp[i-1][j][k]|(len[i]<=j&&dp(i-1]0-len[i]][k])|(len[i]<=k&&dp[i-1][j][k-len[i]]);for(j=1；j<=bound;j++)for(k=1;k<=bound;k++){s=sum-j-k;if(dp[n][j][k]&&j+k>s&&j+s>k&&k+s>j&&(tmp=cul(j,k,s))>area)area=tmp;)if(area==0)printf(w-1\nM);elseprintf(M%d\nM,int(area*100));return0;)PKU1837:BalanceDescription：Gigelhasastrange"balance1'andhewantstopoiseit.Actually,thedeviceisdifferentfromanyotherordinarybalance.Itorderstwoarmsofnegligibleweightandeacharm'slengthis15.SomehooksareattachedtothesearmsandGigelwantstohangupsomeweightsfromhiscollectionofGweights(1<=G<=20)knowingthattheseweightshavedistinctvaluesintherange1..25.Gigelmaydroopanyweightofanyhookbutheisforcedtousealltheweights.Finally,GigelmanagedtobalancethedeviceusingtheexperiencehegainedattheNationalOlympiadinInformatics.Nowhewouldliketoknowinhowmanywaysthedevicecanbebalanced.Knowingtherepartitionofthehooksandthesetoftheweightswriteaprogramthatcalculatesthenumberofpossibilitiestobalancethedevice.Itisguaranteedthatwillexistatleastonesolutionforeachtestcaseattheevaluation.Input：Theinputhasthefollowingstructure:thefirstlinecontainsthenumberC(2<=C<=20)andthenumberG(2<=G<=20);thenextlinecontainsCintegernumbers(thesenumbersarealsodistinctandsortedinascendingorder)intherange-15..15representingtherepartitionofthehooks;eachnumberrepresentsthepositionrelativetothecenterofthebalanceontheXaxis(whennoweightsareattachedthedeviceisbalancedandlineduptotheXaxis;theabsolutevalueofthedistancesrepresentsthedistancebetweenthehookandthebalancecenterandthesignofthenumbersdeterminesthearmofthebalancetowhichthehookisattached:L，fortheleftarmand'+'fortherightarm);onthenextlinethereareGnatural,distinctandsortedinascendingordernumbersintherange1..25representingtheweights'values.Output：TheoutputcontainsthenumberMrepresentingthenumberofpossibilitiestopoisethebalance.SampleInput24-233458SampleOutput題意:ー個杠桿,中心有支點(diǎn),兩邊有掛鉤,掛鉤位置由輸入給定。有一些祛碼,祛碼重量由輸入給定。ー個掛鉤下可以掛多個祛碼,也可以什么都不掛,但每個祛碼必須都用。問有多少種組合方式,可以使杠桿平衡。解題思路1：DP[i][j]表示放置第i個物品后,總質(zhì)量為j的可能組合的數(shù)量。狀態(tài)轉(zhuǎn)移方程DP[i+1]U]=sum{DP[i]0-weight[i]*hook[k]](1<=k<=C)}初始化DP[0][0]=1,最后輸出DP[G][O].因?yàn)镈P[i][j]中j可能為負(fù)數(shù),在代碼中給j加上一個偏移量base。參考代碼1:空間未優(yōu)化#include<iostream>usingnamespacestd;constintbase=6000;intDP[21][base+base];inthook[20],weight[20];intmain(){memset(DP,0,sizeof(DP));intC,G;scanf("％d%d”,&C,&G);for(inti=0;i<C;i++)scanf(M%dw,&hook[i]);for(inti=0;i<G;i++)scanf(M%dM,&weight[i]);DP[0][0+base]=1;for(inti=1;i<=G;i++)for(intj=-4000+base;jv4000+base;j++)for(intk=0;kvC;k++)DP[i][j]+=DP[i-1]0-hook[k]*weight[i-1]];printf(w%d\nM,DP[G][O+base]);return0;)解題思路2:這ー題可以轉(zhuǎn)化為01背包問題,如果所有物體?邊倒,不平衡的差最多是20*15*25=7500,可以設(shè)ー個背包里本身就有7500的重量,如果坐標(biāo)位置l[i]是正的,我們相當(dāng)于往里面放入w[i]*p[i]的重量,否則是取出物品。設(shè)dp[i][j]表示掛上i件物品重量為j的方法數(shù),則狀態(tài)轉(zhuǎn)移方程為:dp[i][k+w[i]*p[j]]+=dp[i-1][k];i=1-g,j=1-c,k=0~15000那么dp[m][7500]即為所求結(jié)果,因?yàn)轭}目要求所有的祛碼用完,所以是m,7500表示是平衡狀態(tài)下的方法數(shù)(因?yàn)檫@個背包最初的重量就是7500),為了防止出現(xiàn)負(fù)數(shù),設(shè)重量為0-15000。參考代碼2:空間未優(yōu)化#include<stdio.h>#include<string.h>intdp[21][15001];intmain(){intn,m,i,j,k; intw[21],p[21];while(scanf(M%d%dM,&n,&m)!=EOF){for(i=1;i<=n;i++)scanf(M%dw,&w[i]);for(i=1;i<=m;i++)scanf(”％d”,&p[i]);memset(dp,0,sizeof(dp));for(i=1;i<=n;i++)dp[1][7500+w[i]*p[1]]++;for(i=2;i<=m;i++)for(j=1;j<=n;j++)for(k=0;k<=15000;k++)if(dp[i-1][k]!=0)dp[i][k+wU]*p[i]]+=dpP-1][k];printf("%d\n",dp[m][7500]);)return0;}PKU1014:DividingDescription：MarshaandBillownacollectionofmarbles.Theywanttosplitthecollectionamongthemselvessothatbothreceiveanequalshareofthemarbles.Thiswouldbeeasyifallthemarbleshadthesamevalue,becausethentheycouldjustsplitthecollectioninhalf.Butunfortunately,someofthemarblesarelarger,ormorebeautifulthanothers.So,MarshaandBillstartbyassigningavalue,anaturalnumberbetweenoneandsix,toeachmarble.Nowtheywanttodividethemarblessothateachofthemgetsthesametotalvalue.Unfortunately,theyrealizethatitmightbeimpossibletodividethemarblesinthisway(evenifthetotalvalueofallmarblesiseven).Forexample,ifthereareonemarbleofvalue1,oneofvalue3andtwoofvalue4,thentheycannotbesplitintosetsofequalvalue.So,theyaskyoutowriteaprogramthatcheckswhetherthereisafairpartitionofthemarbles.Input：Eachlineintheinputfiledescribesonecollectionofmarblestobedivided.Thelinescontainsixnon-negativeintegersn1,...,n6,whereniisthenumberofmarblesofvaluei.So,theexamplefromabovewouldbedescribedbytheinput-line**10120〇”.Themaximumtotalnumberofmarbleswillbe20000.Thelastlineoftheinputfilewillbe"00000〇”;donotprocessthisline.Output：Foreachcollection,output"Collection#k:",wherekisthenumberofthetestcase,andtheneither"Canbedivided."or"Can'tbedivided.".Outputablanklineaftereachtestcase.SampleInput101200100011000000SampleOutputCollection#1:Can'tbedivided.Collection#2:Canbedivided.問題描述:有價值分別為1..6的大理石各a[1..6]塊,現(xiàn)要將它們分成兩部分,使得兩部分價值之和相等,問是否可以實(shí)現(xiàn)。其中大理石的總數(shù)不超過20000。問題分析:很明顯是一個劃分問題一分成等價值的兩部分,進(jìn)ー步可以發(fā)現(xiàn)也是一個組合問題,即:第一部分選擇哪些大理石,選擇多少;第二部分則選擇剩余即可。首先,排除總價值之和為奇數(shù)的情況,輸出“Can'tbedivided.”然后對于組合最優(yōu)化問題,動態(tài)規(guī)劃無疑是最強(qiáng)有力的方法,而且這個問題似乎與經(jīng)典的背包問題有點(diǎn)類似,不過這里是兩個背包,而且要求的是“判斷兩者是否可以裝等價值的物品”,比起要你求出如何裝載成等同價值的兩個背包,難度減少了不少,所以即使這里涉及到的是兩個背包,也可以方便的用動態(tài)規(guī)劃。算法設(shè)計(jì):使用傳統(tǒng)的二維數(shù)組,與背包問題類似,用表示:可否從1到i的大理石中選出部分大理石,使得其價值之和等于j,若能則置f同[j]為true,不能就置為false?因此最后需要判斷的就是:如果有一個i滿足f[i][mid]==true則可以實(shí)現(xiàn)題目要求，否則不可以實(shí)現(xiàn)。下面給出DP的邊條與狀態(tài)轉(zhuǎn)移方程：首先邊界狀態(tài):f皿0]=false；0<=i<=6(即肯定可以選出價值和等于〇的)其次狀態(tài)轉(zhuǎn)移方程：f[i][j]=f[i]Q]orf[i-1]0-i*k];1<=i<=6；1<=j<=sum/2；k表示從第i價值的大理石中任意選取〇?a[i]項(xiàng)，即。<=k<=a[i]。(sum表示輸入的總價值)參考代碼：多重背包include"stdlib.h"#include"string.h"#include"stdio.h"#defineMAXN20001*22intn[7];booldp[MAXN];intmain(){inti,j,k,amount;intcnt=1;while(scanf("%d%d%d%d%d%d",&n[1],&n[2],&n[3],&n[4],&n[5],&n[6])&&(n[1]||n[2]||n[3]||n[4]||n[5]||n[6])){intsum=0;for(i=1;i<=6;i++)sum+=n[i]*i;printf("Collection#%d:\n",cnt++);memset(dp,0,sizeof(dp));dp[0]=1;if(sum%2)printf("Can'tbedivided.\n\n");else{ sum/=2; 〃達(dá)到一半的容量，就是背包容量for(i=1;i<=6;i++) //6組{if(!n[i])continue;amount=sum; 〃多重背包，加壓縮開始if(n[i]*i>=amount) 〃大于那么就是完全背包for(j=0;j<=amount;j++)if(dpO-i]&&j>=i)dp[j]=1;else{ k=1;〃一個amount=n[i];while(k<amount){for(j=sum;j>=k*i;j-)if(dp[j-k*i])dp[j]=1;amount-=k;k*=2;)for(j=sum;j>=amount*i;j-)if(dp[j-amount*i])dp[j]=1;)}if(dp[sum])printf("Canbedivided.\n\n");elseprintf("Can'tbedivided.\n\n");}}return0;)解題思路：想到動態(tài)規(guī)劃的做法，令S=Z(i*a[i]),若S為奇數(shù)，則不可能實(shí)現(xiàn)，否則令Mid=S/2,則問題轉(zhuǎn)化為能否從給定的大理石中選取部分大理石,使其價值和為Mid。m[i,j],04區(qū)6,OvjMMid,表示能11否從價值為1..i的大理石中選出部分大理石,使其價值和為j,若能,則用true表示,否則用false表示。則狀態(tài)轉(zhuǎn)移方程為:m[i,j]=m[i,j]ORm[i-1 (0<k<a[i])?規(guī)劃的邊界條件為:m[i,0]=true；0<i<6若m[i,Mid]=true,0<i<6,則可以實(shí)現(xiàn)題目要求,否則不可能實(shí)現(xiàn)。時間復(fù)雜度6*20000?60000〇需要有更優(yōu)的動態(tài)規(guī)劃做法:狀態(tài)與上述ー樣,增加一個狀態(tài)向量usednum[][]usednum[i][x]=y表示第i堆石頭最少用了y塊能達(dá)到重量x狀態(tài)轉(zhuǎn)移如下:m[i][j]=m[i]0]ora[i]>=usednum[i][j]>0,usednum[i][j]=min{usednum[i][j],if(m[i-1][j-k])1,use[i][j-k]+1}參考代碼1：#include<cstdio>#include<cstring>intmain(){intstone[7],cas=0;while(true){cas++;inti,j,k,sum=O;for(i=1;i<7;i++) { scant(M%dw,&stone[i]);sum+=i*stone[i];}if(sum==0)break;printf(HCollection#%d:\n",cas);if(sum%2!=0){printf(MCan'tbedivided.\n\nM);continue;}inthalf=sum/2;booldp[65536];intusednum[65536];memset(dp,false,sizeof(dp));dp[O]=true;intup=0;for(k=1;k<7;k++)if(stone[k]>0){if(dp[half])break;memset(usednum,0,sizeof(usednum));for(i=0;i<=up;i++){if(dp[i]){j=i+k;if(j>half)break;if(!dp[j])usednum[j]=1;if(j>up)up=j;)elseif(usednum[i]>0&&usednum[i]<stone[k]){j=i+k；if(j>half)break;if(!dp[j])if(usednum[j]==0||usednum[i]+1<usednum[j])usednum[j]=usednum[i]+1;if(卜up) up=j;)}for(i=0;i<=up;i++)if(usednum[i]>0)dp[i]=true;)if(dp[half])printf("Canbedivided.\n\n");elseprintf("Can'tbedivided.\n\n");)return0;參考代碼2：01背包#include<iostream>#include<algorithm>usingnamespacestd;constintMAXN=10000;constintMAXM=250000;intindex,v[MAXN];intm[2][MAXM];boolknapsack(inttot){inti,w,x,y,ans=0;memset(m,0,sizeof(m));for(w=v[〇];w<=tot;w++){ m[0][w]=v[0];ans=v[〇]; }for(i=1;i<index;i++){x=i%2;y=(i+1)%2;for(w=0;w<=tot;w++){if(v[i]>w)m[x][w]=m[y][w];elsem[x][w]=max(m[y][w],m[y][w-v[i]]+v[i]);ans=max(ans,m[x][w]);}}if(ans==tot)returntrue;elsereturnfalse;)intmain(){inti,j,cases=0;intval[6][2];while(true){intnum,n=0,sum=0;for(i=0;i<6;i++){scanf("％d“，&num);if(num){val[n][0]=num;val[n][1]=i+1;sum+=val[n][0]*val[n][1];n++;}}if(sum==0)break;printfC'Collection#%d:\n",++cases);if(sum%2){printf("Can'tbedivided.\n\nH);continue;}index=0;for(i=0;i<n;i++){j=1；while(2*j<=val[i][0]){v[index++]=j*val[i][1]; j?=1; }if(val[i][0]-j+1>0)v[index++]=(val[i][0]-j+1)*val[i][1];)boolfind=knapsack(sum/2);if(find==false)printf(,'Can,tbedivided-');elseprintf("Canbedivided.\n\nw);)return(O);參考代碼3:打表多重背包,有分組#includeMstdlib.h"include“string.h"include"stdio.h"#defineMAXN20001*22intn[7];booldp[MAXN];intmain(){ inti,j,k,amount; intcnt=1;while(scanf("%d%d%d%d%d%d,',&n[1],&n[2],&n[3],&n[4],&n[5],&n[6])&&(n[1]||n[2]||n[3]||n[4]||n[5]||n[6])){intsum=0;for(i=1;i<=6;i++)sum+=n[i]*i;printf(HCollection#%d:\n",cnt++);memset(dp,0,sizeof(dp));dp[0]=1;if(sum%2)printfC'Can'tbedivided.\n\nn);else{ sum/=2; 〃達(dá)到一半的容量,就是背包容量for(i=1;i<=6;i++) 〃6組{ if(!n[i])continue;amount=sum;〃多重背包,加壓縮開始if(n[i]*i>=amount) 〃大于那么就是完全背包{for(j=0;j<=amount;j++)if(dp[j-i]&&j>=i) dp0]=1;)else{ k=1; 〃ー個amount=n[i];while(k<amount){for(j=sum;j>=k*i;j-)if(dp[j-k*i]) dp0]=1;amount-=k;k*=2;}for(j=sum;j>=amount*i;j-)if(dp[j-amount*i]) dp[j]=1;}}if(dp[sum])printf("Canbedivided.\n\n");elseprintf("Can'tbedivided.\n\n");)}return0;)參考代碼2:多重背包#include<iostream>usingnamespacestd;intsum;inta[7];intdp[60001];intmain(){intT=1;while(1){sum=0;for(inti=1;i<=6;i++){scanf("％cT,&a[i]);sum+=a[i]*i; }f(sum==0)break;if(sum%2){printf(MCollection#%d:\nCan*tbedivided.\n\n,,,T++)：continue;}sum=sum/2; memset(dp,〇,sizeof(dp)); dp[O]=1;for(inti=1;i<=6;i++)for(intj=sum;j>=0;j-)if(dp[j]){intt=j;for(intk=1;k<=a[i];k++){t+=i;if(t>sum)break;dp[t]=1; })printfC'Collection#%d:\n”,T++);if(dp[sum]==1)printf(HCanbedividedAn");elseprintf(MCan'tbedividedAn");printf("\n")；)return0;)PKU3624:CharmBraceletDescription：Bessiehasgonetothemall'sjewelrystoreandspiesacharmbracelet.Ofcourse,she'dliketofillitwiththebestcharmspossiblefromtheN(14NS3,402)availablecharms.EachcharmiinthesuppliedlisthasaweightWi(1<Wi<400),a'desirability*factorDi(1<Di<100),andcanbeusedatmostonce.BessiecanonlysupportacharmbraceletwhoseweightisnomorethanM(1M<12,880).Giventhatweightlimitasaconstraintandalistofthecharmswiththeirweightsanddesirabilityrating,deducethemaximumpossiblesumofratings.Input：Line1:Twospace-separatedintegers:NandMLines2..N+1:Linei+1describescharmiwithtwospace-separatedintegers:WiandDiOutput：Line1:AsingleintegerthatisthegreatestsumofcharmdesirabilitiesthatcanbeachievedgiventheweightconstraintsSampleInput46142631227SampleOutput23題目意思:有n個物品,兩個屬性w,d,限定w的最大限度m,求max(sum(d))解題思路1：01背包參考代碼1:空間未優(yōu)化#include<stdio.h>#include<string.h>#defineMAX_N3500#defineMAX_W13000structthings{intweight;intvalue;};intGetMax(inta,intb){returna>b?a:b;}thingst[MAX_N];intw[2][MAX_W];intmain(){intm,n;inti,j;intpos;while(scanf(,,%d%dH,&n,&m)!=EOF){memset(w,0,sizeof(w));for(i=1;i<=n;i++)scanf(',%d%dM,&t[i].weight,&t[i].value);pos=0;for(i=1;iv=n;i++){for(j=1;j<=m;j++)if(j>=t[i].weight)w[i%2][j]=GetMax(w[pos][j],w[pos][j-t[i].weight]+t[i].value);elsew[i%2][j]=w[pos][j];pos++;pos%=2;}printf(M%d\nn,w[pos][m]);)return0;)解題思路2：01背包空間已優(yōu)化#include<stdio.h>#defineM13000#defineN3500intmain(){inta[N][2]; 〃用于存放物品數(shù)與背包容量,以及各物品的權(quán)重與價值inti,j;intb[M];while(scanf("%d%d",&a[0][0],&a[0][1])==2){ for(i=0;i<=a[0][1];i++)b[i]=0;〃數(shù)組b清零處理for(i=1;i<=a[0][0];i++) 〃讀入數(shù)據(jù)生成一個各物品的權(quán)重與價值的對應(yīng)表{scanf("%d%d",&a[i][0],&a[i][1])；for(j=a[0][1];j>=a[i][0];j-)〃此處j的判斷條件不是j>=1!!!否則會因數(shù)組下標(biāo)而出錯!if(b[j-a[i][0]]+a[i][1]>bO])〃將最大的價值賦給當(dāng)前位置

b[j]=b[j-a[i][0]]+a[i][1]; 〃至關(guān)重要的式子!！)printf("%d\n",b[a[0][1]]);)return0;解題思路3：01背包空間已優(yōu)化#include<iostream>#include<algorithm>usingnamespacestd;intw[3500];intv[3500];intdp[13000];intmain(){intn,m;inti,j;scanf("%d%d,1,&n,&m);for(i=1;i<=n;i++)scanf(M%d%dM,&w[i],