动态规划试题

1、动态规划装箱问题(01背包):有一个箱子容量为VV(正整数，0WVW20000),同时有n个物品(0vnW30,每个物品有一个体积(正整数)。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。2468312797输出：0#include#includeusingnamespacestd;intf20005,w35;intmain()intv,n;cinvn;forfinti=l;iwi;for(inti=l;i=wi;j-)fj=max(fj/fj-wi+wi);coutv-fv;return0;fU=max(fU,fU-wi+wi);fUl为：当总容量为j时，不放第i件物品，所能装

2、的最大体积。fU-wi+wi为：当总容量为j时，放了第i件物品后，所能装的最大体积。(即j减去第i件物品体积的容量能装的最大体积+第i件物品的体积。wi为第i件物品体积)背包的种类：背包分为01背包，多重背包以及完全背包这三种基本模型，其他的背包问题都是从这3种背包中延申出来的。完全背包的模板题面是这样的：设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M,今从n种物品中选取若干件（同一种物品可以无限选取），使其重量的和小于等于M,而价值的和为最大。完全背包无限量的釆摘药输入：70 371 10069 112输出：140每个数组在满足条件，可以

3、遍历多次#include#includeusingnamespacestd;intf100001;inta10001,b10001;intmain()intn,m;cinnm;for(inti=l;iaibi;for(inti=l;i=m;i+)for(intj=ai;j#includeusingnamespacestd;inta101,b101;intf10001;intmain()intn,m;cinnm;for(inti=l;iaibi;for(inti=l;i=ai;j-)fj=max(fU,fU-ai+bi);coutfn;return0;题目描述金明今天很开心，家里购置的新房就要领

4、钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品,怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1-5表示，第5等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过N元(可以等于N元)的前提下，使每件物品的价格与重要度的乘积的总和最大。设第jj件物品的价格为vj,重要度为w_U,共选中了k件物品，编号依次为丄k,则所求的总和为：w_j_kvjlxwjl+vj2xwj2+.+vjkxwjko请你

5、帮助金明设计一个满足要求的购物单。输入格式第一行，为2个正整数，用一个空格隔开：nm(其中N(30000)表示总钱数，m(25)为希望购买物品的个数。)从第2行到第m+1行，第jj行给出了编号为卜1的物品的基本数据，每行有2个非负整数vp(其中vv表示该物品的价格(v10000),p表示该物品的重要度(1-5)输出格式1个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值(100000000)o输入：1000580024005300540032002输出：3900#includeusingnamespacestd;intf30010,k30,v30;intn,m;intmain()c

6、innm;for(inti=l;i=m;i+)cinkivi;for(inti=l;i=ki;j-)fUJ=max(fU,fU-ki+ki*vil);coutfn;return0;多重背包有N种物品和一个容量是V的背包。第ii种物品最多有sisi件，每件体积是vivi,价值是wiwio求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。数据范围0N,V1000vi,wi,si100输入样例451232 413 434 52输出样例：#includeusingnamespacestd;constintmaxn=110;intn；intvmaxn,wmaxnsma

7、xn;intfmaxnmaxn;intmain()cinnm;for(intiviwisi;for(inti=n;i+)for(intj=0;j=m;j+)for(intk=0;k=si&k*vi=j;k+)fij=max(fij,fi7j-k*vi+k*wi);coutfnm;neturn0;多重背包2有N种物品和一个容量是V的背包。第i种物品最多有si件，每件体积是归价值是wL求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。数据范围0N10000V20000vi,wi,si2000本题考查多重背包的二进制优化方法。输入样例451232 413 434

8、52输出样例：10#ineludeios#ineludeusingnamespacestd;constintN=12010,M=2010;intm;intvNwN;intfM;intmain()cinnm;intent二0;for(inti=1;iabirrtk=1;while(k0)ent+;vcnt=awcnt=bfor(inti=1;i=i+)vi；j-)fj-vi+wi);coutfmendl;returm0;线性动态规划数塔给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

9、数据范围1n500,-10000#includeconstintMAXV=10010;usingnamespacestd;intdpMAXVMAXV;intmain()intn;cinn;intann;fill(dpO/dpO+MAXV*MAXV,O);forfinti=0;in;i+)for(intj=0;jaij;forfinti=0;i=0;i-)for(intj=0;j=i;j+)dpiU=maxtdpIi+llULdpIi+lJU+l)+aij;coutdp00endl;return0;最大连续子序列和#include#includeusingnamespacestd;constin

10、tMAXV=10010;intAMAXV,dpMAXV;intmain()intn;cinn;for(inti=0;iAi;dpO=A0;for(inti=l;in;i+)dpi=max(Ai,dpi-l+Ai);sort(dp,dp+n);coutdpn-lendl;return0;6-211-413-5-2输出:20最长不下降子序列给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。数据范围1N1000,-10*9数列中的数109输入样例：73 121856输出样例：4#includeconstintMAXV=10010;usingnamespacestd;intdpMAX

11、V;cinn;intAn;for(inti=l;iAi;intans=-1;for(inti=l;i=n;i+)dpi=1；for(intj=l;jAU&(dpU+1)dpi)dpi=dpj+1;ans=max(ans,dpi);coutansendl;return0;最长公共子序列给定两个长度分别为N和M的字符串A和B,求既是A的子序列乂是B的子序列的字符串长度最长是多少。数据范围1N1000,输入样例：4 5acbdabedc输出样例#includeios#includeusingnamespacestd;constintmaxn=1010;charAmaxnBmaxn;intdpmaxn

12、maxn;intmain()intn；cinnm;for(inti=;iAi;for(inti=;iBi;for(inti=0;1=n；i+)dpi00；for(inti=0;1=m；i+)dp0i0；for(inti=l;1=n；i+)for(intj=l;j=m;j+)if(Ai=Bj)dpij=dpi-lj-l+1；elsedpij=max(dpi-lj,dpij-l);coutdpnmendl;return0;最长回文段#include#includeconstintmaxn=1010;charsmaxn;intdpmaxnmaxn;usingnamespacestd;intmain()gets(s);intlen=strlen(s),ans=1;memset(dp,0,sizeof(dp);for(inti=0;ilen;i+)dpii=l；if