动态规划试题（与动态规划精讲配套）.docVIP

目录 1 [0/1背包 ]bag01 3 2 [完全背包问题]bag 4 3 数字三角形问题triangle 5 4 最短路径path 6 5 矩阵取数游戏 8 6 守望者的逃离 10 7 资源分配问题resource 12 8 开心的金明happy 13 9 能量项链energy 15 10 金明的预算方案budget 17 11 采药medic 19 12 过河river 21 13 合唱队形chorus 23 14 乘积最大 product 25 15 拦截导弹missile 26 1 [0/1背包 ]bag01 一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。 W1，W2，...,Wn它们的价值分别为C1,C2,...,Cn2 [完全背包问题] 一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn, 每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多. 求旅行者能获得的最大总价值。 W1，W2，...,Wn它们的价值分别为C1,C2,...,Cn 3 数字三角形问题?????????????? 7 ????????????? 3 8 ???????????? 8 1 0 ??????????? 2 7 7 4 ????????? ? 5 5 2 6 5 示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数≤100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。输人数据：由文件输入数据，文件第一行是三角形的行数N。以后的N行分别是从最顶层到最底层的每一层中的数字。如输入： 57???????????3 8 ????????8 1 0 ????2 7 7 4 ????4 5 2 6 5 ??输出：304 最短路径 　 问题描述： 如图：求v1到v10的最短路径长度及最短路径。0 2 5 1 -1 -1 -1 -1 -1 -1-1 0 -1 -1 12 14 -1 -1 -1 -1-1 -1 0 -1 6 10 4 -1 -1 -1-1 -1 -1 0 13 12 11 -1 -1 -1-1 -1 -1 -1 0 -1 -1 3 9 -1-1 -1 -1 -1 -1 0 -1 6 5 -1-1 -1 -1 -1 -1 -1 0 -1 10 -1-1 -1 -1 -1 -1 -1 -1 0 -1 5-1 -1 -1 -1 -1 -1 -1 -1 0 2-1 -1 -1 -1 -1 -1 -1 -1 -1 0 【样例输出】 19 1 3 5 8 10 5 矩阵取数游戏 【问题描述】 帅帅经常更同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij据为非负整数。游戏规则如下： 1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有的元素； 2. 每次取走的各个元素只能是该元素所在行的行首或行尾； 3. 每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分 = 被取走的元素值*2i，其中i表示第i次取数（从1开始编号）； 4. 游戏结束总得分为m次取数得分之和。 帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。 【输入】 输入文件game.in包括n+1行； 第一行为两个用空格隔开的整数n和m。 第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开 【输出】 输出文件game.out仅包含1行，为一个整数，即输入矩阵取数后的最大的分。 【输入输出样例1】 game.in game.out 2 31 2 43 4 2 82 【输入输出样例1解释】 第1次：第一行取行首元素，第二行取行尾元素，本次的氛围1*21+2*21=6 第2次：两行均取行首元素，本次得分为2*22+3*22=20 第3次：得分为3*23+4*23=56。总得分为6+20+56=82 【输入输出样例2】 game.in game.out 1 44 5 0 5 122 【输入输出样例3】 game.in game.out 2 1096 56 54 46 86 12 23 88 80