《NOIP普及讲座4-动态规划2.ppt》由会员分享，可在线阅读，更多相关《NOIP普及讲座4-动态规划2.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、动态规划2经经典典例例题题讲讲解解【例题例题1 1】装箱问题（装箱问题（noi openjudge 8785noi openjudge 8785）问题描述：问题描述：有一个箱子容量为有一个箱子容量为V V（正整数，（正整数，0=v=200000=v=20000），同时有），同时有n n个物品（个物品（0 0 n=30n=30），每个物品有一个体积（正整数）。），每个物品有一个体积（正整数）。要求要求n n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。输入输入第一行是一个整数第一行是一个整数V V，表示箱子容量。，表示箱子容量。第二行
2、是一个整数第二行是一个整数n n，表示物品数。，表示物品数。接下来接下来n n行，每行一个正整数（不超过行，每行一个正整数（不超过1000010000），分别表示这），分别表示这n n个物品的各自个物品的各自体积。体积。输出输出一个整数，表示箱子剩余空间。一个整数，表示箱子剩余空间。经经典典例例题题讲讲解解样例输入样例输入24246 68 83 312127 79 97 7样例输出样例输出0 0。经经典典例例题题讲讲解解【问题分析问题分析】状态：状态：fi,jfi,j代表前代表前i i个物体装在个物体装在j j重的包里的最优解重的包里的最优解方程：方程：fi,j=max(fi-1,j,fi-1
3、,j-ai);fi,j=max(fi-1,j,fi-1,j-ai);【程序实现程序实现】经经典典例例题题讲讲解解【例题例题2 2】宝石手镯（宝石手镯（usacousaco）问题描述：问题描述：贝茜在珠宝店闲逛时，买到了一个中意的手镯。很自贝茜在珠宝店闲逛时，买到了一个中意的手镯。很自然地，她想从她收集的然地，她想从她收集的N(1=N=3,402)N(1=N=3,402)块宝石中块宝石中选出最好的那些镶在手镯上。对于第选出最好的那些镶在手镯上。对于第i i块宝石，它的重块宝石，它的重量为量为W_i(1=W_i=400)W_i(1=W_i=400)，并且贝茜知道它在镶上，并且贝茜知道它在镶上手镯后
4、能为自己增加的魅力值手镯后能为自己增加的魅力值D_i(1=D_i=100)D_i(1=D_i=100)。由于贝茜只能忍受重量不超过。由于贝茜只能忍受重量不超过M(1=M=M(1=M=12,880)12,880)的手镯，她可能无法把所有喜欢的宝石都镶上。的手镯，她可能无法把所有喜欢的宝石都镶上。于是贝茜找到了你，告诉了你她所有宝石的属性以及于是贝茜找到了你，告诉了你她所有宝石的属性以及她能忍受的重量，希望你能帮她计算一下，按照最合她能忍受的重量，希望你能帮她计算一下，按照最合理的方案镶嵌宝石的话，她的魅力值最多能增加多少。理的方案镶嵌宝石的话，她的魅力值最多能增加多少。经经典典例例题题讲讲解解【
5、输入格式】【输入格式】输入的第一行有两个整数输入的第一行有两个整数N(1=N=3,402)N(1=N=3,402)和和M(1=M(1=M=12,880)M=12,880)，接下来的，接下来的NN行每行两个整数，分别表示宝石行每行两个整数，分别表示宝石重量和魅力值。重量和魅力值。【输出格式】【输出格式】输出只包括一行，这一行只包含一个整数，表示魅力值最多输出只包括一行，这一行只包含一个整数，表示魅力值最多能增加多少。能增加多少。【样例输入】【样例输入】3 703 7071 10071 10069 169 11 21 2【样例输出】【样例输出】3 3经经典典例例题题讲讲解解【问题分析问题分析】状态
6、：状态：fi,jfi,j代表前代表前i i个宝石戴在个宝石戴在j j重的手上获得的最大魅力重的手上获得的最大魅力值值方程：方程：fi,j=max(fi-1,j,fi-1,j-ai)+bi;fi,j=max(fi-1,j,fi-1,j-ai)+bi;【程序实现程序实现】经经典典例例题题讲讲解解【例题例题3 3】奶牛打工奶牛打工问题描述：问题描述：奶牛奶牛BassieBassie去去DQDQ打工，遇到一个客人给了一张好大面打工，遇到一个客人给了一张好大面值的钞票，于是值的钞票，于是BassieBassie不得不为了给这位顾客找零而面不得不为了给这位顾客找零而面对这样一个问题：现在店里一共有对这样一
7、个问题：现在店里一共有n n种硬币，对这些不种硬币，对这些不同种的硬币进行编号，编号为同种的硬币进行编号，编号为i i的硬币面值为的硬币面值为ai ai。因。因为奶牛的手指头是有限的，因此他只能向你求助啦。为奶牛的手指头是有限的，因此他只能向你求助啦。(已知总需找零数为已知总需找零数为total)(1=total=1000,1=n=1000,1=ai=3total)(1=total=1000,1=n=1000,1=ai=300)00)求一共有多少种解决方案？求一共有多少种解决方案？经经典典例例题题讲讲解解【输入格式】【输入格式】第一行为硬币总值第一行为硬币总值totaltotal和硬币种类数和
8、硬币种类数n n。以下以下n n行为数值行为数值aiai，i=1,2,3.ni=1,2,3.n【输出格式】【输出格式】一行，解决方案数一行，解决方案数【样例输入】【样例输入】83 583 55050252510105 51 1【样例输出】【样例输出】159159经经典典例例题题讲讲解解0 x 50 0 x 25 0 x 10 0 x 5 83 x 1 0 x 50 0 x 25 0 x 10 0 x 5 83 x 1 0 x 50 0 x 25 0 x 10 1 x 5 78 x 1 0 x 50 0 x 25 0 x 10 1 x 5 78 x 1 0 x 50 0 x 25 0 x 10
9、2 x 5 73 x 1 0 x 50 0 x 25 0 x 10 2 x 5 73 x 1 0 x 50 0 x 25 0 x 10 3 x 5 68 x 1 0 x 50 0 x 25 0 x 10 3 x 5 68 x 1 0 x 50 0 x 25 0 x 10 4 x 5 63 x 1 0 x 50 0 x 25 0 x 10 4 x 5 63 x 1 0 x 50 0 x 25 0 x 10 5 x 5 58 x 1 0 x 50 0 x 25 0 x 10 5 x 5 58 x 1 0 x 50 0 x 25 0 x 10 6 x 5 53 x 1 0 x 50 0 x 25 0
10、 x 10 6 x 5 53 x 1 0 x 50 0 x 25 0 x 10 7 x 5 48 x 1 0 x 50 0 x 25 0 x 10 7 x 5 48 x 1 0 x 50 0 x 25 0 x 10 8 x 5 43 x 1 0 x 50 0 x 25 0 x 10 8 x 5 43 x 1 0 x 50 0 x 25 0 x 10 9 x 5 38 x 1 0 x 50 0 x 25 0 x 10 9 x 5 38 x 1 0 x 50 0 x 25 0 x 10 10 x 5 33 x 1 0 x 50 0 x 25 0 x 10 10 x 5 33 x 1 0 x 50
11、0 x 25 0 x 10 11 x 5 28 x 1 0 x 50 0 x 25 0 x 10 11 x 5 28 x 1 0 x 50 0 x 25 0 x 10 12 x 5 23 x 1 0 x 50 0 x 25 0 x 10 12 x 5 23 x 1 0 x 50 0 x 25 0 x 10 13 x 5 18 x 1 0 x 50 0 x 25 0 x 10 13 x 5 18 x 1 0 x 50 0 x 25 0 x 10 14 x 5 13 x 10 x 50 0 x 25 0 x 10 14 x 5 13 x 1 【样例说明样例说明】经经典典例例题题讲讲解解【问题分析问
12、题分析】状态：状态：fifi代表面值为代表面值为i i的钱的换钱方案数的钱的换钱方案数方程：方程：fi=sum(fi-ak)1=k=n;fi=sum(fi-ak)1=k=n;【程序实现程序实现】经经典典例例题题讲讲解解【例题例题4 4】滑雪滑雪问题描述：问题描述：Michael Michael喜欢滑雪。这并不奇怪，喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。因为滑雪的确很刺激。可是为了获得速度，滑的区域必需向下倾斜，而且当可是为了获得速度，滑的区域必需向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来你滑到坡底，你不得不再次走上坡或者等待升降机来载你。载你。MichaelMichae
13、l想知道在一个区域中最长的滑坡。区域想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。由一个二维数组给出。数组的每个数字代表点的高度。经经典典例例题题讲讲解解下面是一个例子下面是一个例子 1 2 3 4 5 1 2 3 4 516 17 18 19 616 17 18 19 615 24 25 20 715 24 25 20 714 23 22 21 814 23 22 21 813 12 11 10 913 12 11 10 9一个人可以从某个点不滑向上下左右相邻四个点之一，当且仅当高度减一个人可以从某个点不滑向上下左右相邻四个点之一，当且仅当高度减小，在上面
14、的例子中，一条可行的不滑坡为小，在上面的例子中，一条可行的不滑坡为2424171716161 1（从（从2424开始，开始，在在1 1结束）。当然结束）。当然2525242423233 32 21 1更长。事实上，这是最长更长。事实上，这是最长的一条。的一条。【输入格式】【输入格式】第第1 1行为表示区域的二维数组的行数行为表示区域的二维数组的行数R R和列数和列数C(1RC(1R，C100)C100)。下面是。下面是R R行，每行有行，每行有C C个数，代表高度。个数，代表高度。【输出格式】【输出格式】区域中最长滑坡的长度区域中最长滑坡的长度经经典典例例题题讲讲解解【样例输入】【样例输入】5
15、 55 5123 4 5123 4 516 17 18 19 616 17 18 19 615 24 25 20 715 24 25 20 714 23 22 21 814 23 22 21 813 12 11 10 913 12 11 10 9【样例输出】【样例输出】2525 经经典典例例题题讲讲解解【问题分析问题分析】一个类似最长下降序列，穷举每个最低点。用记忆化搜索写一个类似最长下降序列，穷举每个最低点。用记忆化搜索写一个类似最长下降序列，穷举每个最低点。用记忆化搜索写一个类似最长下降序列，穷举每个最低点。用记忆化搜索写比较方便。比较方便。比较方便。比较方便。【程序实现程序实现】经经典典
16、例例题题讲讲解解【例题例题5 5】最小代价子母树最小代价子母树问题描述：问题描述：有有n n堆沙子排成一排，每堆沙子有一个数量，例如：堆沙子排成一排，每堆沙子有一个数量，例如：13 7 8 16 21 4 1813 7 8 16 21 4 18。任意。任意2 2堆相邻的沙子可以进行合并，将两堆沙子合并为一堆时，两堆沙堆相邻的沙子可以进行合并，将两堆沙子合并为一堆时，两堆沙子数量的和称为合并这两堆沙子的代价。经过不断的归并，最后将这些子数量的和称为合并这两堆沙子的代价。经过不断的归并，最后将这些沙子归为一堆，而全部归并代价的和称为总代价。例如上列数，其中沙子归为一堆，而全部归并代价的和称为总代价
17、。例如上列数，其中2 2种种归并方案的代价为：归并方案的代价为：第第1 1种的总代价为种的总代价为 20+24+25+44+69+87=26720+24+25+44+69+87=267第第2 2种的总代价为种的总代价为 15+37+22+28+59+87=24815+37+22+28+59+87=248由此可见，不同的归并过程得到的总代价是不一样的。由此可见，不同的归并过程得到的总代价是不一样的。问题：当问题：当n n个数给出后，找出一种合理的归并方法，使得总代价最小。个数给出后，找出一种合理的归并方法，使得总代价最小。经经典典例例题题讲讲解解【问题分析问题分析】状态：状态：状态：状态：fi,
18、j fi,j fi,j fi,j代表从代表从代表从代表从i i i i堆合并到堆合并到堆合并到堆合并到j j j j堆所需要的最小代价堆所需要的最小代价堆所需要的最小代价堆所需要的最小代价 方程方程方程方程 fi,j=min(fi,k+fk+1,j)+sj-si-1;fi,j=min(fi,k+fk+1,j)+sj-si-1;fi,j=min(fi,k+fk+1,j)+sj-si-1;fi,j=min(fi,k+fk+1,j)+sj-si-1;i=k=j i=k=j i=k=j i=k=j动态规划递归实现动态规划递归实现-记忆化搜索记忆化搜索课课后后练练习习推推荐荐课堂讨论及课后习题课堂讨论及课后习题习题习题1 1、合并果子合并果子习题习题2 2、能量项链、能量项链习题习题3 3、传纸条、传纸条习题习题4 4、宝箱、宝箱