动态规划 练习题

动态规划练习题23.（11分）请用动态规划逆序求解法求解下列问题：求出下图中从A到E的最短路线及长度。在图中标出每个点到终点的最短距离。24.（11分）一个旅行者从A点出发，经过B、C、D等处，到达E。各地间距离如图中所示。问该旅行者应选择哪一条路线，使从A到E的总路程最短？（可直接在图上标号，最后给定答案）24.一个旅行者从A点出发，经过B、C、D等处，到达E。各地间距离如图中所示。问该旅行者应选择哪一条路线，使从A到E的总路程最短？（可直接在图上标号，最后给定答案）（11分）6643125417433344423AB1B3C1B2C3D1C2D2E3动态规划练习题解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下：6643125417433344423AB1B3C1B2C3D1C2D2E36643125417433344423AB1B3C1B2C3D1C2D2E3034476117811动态规划练习题最佳策略为：A→B2→C1→D1→E或A→B3→C1→D1→E此时从A到E的总路程的最短距离都是1123.请用动态规划逆序求解法求解下列问题：各点标号依次为：A:8,B1：7，B2:6,B3:8,C1：5，C2：4，D1：3，D2：1，D3：5.25.某厂生产CBA,,三种产品，其所需劳动力、材料等有关数据见下表。要求：建立模型，并用单纯形法计算，确定获利最大的产品生产计划。消耗定额产品资源CBA可用单位劳动力材料6353454530产品利润（元/件）314动态规划练习题解：（1）设CBA,,各生产321,,xxx件。有32143minxxxzst.)3,2,1(,03054345536321321jxxxxxxxj（4分）列表计算1x2x3x4x5x4x45635105x3034[5]01jjzc314004x15[3]-101-13x653541051jjzc5351100541x5131031313x30115152jjzc0-205153（13分）获利最大的生产计划是CBA,,各生产5件、0件、3件，最大利润为273453z元。（15分）