动态规划练习题含答案.docx
- 文档编号:14693470
- 上传时间:2023-06-26
- 格式:DOCX
- 页数:12
- 大小:21.17KB
动态规划练习题含答案.docx
《动态规划练习题含答案.docx》由会员分享,可在线阅读,更多相关《动态规划练习题含答案.docx(12页珍藏版)》请在冰点文库上搜索。
动态规划练习题含答案
动态规划练习题
USACO2.2SubsetSums
题目如下:
对于从1到N的连续整集合合,能划分成两个子集合,且保证每个集合的数字和是相等的。
举个例子,如果N=3,对于{1,2,3}能划分成两个子集合,他们每个的所有数字和是相等的:
and{1,2}
这是唯一一种分发(交换集合位置被认为是同一种划分方案,因此不会增加划分方案总数)
如果N=7,有四种方法能划分集合{1,2,3,4,5,6,7},每一种分发的子集合各数字和是相等的:
{1,6,7}and{2,3,4,5}{注1+6+7=2+3+4+5}
{2,5,7}and{1,3,4,6}
{3,4,7}and{1,2,5,6}
{1,2,4,7}and{3,5,6}
给出N,你的程序应该输出划分方案总数,如果不存在这样的划分方案,则输出0。
程序不能预存结果直接输出。
PROGRAMNAME:
subset
INPUTFORMAT
输入文件只有一行,且只有一个整数N
SAMPLEINPUT(filesubset.in)
7
OUTPUTFORMAT
输出划分方案总数,如果不存在则输出0。
SAMPLEOUTPUT(filesubset.out)
4
参考程序如下:
#include
usingnamespacestd;
constunsignedintMAX_SUM=1024;
intn;
unsignedlonglongintdyn[MAX_SUM];
ifstreamfin("subset.in");
ofstreamfout("subset.out");
intmain(){
fin>>n;
fin.close();
ints=n*(n+1);
if(s%4){
fout<<0< fout.close(); return; } s/=4; inti,j; dyn[0]=1; for(i=1;i<=n;i++) for(j=s;j>=i;j--) dyn[j]+=dyn[j-i]; fout<<(dyn[s]/2)< fout.close(); return0; } USACO2.3LongestPrefix 题目如下: 在生物学中,一些生物的结构是用包含其要素的大写字母序列来表示的。 生物学家对于把长的序列分解成较短的(称之为元素的)序列很感兴趣。 如果一个集合P中的元素可以通过串联(允许重复;串联,相当于Pascal中的“+”运算符)组成一个序列S,那么我们认为序列S可以分解为P中的元素。 并不是所有的元素都必须出现。 举个例子,序列ABABACABAAB可以分解为下面集合中的元素: {A,AB,BA,CA,BBC} 序列S的前面K个字符称作S中长度为K的前缀。 设计一个程序,输入一个元素集合以及一个大写字母序列,计算这个序列最长的前缀的长度。 PROGRAMNAME: prefix INPUTFORMAT 输入数据的开头包括1..200个元素(长度为1..10)组成的集合,用连续的以空格分开的字符串表示。 字母全部是大写,数据可能不止一行。 元素集合结束的标志是一个只包含一个“.”的行。 集合中的元素没有重复。 接着是大写字母序列S,长度为1..200,000,用一行或者多行的字符串来表示,每行不超过76个字符。 换行符并不是序列S的一部分。 SAMPLEINPUT(fileprefix.in) AABBACABBC . ABABACABAABC OUTPUTFORMAT 只有一行,输出一个整数,表示S能够分解成P中元素的最长前缀的长度。 SAMPLEOUTPUT(fileprefix.out) 11 示例程序如下: #include #defineMAXP200 #defineMAXL10 charprim[MAXP+1][MAXL+1]; intnump; intstart[200001]; chardata[200000]; intndata; intmain(intargc,char**argv) { FILE*fout,*fin; intbest; intlv,lv2,lv3; if((fin=fopen("prim.in","r"))==NULL) { perror("fopenfin"); exit (1); } if((fout=fopen("prim.out","w"))==NULL) { perror("fopenfout"); exit (1); } while (1) { fscanf(fin,"%s",prim[nump]); if(prim[nump][0]! ='.')nump++; elsebreak; } ndata=0; while(fscanf(fin,"%s",data+ndata)==1) ndata+=strlen(data+ndata); start[0]=1; best=0; for(lv=0;lv if(start[lv]) { best=lv; for(lv2=0;lv2 { for(lv3=0;lv+lv3 prim[lv2][lv3]==data[lv+lv3];lv3++) ; if(! prim[lv2][lv3]) start[lv+lv3]=1; } } if(start[ndata])best=ndata; fprintf(fout,"%i\n",best); return0; } USACO3.1ScoreInflation 题目如下: 我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。 我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。 你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。 输入包括竞赛的时间,M(1<=M<=10,000)和N,"种类"的数目1<=N<=10,000。 后面的每一行将包括两个整数来描述一个"种类": 第一个整数说明解决这种题目能得的分数(1<=points<=10000),第二整数说明解决这种题目所需的时间(1<=minutes<=10000)。 你的程序应该确定我们应该从每个"种类"中选多少道题目使得能在竞赛的时间中得到最大的分数。 来自任意的"种类"的题目数目可能任何非负数(0或更多)。 计算可能得到的最大分数。 PROGRAMNAME: inflate INPUTFORMAT 第1行: M,N--竞赛的时间和题目"种类"的数目。 第2-N+1行: 两个整数: 每个"种类"题目的分数和耗时。 SAMPLEINPUT(fileinflate.in) 3004 10060 250120 120100 3520 OUTPUTFORMAT 单独的一行包括那个在给定的限制里可能得到的最大的分数。 SAMPLEOUTPUT(fileinflate.out) 605 {从第2个"种类"中选两题,第4个"种类"中选三题} 示例程序如下: #include ifstreamfin("inflate.in"); ofstreamfout("inflate.out"); constshortmaxm=10010; longbest[maxm],m,n; void main() { shorti,j,len,pts; fin>>m>>n; for(j=0;j<=m;j++) best[j]=0; for(i=0;i fin>>pts>>len; for(j=len;j<=m;j++) if(best[j-len]+pts>best[j]) best[j]=best[j-len]+pts; } fout< } USACO3.3AGame 题目如下: 有如下一个双人游戏: N(2<=N<=100)个正整数的序列放在一个游戏平台上,两人轮流从序列的两端取数,取数后该数字被去掉并累加到本玩家的得分中,当数取尽时,游戏结束。 以最终得分多者为胜。 编一个执行最优策略的程序,最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。 你的程序要始终为第二位玩家执行最优策略。 PROGRAMNAME: game1 INPUTFORMAT 第一行: 正整数N,表示序列中正整数的个数。 第二行至末尾: 用空格分隔的N个正整数(大小为1-200)。 SAMPLEINPUT(filegame1.in) 6 4729 52 OUTPUTFORMAT 只有一行,用空格分隔的两个整数: 依次为玩家一和玩家二最终的得分。 SAMPLEOUTPUT(filegame1.out) 1811 参考程序如下: #include #defineNMAX101 intbest[NMAX][2],t[NMAX]; intn; void readx(){ inti,aux; freopen("game1.in","r",stdin); scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&aux); t=t[i-1]+aux; } fclose(stdin); } inlineint min(intx,inty){ returnx>y? y: x; } void solve(){ inti,l; for(l=1;l<=n;l++) for(i=1;i+l<=n+1;i++) best[l%2]=t[i+l-1]-t[i-1]-min(best[i+1][(l-1)%2], best[(l-1)%2]); } voidwritex(){ freopen("game1.out","w",stdout); printf("%d%d\n",best[1][n%2],t[n]-best[1][n%2]); fclose(stdout); } int main(){ readx(); solve(); writex(); return0; } USACO3.4RaucousRockers 题目如下: 你刚刚得到了流行的“破锣摇滚”乐队录制的尚未发表的N(1<=N<=20)首歌的版权。 你打算从中精选一些歌曲,发行M(1<=M<=20)张CD。 每一张CD最多可以容纳T(1<=T<=20)分钟的音乐,一首歌不能分装在两张CD中。 不巧你是一位古典音乐迷,不懂如何判定这些歌的艺术价值。 于是你决定根据以下标准进行选择: 歌曲必须按照创作的时间顺序在CD盘上出现。 选中的歌曲数目尽可能地多。 PROGRAMNAME: rockers INPUTFORMAT 第一行: 三个整数: N,T,M. 第二行: N个整数,分别表示每首歌的长度,按创作时间顺序排列。 SAMPLEINPUT(filerockers.in) 452 4342 OUTPUTFORMAT 一个整数,表示可以装进M张CD盘的乐曲的最大数目。 SAMPLEOUTPUT(filerockers.out) 3 参考程序如下: #include #defineMAX25 intdp[MAX][MAX][MAX],length[MAX]; int main() { FILE*in=fopen("rockers.in","r"); FILE*out=fopen("rockers.out","w"); inta,b,c,d,best,numsongs,cdlength,numcds; fscanf(in,"%d%d%d",&numsongs,&cdlength,&numcds); for(a=1;a<=numsongs;a++) fscanf(in,"%d",&length[a]); best=0; for(a=0;a for(b=0;b<=cdlength;b++) for(c=0;c<=numsongs;c++){ for(d=c+1;d<=numsongs;d++){ if(b+length[d]<=cdlength){ if(dp[a][c]+1>dp[a][b+length[d]][d]) dp[a][b+length[d]][d]=dp[a][c]+1; } else{ if(dp[a][c]+1>dp[a+1][length[d]][d]) dp[a+1][length[d]][d]=dp[a][c]+1; } } if(dp[a][c]>best) best=dp[a][c]; } fprintf(out,"%d\n",best); return0; } 解决背包问题 动态规划的定义: 动态规划的基本思想是把待求解的问题分解成若干个子问题,先求解子问题,然后再从这些子问题的解得到原问题的解,其中用动态规划分解得到的子问题往往不是互相独立的。 动态规划在查找有很多重叠子问题的情况的最优解时有效。 它将问题重新组合成子问题。 为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。 因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。 动态规划只能应用于有最优子结构的问题。 最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。 简单地说,问题能够分解成子问题来解决。 求解步骤如下: 1.找出最优解的性质,并刻画其结构特征; 2.递归地定义最优值; 3.以自底向上的方式计算出最优值; 4.根据计算最优值时得到的信息,构造最优解。 问题描述及实现: 背包问题: 解决背包问题的方法有多种,动态规划,贪心算法,回溯法,分支定界法都能解决背包问题。 其中动态规划,回溯法,分支定界法都是解决0-1背包问题的方法。 背包问题与0-1背包问题的不同点在于在选择物品装入背包时,可以只选择物品的一部分,而不一定是选择物品的全部。 在这里,我们组用的有贪心法和动态规划法来对这个问题进行算法的分析设计。 用动态规划的方法可以看出如果通过第n次选择得到的是一个最优解的话,那么第n-1次选择的结果一定也是一个最优解。 这符合动态规划中最优子问题的性质。 动态规划方法是处理分段过程最优化一类问题极其有效的方法。 在实际生活中,有一类问题的活动过程可以分成若干个阶段,而且在任一阶段后的行为依赖于该阶段的状态,与该阶段之前的过程是如何达到这种状态的方式无关。 这类问题的解决是多阶段的决策过程。 考虑用动态规划的方法来解决,这里的: 阶段是: 在前n件物品中,选取若干件物品放入背包中; 状态是: 在前n件物品中,选取若干件物品放入所剩空间为w的背包中的所最大价值; 决策是: 第n件物品放或者不放;由此可以写出动态转移方程: 我们用f[i,j]表示在前i件物品中选择若干件放在所剩空间为j的背包里所能获得最大价值是: f[i,j]=max{f[i-1,j-wi]+pi(j>=wi),f[i-1,j]}。 这样,我们可以自底向上地得出在前m件物品中取出若干件放进背包能获得的最大价值,也就是f[m,w]令f(i,j)表示用前i个物体装出重量为j的组合时的最大价值 f(i,j)=max{f(i-1,j),f(i-1,j-w[i])+v[i]},i>0,j>=w[i]; f(i,j)=f(i-1,j),i>0,j f(0,j)=v[0],i=0,j>=w[0]; f(0,j)=0,i=0,j 代码实现: packagezyf; publicclassbagPro{ publicstaticvoidmain(String[]args){ //TODO自动生成方法存根 intw[]={2,2,6,5,4};//5个物体各自的重量 intv[]={6,3,5,4,6};//5个物体各自的价值 intc=10;//最大载重 intf[][]=newint[5][c+1];//前i个物体装出重量为j的组合时的最大价值 intmaxValue=0; for(intj=0;j<=c;j++){ if(j>=w[0]) f[0][j]=v[0]; else f[0][j]=0; } for(inti=1;i for(intj=0;j<=c;j++){ if(j f[i][j]=f[i-1][j]; elseif(f[i-1][j]>=f[i-1][j-w[i]]+v[i]) f[i][j]=f[i-1][j]; else f[i][j]=f[i-1][j-w[i]]+v[i]; } } System.out.println(f[4][c]); } } topcodersrm442d2背包问题 n个正整数,可能有重复,现在要找出两个不相交的子集A和B,A和B不必覆盖所有元素,使A中元素的和SUM(A)与B中元素的和SUM(B)相等,且SUM(A)和SUM(B)尽可能大。 intMX=500000; int[,]c=newint[2,MX*2+1]; intT; intfunction(int[]d) { inti,j; for(i=0;i<=MX*2;i++) c[T,i]=-1; c[T,MX]=0; for(i=0;i T=1-T; for(j=0;j c[T,j]=c[1-T,j]; for(j=0;j { if(c[1-T,j]<0) continue; c[T,j+d[i]]=Math.Max(c[T,j+d[i]],c[1-T,j]+d[i]); c[T,j-d[i]]=Math.Max(c[T,j-d[i]],c[1-T,j]); } } returnc[T,MX]! =0? c[T,MX]: -1; } 状态1是前i个元素,状态2是构造的两个子集的差的绝对值为j,保存的是较小的那个子集的最大sum。 这样两个子集的和就分别是dp[i][j]和dp[i][j]+j。 然后枚举当前元素放在小集合还是大集合,或者干脆就不放。 设f[i][j]是考虑i个元素时A的和,j是A和B的差。 当考虑i+1时,有三种情况: 1.跳过a[i+1],有f[i+1][j]=f[i][j]; 2.将a[i+1]加入A,有f[i+1][j+a[i+1]]=f[i][j]+a[i+1]; 3.将a[i+1]加入B,有f[i+1][j-a[i+1]]=f[i][j]; 填完这个表格后,f[n][0]即为所求。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 练习题 答案