谁有动态规划的题目（编程的进）

编程 动态规划~

动态规划有很多种，但基本思想是一样的。
就是对于一个问题，如果它的解包含了它的子问题的解。（即要解出这个问题就必须解出它的子问题）。那么就可以根据它与子问题的关系得到一个状态转移方程。
但动态规划的意义在于，如果多个子问题都包含相同的“子子问题”，那么这个“子子问题”就会被重新计算很多次，用动态规划，我们把这个“子子问题”的解求出并储存下来，再次遇到的时候就不必再次计算。所以可以省下许多时间。
经典的动态规划题目有：0-1背包、装箱问题等。
这些问题的详细解答分析我就不赘述了，网上有许多资料，LZ可以搜索一下。

背景：某电力系统拟建三座大型水电站，通过设计负荷水平年和枯水年的电力电量平衡计算，确定水电站群的总装机容量为280万kw；根据投资估算和经济分析，各电站可选择的装机容量变化范围及部分装机容量相应的费用列表如下：
费用
(亿元)
序号装机容量(万kw)
5060708090100110120130
电站11.6001.6101.6221.6351.6501.670
电站21.8001.8141.8321.8521.8751.900
电站31.7001.7201.7431.7701.8001.835
问题：如何合理地分配水电站群内各电站的装机容量，使系统的总费用为最小？

1． 最长公共子序列 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=<x1, x2,…, xm>，则另一序列Z=<z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 <i1, i2,…, ik>，使得对于所有j=1,2,…,k有 2． 计算矩阵连乘积 在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，则其乘积C=AB是一个p×r的矩阵。由该公式知计算C=AB总共需要pqr次的数乘。其标准计算公式为： 3． 凸多边形的最优三角剖分 多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。一个简单多边形将平面分为3个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。 通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P=<v0 ,v1 ,… ,vn-1>表示具有n条边v0v1，v1v2，… ,vn-1vn的一个凸多边形，其中，约定v0=vn 。 若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。弦 将多边形分割成凸的两个子多边形<vi ,vi+1 ,… ,vj>和<vj ,vj+1 ,… ,vi>。多边形的三角剖分是一个将多边形分割成互不重迭的三角形的弦的集合T。如图是一个凸多边形的两个不同的三角剖分。 凸多边形最优三角剖分的问题是：给定一个凸多边形P=<v0 ,v1 ,… ,vn-1>以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。 可以定义三角形上各种各样的权函数W。例如：定义ω(△vivjvk)=|vivj|+|vivk|+|vkvj|，其中，|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。(注意：解决此问题的算法必须适用于任意的权函数) 4． 防卫导弹 一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一： a)它是该次测试中第一个被防卫导弹截击的导弹； b)它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。 输入数据：第一行是一个整数n，以后的n各有一个整数表示导弹的高度。 输出数据：截击导弹的最大数目。 5． 石子合并 在一个圆形操场的四周摆放着n堆石子(n<= 100)，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序，由文件读入堆栈数n及每堆栈的石子数(<=20)。 选择一种合并石子的方案,使得做n－1次合并,得分的总和最小； 输入数据： 第一行为石子堆数n； 第二行为每堆的石子数,每两个数之间用一个空格分隔。 输出数据： 从第一至第n行为得分最小的合并方案。第n+1行是空行.从第n+2行到第2n+1行是得分最大合并方案。每种合并方案用n行表示，其中第i行(1<=i<=n)表示第i次合并前各堆的石子数(依顺时针次序输出，哪一堆先输出均可)。要求将待合并的两堆石子数以相应的负数表示。 Sample Input 4 4 5 9 4 Sample Output －4 5 9 －4 －8 －5 9 －13 －9 22 4 －5 －9 4 4－14 －4 －4 －18 22 6． 最小代价子母树 设有一排数，共n个，例如：22 14 7 13 26 15 11。任意2个相邻的数可以进行归并，归并的代价为该两个数的和,经过不断的归并，最后归为一堆，而全部归并代价的和称为总代价，给出一种归并算法，使总代价为最小。 输入、输出数据格式与“石子合并”相同。 Sample Input 4 12 5 16 4 Sample Output －12 －5 16 4 17 －16 －4 －17 －20 37 7． 商店购物 某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）；一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如：3朵花的价格不是6而是5 ICU；2个花瓶加1朵花是10 ICU不是12 ICU。 编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为：3朵花和2个花瓶。那么顾客应付款为14 ICU因为： 1朵花加2个花瓶优惠价：10 ICU 2朵花正常价：4 ICU 输入数据：第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF ER．TXT）。 两个文件中都只用整数。 第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。 C 代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。 第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤9 9），表示共有S 种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤ P≤9999）代表此商品组合的优惠价。当然， 优惠价要低于该组合中商品正常价之总和。 输出数据：在输出文件OUTPUT．TXT中写 一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款。 8． 旅游预算 一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。旅游预算有如下规则： 若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加油时，司机要花费2元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分（1元=100分）。编写程序估计实际行驶在某路线所需的最小费用。 输入数据：从当前目录下的文本文件“route.dat”读入数据。按以下格式输入若干旅行路线的情况： 第一行为起点到终点的距离（实数） 第二行为三个实数，后跟一个整数，每两个数据间用一个空格隔开。其中第一个数为汽车油箱的容量（升），第二个数是每升汽油行驶的公里数，第三个数是在起点加满油箱的费用，第四个数是加油站的数量。（〈=50）。接下去的每行包括两个实数，每个数据之间用一个空格分隔，其中第一个数是该加油站离起点的距离，第二个数是该加油站每升汽油的价格（元/升）。加油站按它们与起点的距离升序排列。所有的输入都有一定有解。 输出数据：答案输出到当前目录下的文本文件“route.out”中。该文件包括两行。第一行为一个实数和一个整数，实数为旅行的最小费用，以元为单位，精确到分，整数表示途中加油的站的N。第二行是N个整数，表示N个加油的站的编号，按升序排列。数据间用一个空格分隔，此外没有多余的空格。 Sample Input 516.3 38.09 1 15.7 22.1 20.87 3 2 125.4 1.259 297.9 1.129 345.2 0.999 Sample Output 38.09 1 2

---

海原县17369914945： 谁有动态规划的题目(编程的进) - ？
申阁单唾： 1. 最长公共子序列 一个给定序列的子序列是在该序列中删去若干元素后得到的序列.确切地说,若给定序列X=,则另一序列Z=是X的子序列是指存在一个严格递增的下标序列 ,使得对于所有j=1,2,…,k有 2. 计算矩阵连乘积 在科学计算中经常要...

海原县17369914945： 一道C语言动态规划题 - ？
申阁单唾： #include<iostream>#include<cstring> using namespace std; int a[101][101],f[101][101],n,T; int maxi(int a,int b,int c) { if(a<b) a=b; if(a<c) a=c; return a; } int main() { cin>>T; for(;T;T--) { cin>>n; memset(a,0,sizeof(a)); memset(f,0,sizeof(f)); for(int i=1;i<...

海原县17369914945： C语言 砝码称重问题,高手进~~~~？
申阁单唾： 这是一道简单的动态规划题目. 它的做法是: 先只用第一种砝码,看它能构成多少种重量, 再用前2种,看能构成多少种重量(不包括上面的那个) 接着前3种.. 前4钟... 前5种... 前6种... 所以有第一个for 循环 for ( i = 0; i &lt; 6; i++ ) 第2个for循环...

海原县17369914945： 关于c++动态规划的问题 - ？
申阁单唾： 题目中较明显的条件:每项任务,只有在印刷车间完成后,才能在装订车间加工.第一个任务完成前,装订车间不开工很明显,安排印刷车间的任务,要将印刷车间工作天数比装订车间工作天数小的安排...

海原县17369914945： 一道PASCAL语言编程题？
申阁单唾： 这是一道简单的动态规划题目额.... 代码如下: var n:1..1000; a,f:array[0..1000,0..1000]of longint; function huajian(v:longint):longint; var t:longint; begint:=v;while t mod 2=0 dot:=t div 2;while t mod 5=0 dot:=t div 5;exit(v div t); end; ...

海原县17369914945： c语言动态规划的一个问题 - ？
申阁单唾： 动态规划关键是找到问题中的子问题,写出状态方程. 这个问题的子问题可以定义为前n件物品,总费用为v的最大价值总和. 先考虑第n件物品,如果c[n]f(n,v)=max{f(n-1,v-c[n]*i)+w[n]*i};i根据物品费用和对应的总费用确定取值,即小于对应的总费用时可取0,1,否则为0. 很明显最简单的是从前1件物品中选取,这个就是最后用递归程序编写程序时候的出口. 算法思想就是上面所写的.程序的精华在于思想,仅供你编程参考.

海原县17369914945： 用动态规划法解 0/1背包问题 要求用c语言编写程序原代码. - ？
申阁单唾： 1.动态规划 #include<stdio.h>#include<stdlib.h>#include<time.h> #define N 100 //货物的种类#define M 10 //货物的质量(千克) typedef struct good { int no; //第几个物品 int w; //质量 int p; //可获利 int flag; float pw; //获得的最高利润 }Good; ...

海原县17369914945： 高分求动态规划题目!!! - ？
申阁单唾： 这是我们计算机系算法设计课的实验课程,下面是动态规划内容:实验四:动态规划实验目的:理解动态规划的基本思想,理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质.熟练掌握典型的动态规划问题.掌握动态规划思...

海原县17369914945： 求教:如何用Matlab编写这个动态规划的程序 - ？
申阁单唾： 建立数学模型设xi=1表示Ai被选中,xi=0表示Ai没被选中.则数学模型是:max 1500x1+2000x2+1300x3+2300x4+2800x5s.t. x1+x2=1 x4+x5=1 x1+x4

海原县17369914945： ACM动态规划题 - ？
申阁单唾： 这是动态规划很经典的问题之一... 还有,想纠正LZ一个说法,“用C做,怎么做?不行的话C++也行啊”,感觉LZ觉得C++更厉害一些哈...其实不然,像LZ说的这种问题是算法问题,不基于某种编程语言的... 正题: 假设我们的实...