用于生成动态时间频率分布CEM目标的一种物理方法

毕业论文（设计）

英文翻译

姓名郭加炎

学号 0811121213 所在学院理学院

专业班级 2008级信科2班

指导教师徐国旺

日期 2012年3月30 日

A PHYSICAL APPROACH TO GENERATING TIME FREQUENCY DISTRIBUTIONS OF DYNAMIC CEM TARGETS

M. Carr and J. L. Volakis

Radiation Laboratory, Electrical Engineering and Computer Science University of Michigan, Ann Arbor, MI 48109-2122 Received 29 April 2002

ABSTRACT: Generating accurate, high-resolution time-frequency distributions (TFD) is a critical aspect of dynamic radar scattering analysis. Well-formed TFD’s can be used for target identification, target acquisition in high-noise environments, or extending the range of radar systems. In this paper, we diverge from traditional methods employing complex signal-processing methods and propose a simple approach for constructing the TFD for computational electromagnetic (CEM) targets based on the physics of the problem. The proposed method allows for an arbitrarily high resolution at any single look angle. Several examples are presented to validate the method. ? 2002 Wiley Periodicals, Inc. Microwave Opt Technol Lett 35: 186–189, 2002; Published online in Wiley InterScience (www.interscience.wiley . com). DOI 10.1002/mop. 10552

Key words: time-frequency; radar; computational electromagnetics; moment method; Doppler

1. INTRODUCTION

The Fourier Transform has long been an important tool for providing a measure of the frequencies contained within a signal. Time-frequency distributions (TFD) extend the functionality of the Fourier Transform by computing the localized frequency content at a particular time within the signal. Thus, one can obtain information about the dynamic frequency-domain behavior of a signal over time. Within the realm of radar scattering, one can interpret the TFD physically as a representation of the dynamically changing Doppler frequency shifts caused by moving targets or targets with moving components. TFDs can then be used for a variety of applications, such as clutter reduction and moving target detection using airborne radars [1].

As an example, consider the ?z

-directed dipole source spinning about the origin as shown in Figure 1(a), where we wish to measure the far field radiated in the negative ?x

-direction [2]. From Doppler theory, we know that the frequency measured at the observation point will shift upwards when the source is approaching the observer. As the source recedes, the observed frequency shifts downward with the Doppler shift frequency given by

?2

D V x

f λ

?=- (1)

Since ?2()V l t πφ=, where ?φ is the usual cylindrical unit vector and t denotes time, the Doppler frequency as time increases can then be expressed as

Figure 1 (a) Z-directed dipole source spinning about the origin. (b) TFD representation of the radiated field in the negative x-direction

??()4sin()

4.D t x

l t f l

φππλλ

?=-=

(2)

A TFD of this situation would then look as that shown in Figure 1(b).

In practice, to generate Figure 1(b) we use the scattered signal from the rotating object. The simplest and most well known method for genera ting a given signal’s TFD is the windowed Fourier transform known as the spectrogram [3]. Basically, to find the signal component associated with frequency ωat a certain time t , the received signal s (t ) is multiplied by a windowing function h (t ) centered at time t . The result is then transformed to frequency domain to yield '1()(')(')'.

j w t

t S e

s t h t t d t ω-=

- (3)

Here is the spectrum of the windowed signal at time t. From Eq. (3), it is evident

that a compact windowing function h will increase localization in time domain but lower resolution in frequency domain. Conversely, a wide windowing function will lead to high frequency resolution and low time localization. This uncertainty principle, present in all signal-processing TFD approaches, ultimately limits our overall resolution and forces us to settle for a compromise between time and frequency resolution. It is, of course, desirable to remove this restriction and allow for an arbitrary resolution in both domains.

In proceeding to remove such a restriction, we note that Eq. (3) neglects

information from the individual currents J , which are the source of the scattered field (see Fig. 2(a)). In this paper we present a physics-based approach called the Direct TFD (DTFD) for computing each column of the TFD from knowledge of the individual currents upon the geometry and its velocity at a single look angle. In this manner, the intermediate calculation of the scattered field is bypassed (see Fig. 2(b)), thus avoiding the uncertainty principle and allowing for much higher resolution. Further, DTFD has O(N) complexity and requires little memory. 2. DIRECT TFD FORMULATION

Computation of the scattered fields (as required for signal-processing methods) requires lumping all induced currents into a single field value, therefore forfeiting much detail about the target’s electromagnetic characteristics. In the DTFD method, we instead use information about the geometry’s instantaneous velocity to localize (in frequency) the contribution from each current source. From Doppler theory, we know that the velocity of the geometry upon which the source resides will determine the apparent frequency shift as seen by a stationary observer. We can also account for any frequency shift of the induced curren ts due to the geometry’s motion through the incident field by expressing the localized current as ??()()'(,)()[]s o d d r

v r r

v r J r f J r f δλ

λ

=--

(4)

where

δ

is the Dirac delta function, λis the carrier wavelength, d f is the Doppler

frequency shift, ?o r

and ?s r are unit vectors in the direction of the observer and source, respectively, and v (r ) is the velocity of the geometry at point r . For the monostatic

case, ??o s r

r = and thus Eq. (4) simplifies to ?()'(,)()[2

]o d d r

v r J r f J r f δλ

=-

(5)

By modifying the currents as shown, we restrict the radiation integral to include only those currents which appear at a given Doppler shift d f , and thus extend our usual computation of the

Figure 2 (a) Standard signal-processing methods such as the spectrogram. (b) The proposed Direct TFD (DTFD) method

Figure 3 A 5.00.3λλ?perfectly electrically conducting plate scattered field from time-domain to frequency-domain. We therefore construct a subset of the original currents J as

22

()'(,)d d

d f

f f f f f J

r J r f df

?+??-

=

?

(6)

The resolution in the frequency domain is therefore based solely on the choice of f ?. As usual, the scattered field (for the chosen range of Doppler shift) is found by

employing ()d

f

f

J r ? in the radiation integral. Since the currents upon the geometry can be calculated for any given time, we note that unlike traditional signal processing

methods, the user’s arbitrary choice of time and frequency allows for any desirable resolution within the DTFD. 3. EXAMPLE Geometry

As an example, we present the TFD generated by a 0.3 5.0λλ?metallic plate rotating in the xy plane about the center at one end (see Fig. 3). The incident field is a plane wave in the xy plane and traveling along the positive x-axis.

To compute the DTFD, currents are first evaluated via the moment method at each look angle. The currents are then modified using Eqs. (5) and (6). Since the plate rotates about the origin, the velocity of the geometry at a given point r is

?()2v r r πφ

= (7) where v is then substituted in (5). For reference, the monostatic RCS of the geometry

(as it moves through a rotation of 360°) is shown in Figure 4(a). Note the sharp specular response at 90° and 270° and the broader traveling wave responses at about 20°, 160°, 200°, and 340°. The corresponding discrete Fourier transform of

the scattered field is given in Figure 4(b), showing all frequencies present throughout the plate’s entire rotation.

From (7) and Figure 4(b), we observe that the maximum Doppler frequency is ±63 Hz, occuring when the blade is at 90° and 270°, respectively. Thus, a well-formed TFD should give us some physical insight into these behaviors.

Figure 5 shows the TFD of the plate using the spectrogram method

described

above. From this image, we can clearly see the large specular and traveling wave returns but the physics of the behavior are unclear, largely due to the ―smearing‖ in both timeand frequency-domain resulting from the uncertainty principle. Overall, the image doesn’t show much more detail th an the RCS plot of Figure 4(a).

Figure 6 shows the TFD of the plate using the proposed DTFD method with

max min ()/3000.42f f f ?=-=

Hz. In this graph, one can clearly see that the large

traveling-wave returns are caused by 10 discrete scattering centers distributed along the outer portions of the blade. As one might expect, these ten discrete scattering centers correspond to the ten λ/2 sections (10/25λλ= ) of

Figure 4 RCS of PEC plate in (a) time-domain. (b) Frequency-domain the blade. Another curious feature is the apparent absence of the large specular return generated by the spectrogram in Figure 5. However, it is not difficult to conclude that the specular returns are

Figure 5 TFD of a spinning 5.0λmetallic plate generated by the spectrogram method [Color figure can be viewed in the online issue, which is available at https://www.wendangku.net/doc/6318018433.html,]

Figure 6 Direct TFD of a spinning 5.0λmetallic plate [Color figure can be viewed in the online issue, which is available at www.interscience. https://www.wendangku.net/doc/6318018433.html,] created by the in-phase summation of many relatively small current elements located along the entire leading-edge of the blade—thus, the energy of the specular return is spread evenly along the entire blade and therefore appears at all Doppler frequencies. The spectrogram result suggests, incorrectly, that the specular return is caused largely by currents located at the center of the blade. Obviously this is not true and is a direct result of the uncertainty principle.

4. CONCLUSION

We presented the new Direct TFD method for generating TFD graphs with arbitrary resolution using only the computed currents and knowledge of the velocity of the geometry at each time step.The TFD of a spinning metallic plate was computed to demonstrate the much higher resolution of the proposed approach. REFERENCES

1. R. Klemm, Space-time adaptive processing principles and applications, IEE, London, 1998.

2. C.J. McCormack, V.V. Liepa, and W.J. Williams, Applying timefrequency techniques to noise corrupted radar signals, IEEE Radar Conf Proc (1996), 345–350.

3. L. Cohen, Time-frequency distributions—A review, Proc IEEE 7 (1989), 941–981.

4. D.A. Dunavant, High degree efficient symmetrical gaussian quadrature rules for the triangle, Int J Num Meth Eng (1985), 1129–1148.

5. M. Carr, J.L. Volakis, and D.C. Ross, New time-frequency techniques for identification and extraction of scattering mechanisms, IEEE APS Int Symp (1998), 346–349.

? 2002 Wiley Periodicals, Inc.

用于生成动态时间频率分布CEM目标的一种物理方法

M. Carr and J. L. Volakis

辐射实验室，电气工程和计算机科学

美国密歇根大学，安阿伯，MI48109-2122

2002年4月29日

摘要：生成准确，高分辨率的动态时频分布目标（TFD）是一个雷达散射分析的重要方面。正确地TFD在高噪声环境中或扩大的雷达探测范围系统中可用于目标识别，目标探测。在本文中，我们避免了采用传统的复杂的信号处理方法，为在计算电磁（CEM）目标的物理问题的基础上提出了一种简单的TFD方法。该方法可以从任何一个角度提供任意高的分辨率。举几个例子来验证该方法。?2002威利公司期刊微波学报35期：186-189，2002年，已在约翰威利网上公布（https://www.wendangku.net/doc/6318018433.html,）。数字对象标识10.1002/mop.10552。

关键词：时频；雷达；电磁计算学；矩量法；多普勒效应。

1. 引言

傅里叶变换一直是提供衡量一个信号包含频率的重要工具。时频分布（TFD）的功能扩展了傅里叶变换在计算局部频率时是在特定时间内的信号。因此，随着时间的推移人们可以获取频域动态信号变化的有关信息。在雷达散射区域内，物理上人们可以解释TFD为表示由动态目标或动态元件组成的目标所造成的动态变化的多普勒频移。然后，TFD可以用于各种各样的应用，如减少杂波和机载雷达的动态目标检测[1]。

例如，如图1（a）所示，考虑原点处的Z向旋转偶极子，我们希望测量在x 轴负方向远场区的辐射[2]。从多普勒理论考虑，我们知道，当信号源靠近观测者时，在观测点测量的频率将会增大。作为信号源远离观测者时，观测到的频率变小，多普勒效应的频率是

由于，通常表示圆柱体的单位向量，t表示时间，然后随着时间的变化多普勒频率可以表示为

图1（a）原点处的Z向旋转偶极子。（b）表示辐射场在x轴负方向的TFD。

再看看，如图1（B）的这种情况的TFD。

在实践中，我们使用分散的信号从旋转对象中产生图1（b）。已知最简单和最有名的产生一个给定信号的TFD的方法是傅立叶窗频谱变换[3]。基本上，在一定的时间t内找到相关频率ω的信号分量，收到的信号s(t’)乘以一个以时间t中心的窗函数h(t’)。然后将结果转换到频域产生

这里St(ω)是在时间t内窗信号的频谱。从式(3)易知，在时域内窗函数h将显得更加紧凑，但载频域内分辨率较低。相反，一个广泛的窗函数将导致高频率分辨率和低的时间定位。由不确定性原理，目前TFD的所有的信号处理方法，最终限制了我们的整体解决，并迫使我们在解决时间和频率分辨率之间妥协。当然，最好是消除此限制，并允许得到在这两个领域的任意分辨率。

从消除此限制出发，我们注意到，式(3)，忽视信息散射场源的个别电流J（见图2（a）项）。在本文中，我们提出了一个基于物理的方法称为直接TFD（DTFD），为从个人的知识出发，在一个单一的外观角度，计算每个TFD的列电流的几何形状和它的速度。

在这种方式下，绕过分散的中间计算过程（参见图2（b）条），从而避免不确定性的原则，允许了更高的分辨率。此外，DTFD降低复杂度O（N）和减少的内存的消耗。

2. 直接TFD的制定

计算散射场（所需的信号处理方法）的要求是所有的感应电流组成一个单一的字段值，因此忽略很多目标的电磁特性细节。DTFD方法，替代了采用几何的瞬时速度信息，导致的每个电流源（在频率方面）的综合影响。从多普勒理论，我们知道，几何速度源驻留将使得明视在频率转变为观察者可观测到的固定频率。我们也可以解释为由于几何上的任何感应电流的频移通过入射场的议案，局部电流可表示为

这里的是狄拉克函数，是载波波长，是多普勒频移，和观察者和源的方向上的单位向量，分别与v(r)是在r点的几何速度。对于单站的情况下

，因而式（4）可简化为

我们通过修改如下所示的电流，限制辐射部分只包括那些出现在一个给定多

普勒频移下的电流，从而扩展了我们的一贯计算

图2（a）是标准的频谱信号处理方法。图（b）是提出的直接TFD（DTFD）方法。

图3是一个从时域到频域的5.0λ33.0λ完全导电板散射场，因此，我们构建原电流J的一个子集为

因此，仅仅根据在频域的分辨率可选择Δf。像往常一样，通过在整体的辐射中

使用发现了散射场（在可选择的多普勒频移范围内）。我们注意到，不同于传统的信号处理方法，因为根据几何学电流的计算，对于任何给定的时间内，用户在允许DTFD的范围内可以任意的选择时间和频率，从而选择任何可取的方案。

3. 示例

几何

例如，我们提出了一个在xy平面上以0.3λ35.0λ金属板一端为中心旋转的TFD算（见图3）。入射场是在xy平面的沿正x轴的平面波。

计算DTFD，首先通过矩量法从每一个角度来评估电流。然后修改电流使用式（5）和（6）。由于板绕源点旋转，在给定的点r几何的速度为

其中V用（5）式替代。参考如图4（a）所示，是单站几何体的RCS（随着它做360°旋转）。需要注意在90°和270°时的垂直反射现象，和大约在20°，160°，200°和340°时存在的更广泛的行波现象。在图4（b）中相应的离散傅里叶变换散射场中，显示了整个板的全部旋转过程中所有出现的频率。

从式（7）和图4（b）中，我们观察到当金属板在90°和270°时，出现最大的多普勒频率分别是±63赫兹，。因此，这些现象应该给我们一些非常地有关TFD的物理洞察力。

图5显示了使用上面介绍的方法的TFD频谱板。从这个图片，我们可以清楚地看到强烈的镜面反射和行波的放射，但其物理现象的原因目前尚不清楚，这主要是由于时域和频域的不确定性原理产生的“拖尾效应”。总而言之，图4（a）没有显示过多的有关RCS图像的细节。

图6显示了该金属板使用DTFD方法的TFD

在这个图中，人们可以清楚地看到，沿着金属板边缘外层部分分布的10个离散散射中心有大量的行波反射。正如人们所预料的，这十个离散散射中心对应于102λ/2（102λ/2 = 5λ）的截面。

图4金属板光电管的RCS，（a）在时域，（b）在频域。另一种奇怪的特征是在图5的频谱图中明显的缺乏大量地镜面反射。然而，不难得出这样的镜面反射结论

图5是一个 5.0λ旋转金属板使用TFD方法产生的频谱图【在https://www.wendangku.net/doc/6318018433.html,网上可以访问该彩色图片】。

图6是整个5.0λ旋转金属板尖端边缘的许多相对较小的同步电流的直接TFD 【在https://www.wendangku.net/doc/6318018433.html,网上可以访问该彩色图片】。从而，镜面反射

的能量均匀地分布在整个金属板边缘，因此也会出现在所有的多普勒频率。光谱结果表明，镜面反射主要是由于位于金属板边缘中心电流引起的理论是不正确的。这是不确定性原理的直接结果，它的不正确性是显然的。

4. 结论

我们提出了新的直接TFD的方法，只用计算电流和在每个时间步长的几何速度，就能生成任意分辨率的TFD图形。一个旋转金属板的TFD计算证明该方法可得到的分辨率更高。

参考

1. 克莱姆《时空自适应处理原理及应用》，电气工程师学会，伦敦，1998.

2. C.J. McCormack, V.V. Liepa,和W.J. Williams《时频分析技术在噪声污染雷

达信号中的应用》，雷达信号处理程序（1996），345－350。

3. L. Cohen《时频分布评论》电气与电子工程师协会程序（1989），941—981。

4. D.A. Dunavant《高度有效地对称三角高斯积分规则》，国际冰毒工程（1985），

1129—1148.

5. M. Carr, J.L. Volakis和D.C. Ross《新的时频散射机制的识别和提取技术》，

电气与电子工程师协会，美国物理学会，国际专题学术讨论会（1998），346—349。

?2002威利公司期刊。

动态规划例题

例1：机器负荷分配问题 某公司新购进1000台机床，每台机床都可在高、低两种不同的负荷下进行生产，设在高负荷下生产的产量函数为g(x )=10x （单位：百件），其中x 为投入生产的机床数量，年完好率为a =0.7；在低负荷下生产的产量函数为h(y)=6y （单位：百件），其中y 为投人生产的机床数量，年完好率为b=0.9。计划连续使用5年，试问每年如何安排机床在高、低负荷下的生产计划，使在五年内生产的产品总产量达到最高。 例2：某企业通过市场调查，估计今后四个时期市场对某种产品的需要量如下表： 时期(k) 1 2 3 4 需要量(d k ) 2（单位） 3 2 4 假定不论在任何时期，生产每批产品的固定成本费为3(千元)，若不生产，则为零；生产单位产品成本费为1(千元)；每个时期生产能力所允许的最大生产批量为不超过6个单位，则任何时期生产x 个单位产品的成本费用为： 若 0＜x ≤6 ， 则生产总成本＝3十1·x 若 x ＝0 ， 则生产总成本＝0 又设每个时期末未销售出去的产品，在一个时期内单位产品的库存费用为0.5(千元)，同时还假定第1时期开始之初和在第4个时期之末，均无产品库存。现在我们的问题是；在满足上述给定的条件下，该厂如何安排各个时期的生产与库存，使所花的总成本费用最低？ 例3：设某企业在第一年初购买一台新设备，该设备在五年内的年运行收益、年运行费用及更换新设备的净费用如下表：（单位：万元） 年份(k) 役龄(t) 运行收益()k g t 运行费用()k r t 更新费用()k c t 第一年 0 22 6 18 第二年 0 1 23 21 6 8 19 22

动态规划讲解大全(含例题及答案)

动态规划讲解大全 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。 基本模型 多阶段决策过程的最优化问题。 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图） 这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。 记忆化搜索 给你一个数字三角形, 形式如下: 1 2 3 4 5 6 7 8 9 10 找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大. 无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)} 对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么

2设计动态规划算法的主要步骤为

2设计动态规划算法的主要步骤为： （1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。 3. 分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。 贪心选择算法与动态规划算法的异同点：同：都要求问题具有最优子结构性质；异：动态规划算法为自底向上的方式解各子问题，贪心算法为自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择问题就转换为规模更小的字问题。 6. 分治法所能解决的问题一般具有的几个特征是：（1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质; （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 P：也即是多项式复杂程度的问题。 NP就是多项式复杂程度的非确定性问题。 NPC(NP Complete)问题 ADT 抽象数据类型 分析问题→设计算法→编写程序→上机运行和测试 算法特性1. 确定性、可实现性、输入、输出、有穷性 算法分析目的2. 分析算法占用计算机资源的 情况，对算法做出比较和评价，设计出额更好 的算法。 3. 算法的时间复杂性与问题的规模相关，是 问题大小n的函数。 算法的渐进时间复杂性的含义：当问题的规模 n趋向无穷大时，影响算法效率的重要因素是 T(n)的数量级，而其他因素仅是使时间复杂度 相差常数倍，因此可以用T(n)的数量级(阶) 评价算法。时间复杂度T(n)的数量级(阶)称为 渐进时间复杂性。 最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 最坏情况下的时间复杂性和平均时间复杂性 考察的是n固定时，不同输入实例下的算法所 耗时间。最坏情况下的时间复杂性取的输入实 例中最大的时间复杂度： W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间 与各自概率的乘积和： A(n) =∑P(I)T(n，I) I∈Dn 为什么要分析最坏情况下的算法时间复杂 性？最坏情况下的时间复杂性决定算法的优 劣，并且最坏情况下的时间复杂性较平均时间 复杂性游可操作性。 1.贪心算法的基本思想？ 是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。 贪心选择算法与动态规划算法的异同点：同：都要求问题具有最优子结构性质；异：动态规划算法为自底向上的方式解各子问题，贪心算法为自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择问题就转换为规模更小的字问题。

动态规划习题

第七章动态规划 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（dynamic programming）同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献。 动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。 动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。 §7.1 动态规划的基本理论 1.1多阶段决策过程的数学描述 有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。任何一个阶段（stage，即决策点）都是由输入（input）、决策（decision）、状态转移律（transformation function）和输出（output）构成的，如图7-1（a）所示。其中输入和输出也称为状态（state），输入称为输入状态，输出称为输出状态。

动态规划典型例题

1、单调递增最长子序列 描述 求一个字符串的最长递增子序列的长度 如：dabdbf最长递增子序列就是abdf，长度为4 输入 第一行一个整数0

2、最长公共子序列 描述 如题，需要写一个程序，得出最长公共子序列。 tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。 输入 第一行给出一个整数N(0

3、括号匹配 时间限制：1000 ms | 内存限制：65535 KB 描述 给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。 如： []是匹配的 ([])[]是匹配的 ((]是不匹配的 ([)]是不匹配的 输入 第一行输入一个正整数N，表示测试数据组数(N<=10) 每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符， S的长度不超过100 输出 对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组 测试输出占一行 样例输入 4 [] ([])[] ((] ([)] 样例输出 3 2

第六章动态规划解析

第六章动态规划 6.1 动态规划的思想方法 6.1.1 动态规划的最优决策原理 活动过程划分为若干个阶段，每一阶段的决策，依赖于前一阶段的状态，由决策所采取的动作，使状态发生转移，成为下一阶段的决策依据。 P1P2 P n S0S1 S2┅┅S n-1 S n 图6.1 动态规划的决策过程 最优性原理：无论过程的初始状态和初始决策是什么，其余决策都必须相对于初始决策所产生的状态，构成一个最优决策序列。 S0 p(1,1) p(1,2) p(1,r1) s(1,1) s(1,2) s(1,r1) s(2,11) p(2,12) s(2,1r2) p(2,21) s(2,22) s(2,2r2) s(2,r11) s(2,r12) s(2,r1r2) 令最优状态为) (s，由此倒推： 22 ,2 s p p → ,2(s → → s→ ) )2,1( 22 )2,1( ) ,2( 22 最优决策序列，) p→ )2,1(p 22 ,2 ( 状态转移序列：) s 22 → 0s s→ ,2 ( )2,1( 赖以决策的策略或目标，称为动态规划函数。 整个决策过程，可以递归地进行，或用循环迭代的方法进行。 动态规划函数可以递归地定义，也可以用递推公式来表达。 最优决策是在最后阶段形成的，然后向前倒推，直到初始阶段； 而决策的具体结果及所产生的状态转移，却是由初始阶段开始进行计算的，然后向后递 6

6 归或迭代，直到最终结果。 6.1.2 动态规划实例、货郎担问题 例6.1 货郎担问题。 在有向赋权图>=

动态规划习题完整版

动态规划习题 Document serial number【NL89WT-NY98YT-NC8CB-NNUUT-NUT108】

动态规划专题分类视图数轴动规题： 题1.2001年普及组第4题--装箱问题 【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0

对于100%的数据,砝码的种类n满足:1≤n≤100; 对于30%的数据,砝码的总数量C满足:1≤C≤20; 对于100%的数据,砝码的总数量C满足:1≤C≤100; 对于所有的数据,砝码的总重量W满足:1≤W≤400000; 题3.石子归并-szgb.pas 【问题描述】有一堆石头质量分别为W1,W2,…,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。 【输入】输入文件szgb.in的第一行只有一个整数n(1≤n≤50),表示有n堆石子。接下去的n行,为每堆石子质量。 【输出】输出文件szgb.out的只有一行,该行只有一个整数,表示最小的质量差. 【样例输入】 5 5 8 13 27 14 【样例输出】 3 题4.补圣衣 【问题描述】有四个人，每人身上的衣服分别有s1,s2,s3和s4处破损,而且每处破损程度不同,破损程度用需修好它用的时间表示 (A1...As1,B1...Bs2,C1...Cs3,D1...Ds4)。不过你可以同时修补2处破损。但是这2处破损，只能是同一件衣服上的。就是说你只能同时修补一件衣服，修好了，才能修补下一件。 【输入】本题包含5行数据：第1行，为s1,s2,s3,s4(1≤s1,s2,s3,s4≤20) 第2行，为A1...As1共s1个数，表示第一件衣服上每个破损修好它所需的时间 第3行，为B1...Bs2共s2个数，表示第二件衣服上每个破损修好它所需的时间 第4行，为C1...Cs3共s3个数，表示第三件衣服上每个破损修好它所需的时间 第5行，为D1...Ds4共s4个数，表示第四件衣服上每个破损修好它所需的时间 (1≤A1...As1,B1...Bs2,C1...Cs3,D1...Ds4≤60) 【输出】输出一行,为修好四件衣服所要的最短时间。 【样例输入】 1213 5 43 6 243 【样例输出】 20 题5.光光的作业homework.pas/homework.exe 【问题描述】光光上了高中，科目增多了。在长假里，光光的老师们都非常严厉，都给他布置了一定量的作业。假期里，光光一共有的时间是k小时。在长假前，老师们一共给光光布置了n份作业，第i份作业需要的时间是ti小时。但是由于老师们互相不

动态规划法求解生产与存储问题

动态规划 一·动态规划法的发展及其研究内容 动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解 创立了解决这类过程优化问题的新方法——动态规划。1957年出版的他的名著《Dynamic Proggramming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题，采用动态规划法求解比用其他方法更为简便。 二·动态规划法基本概念 一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素： 1．阶段 阶段（stage）是对整个过程的自然划分。通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。阶段变量一般用k=….n.表示。

1.状态 状态(state)是我们所研究的问题（也叫系统）在过个阶段的初始状态或客观条件。它应能描述过程的特征并且具有无后效性，即当某阶段的状态给定时，这个阶段以后的过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是可以直接或者是间接可以观测的。描述状态的变量称为状态变量（State Virable）用s 表示，状态变量的取值集合称为状态集合，用S表示。变量允许取值的范围称为允许状态集合(set of admissble states).用x(k)表示第k阶段的状态变量，它可以是一个数或者是一个向量。用X(k)表示第k阶段的允许状态集合。 n 个阶段的决策过程有n+1个状态变量，x(n+1)是x(n)的演变的结果。 根据演变过程的具体情况，状态变量可以是离散的或是连续的。为了计算方便有时将连续变量离散化，为了分析的方便有时又将离散的变量视为连续的。 2．决策 当一个阶段的状态确定后，可以做出各种选择从而演变 到下一阶段的某个状态，这种选择手段称为决策 （decision），在最优控制问题中也称为控制（control）描述决策的变量称为决策变量（decision virable）。 变量允许取值的范围称为允许决策集合（set of

第11章 动态规划

第11章 动态规划 一个随事件或阶段推移的系统叫做动态系统，动态规划是解决多阶段决策过程最优化的一种数学方法。一个系统依据某种方式分为许多个不同的阶段，这些阶段不仅有着次序推移性，而且相互间有着依赖和影响。这样，在多阶段决策过程中，每个阶段决策的选择，不仅要依据次序来考查某阶段的效果，而且要顾及此决策对以后各阶段决策的影响。一般情况下，为得到整个系统的最优选择，必须放弃对某个阶段来说最佳的决策。对各个阶段所做的决策形成确定整个系统的决策序列，称这样的决策序列为系统的一个策略。对应某一确定的策略，整个系统依据某种数量指标衡量其决策的优劣。多阶段决策过程就是在所有允许策略集合中。确定一个达到最有指标的最优策略。这种衡量系统的指标一般取最大值或最小值的策略。因此，多阶段决策过程也是一个可以构成多个变量的最优化问题。动态规划就是解决此类多阶段决策过程的最优化方法。虽然动态规划主要解决多阶段决策的动态系统，但是可分阶段的静态系统问题也能作为特例用它有效地求解。 §11.1 动态规划的基本原理 本章通过构造数学模型，形成具有特殊的动态系统过程，将基于某种方式把整个过程分成若干个互相联系的阶段，在其每个阶段都需要作出决策，从而使整个过程达到最佳效果。同时，各个阶段决策的选择依赖于该阶段的状态以及前阶段或后阶段的变化。各个阶段决策确定后，组成一个决策序列，从而形成了整个过程具有前后关联的链状结构的多阶段决策过程，称为序贯决策过程。 先用下面的最短路问题（问题可分成阶段性）来说明动态规划的基本思想。 例 1，最短路问题。图11—1所示是一个路线网络图，连线上的数字表示两点之间的距离（或费用），要求寻找一条由A 到E 的路线，使距离最短（或费用最省）。 对于这样的一个比较简单的问题，可直接使用枚举法例举所有从A 到E 得路线，确定 出所应走的路线是距离最短或费用最少，用 动态规划的思想，如果已找到由A 到E 得最 短路线是A —B 1—C2—D 2—E （记作L ），那 么当寻求L 中的任何一点（如C 2）到E 得最 短路时，它必然是L 子路线 C 2—D 2—E(记 作L 1)。否则，如D 2到E 的最短路是另一条 路线L 2，则把A —B 1—C 2与L2连接起来， 就会得到一条不同于L 的从A 到E 得最短 路，根据最短路的这一特性，可以从最后一 段开始，用逐步向前递推的方法，一次求出路段上各点到E 的最短路，最后得到A 到E 得最短路。上述这种由系统的最后阶段逐段向初始阶段求最优的过程称为动态规划的解法。该过程揭示了动态规划的基础思想，为便于对动态规划的思想和方法进行数学描述，下面先引入动态规划的基本概念并建立最优目标函数。 （1）分阶段：适当地依据具体情况将系统分成若干个相互联系的阶段，并将各个段按顺序或逆序加以编号（常用K ），描述阶段的变量称为阶段变量。如例1可分为5个阶段，k=1，2，3，4，5. （2）状态：状态表示系统在某一阶段所处的位置。描述过程状态的变量称为状态变量，第k 阶段的状态变量常用s k 表示，状态变量的集合用S k 表示。如在例1中，第一阶段有一个状态就是初始位置A ，第三阶段有3个状态，即集合S3=}{1,2,3C C C . (3)决策：当系统处于某一阶段的某个状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。如在例1第二阶段中，从状态B2出发，其允许决

动态规划理论(精华)

动态规划理论 一．动态规划的逆向思维法 动态规划是一种思维方法，没有统一的、具体的模式。动态规划可以从多方面去考察，不同的方面对动 态规划有不同的表述。我们不打算强加一种统一的表述，而是从多个角度对动态规划的思维方法进行讨 论，希望大家在思维具体问题时，也能够从多个角度展开，这样收获会更大。 逆向思维法是指从问题目标状态出发倒推回初始状态或边界状态的思维方法。如果原问题可以分解成 几个本质相同、规模较小的问题，很自然就会联想到从逆向思维的角度寻求问题的解决。 你也许会想，这种将大问题分解成小问题的思维不就是分治法吗?动态规划是不是分而治之呢?其实， 虽然我们在运用动态规划的逆向思维法和分治法分析问题时，都使用了这种将问题实例归纳为更小的、 相似的子问题，并通过求解子问题产生一个全局最优值的思路，但动态规划不是分治法：关键在于分解 出来的各个子问题的性质不同。 分治法要求各个子问题是独立的(即不包含公共的子问题)，因此一旦递归地求出各个子问题的解后， 便可自下而上地将子问题的解合并成原问题的解。如果各子问题是不独立的，那么分治法就要做许多不 必要的工作，重复地解公共的子问题。 动态规划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题可包含公共的子问题) ，它对每个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。这就是动态规划高效

的一个原因。 动态规划的逆向思维法的要点可归纳为以下三个步骤： (1)分析最优值的结构，刻画其结构特征； (2)递归地定义最优值；0 (3)按自底向上或自顶向下记忆化的方式计算最优值。 【例题1】背包问题描述： 有一个负重能力为m的背包和n种物品，第i种物品的价值为v，重量为w。在不超过背包负重能力的前 提下选择若干个物品装入背包，使这些的物品的价值之和最大。每种物品可以不选，也可以选择多个。 假设每种物品都有足够的数量。 分析： 从算法的角度看，解决背包问题一种最简单的方法是枚举所有可能的物品的组合方案并计算这个组合 方案的价值之和，从中找出价值之和最大的方案。显然，这种靠穷举所有可能方案的方法不是一种有效 的算法。 但是这个问题可以使用动态规划加以解决。下面我们用动态规划的逆向思维法来分析这个问题。 (1)背包问题最优值的结构 动态规划的逆向思维法的第一步是刻画一个最优值的结构，如果我们能分析出一个问题的最优值包含 其子问题的最优值，问题的这种性质称为最优子结构。一个问题的最优子结构性质是该问题可以使用动 态规划的显著特征。 对一个负重能力为m的背包，如果我们选择装入一个第 i 种物品，那么原背包问题就转化为负重能力 为 m-w 的子背包问题。原背包问题的最优值包含这个子背包问题的最优值。若我们用背包的负重能力来 划分状态，令状态变量s[k]表示负重能力为k的背包，那么s[m]的值只取决于s[k](k≤m)的值。因此背包

动态规划方法的matlab实现及其应用

动态规划方法的matlab实现及其应用 （龙京鹏，张华庆，罗明良，刘水林） (南昌航空大学，数学与信息科学学院，江西，南昌) 摘要：本文运用matlab语言实现了动态规划的逆序算法，根据状态变量的维数，编写了指标函数最小值的逆序算法递归计算程序。两个实例的应用检验了该程序的有效性，同时也表明了该算法程序对众多类典型的动态规划应用问题尤其是确定离散型的应用问题的通用性，提供了求解各种动态规划问题的有效工具。关键词：动态规划基本方程的逆序算法 MATLAB实现 MATLAB Achieve For Dynamic Programming and Its Application (JingpengLong，HuaqingZhang，MingliangLuo，ShuilinLiu) （School of Mathematics and Information Science,Nanchang Hangkong University,Nanchang,China） Abstract:This article achieves the reverse algorithm of dynamic programming by using the matlab language，and prepares the recursive calculation program of reverse algorithm which thetargetfunctionvalueisthesmallest.Theapplicationoftwoexamplesshowthattheprogram is effective，and this algorithm program is general to many typical application of dynamic programming,especially the application of deterministic discrete.This algorithm program provides a effective tool to the solution of a variety of dynamic programming problems. Key words:dynamic programming；reverse algorithm；Matlab achievement 动态规划是一类解决多阶段决策问题的数学方法, 在工程技术、科学管理、工农业生产及军事等领域都有广泛的应用。在理论上,动态规划是求解这类问题全局最优解的一种有效方法,特别是对于实际中某些非线性规划问题可能是最优解的唯一方法。然而,动态规划仅仅决多阶段决策问题的一种方法,或者说是考查问题的一种途径,而不是一种具体的算法。就目前而言,动态规划没有统一的标准模型,其解法也没有标准算法,在实际应用中,需要具体问题具体分析。动态规划模型的求解问题是影响动态规划理论和方法应用的关键所在,而子问题的求解和大量结果的存储、调用更是一个难点所在。然而, 随着计算机技术的快速发展,特别是内存容量和计算速度的增加,使求解较小规模的动态规划问题成为可能,从而使得动态规划的理论和方法在实际中的应用范围迅速增加。 目前,在计算机上实现动态规划的一般求解方法并不多见,尤其是用来解决较复杂的具体问题的成果甚少。本文从实际出发,利用数学工具软件matlab 的强大功能, 对动态规划模型的求解方法做了尝试,编写出了动态规划逆序算法的matlab程序，并结合“生产与存储问题”[1] 和“背包问题”[1]进行了应用与检验,实际证明结果是令人满意的。 1 动态规划的基本模型 实际中,要构造一个标准的动态规划模型,通常需要采用以下几个步骤: ①划分阶段按照问题的时间或空间特征,把问题分为若干个阶段。这些阶段必须是有序的或者是可排序的(即无 后向性) ,否则,应用无效。 ②选择状态将问题发展到各个阶段时所处的各种客观情况用不同的状态表示,即称为状态。状态的选择要满足无后效性和可知性,即状态不仅依赖于状态的转移规律,还依赖于允许决策集合和指标函数结构。 ③确定决策变量与状态转移方程当过程处于某一阶段的某个状态时,可以做出不同的决策,描述决策的变量称为决策变量。在决策过程中,由一个状态到另一个状态的演变过程称为状态转移。状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。 ④写出动态规划的基本方程动态规划的基本方程一般根据实际问题可分为两种形式,逆序形式和顺序形式。这里只考虑逆序形式。动态规划基本方程的逆序形式为 f s k k( ) = opt gv s x{ ( k k k( , )+f s k+1( k+1))} x D s k∈ k k( ) k nn= , ?1, ,1 边界条件 f s n+1( n+1) = 0或f s v s x n n() = n n n( , ) 其中第k 阶段的状态为s k,其决策变量x k表示状s k的决策,状态转移方程为s k+1 =T s x k k k( , ), 态处于k 阶段的允许决策集合记为D s k k( ) , v s x k k k( , ) 为指标函数。

经典的动态规划入门练习题

动态规划入门练习题 1.石子合并 在一个圆形操场的四周摆放着N堆石子(N<= 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(<=20). (1)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最小; (2)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最大; 输入数据: 第一行为石子堆数N; 第二行为每堆的石子数,每两个数之间用一个空格分隔. 输出数据: 从第一至第N行为得分最小的合并方案.第N+1行是空行.从第N+2行到第2N+1行是得分最大合并方案.每种合并方案用N行表示,其中第i行(1<=i<=N)表示第i次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可).要求将待合并的两堆石子数以相应的负数表示. 输入输出范例: 输入: 4 4 5 9 4 输出: －４５９－４ －８－５９ －１３－９ ２２４－５－９４ ４－１４－４ －４－１８ ２２ 最小代价子母树设有一排数，共ｎ个，例如：22 14 7 13 26 15 11.任意2个相邻的数可以进行归并,归并的代价为该两个数的和,经过不断的归并,最后归为一堆,而全部归并代价的和称为总代价,给出一种归并算法,使总代价为最小. 输入、输出数据格式与“石子合并”相同。 输入样例： 4 12 5 16 4 输出样例： －１２－５１６４ １７－１６－４ －１７－２０ ３７

2.背包问题 设有ｎ种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为ＸＫ，今从ｎ种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于ＸＫ，而价值的和为最大。 输入数据： 第一行两个数：物品总数Ｎ，背包载重量ＸＫ；两个数用空格分隔； 第二行N个数,为Ｎ种物品重量；两个数用空格分隔； 第三行N个数,为N种物品价值; 两个数用空格分隔； 输出数据： 第一行总价值； 以下N行，每行两个数，分别为选取物品的编号及数量； 输入样例： 4 10 2 3 4 7 1 3 5 9 输出样例： 12 2 1 4 1 3.商店购物 某商店中每种商品都有一个价格。例如，一朵花的价格是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中写一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品）

算法设计与分析动态规划算法_百度文库

第六章动态规划算法 §1.动态规划算法的基本思想 动态规划方法是处理分段过程最优化问题的一类及其有效的方法。在实际生活中，有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程是如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（Richard Bellman）等人提出了解决这类问题的“最优化原则”，从而创建了最优化问题的一种新的算法动态规划算法。 最优化原则指出，多阶段过程的最优决策序列应当具有性质： 无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。这要求原问题的最优解包含了其子问题的一个最优解（称为最优子结构性质）。 动态规划算法采用最优原则来建立递归关系式（关于求最优值的），在求解问题时有必要验证该递归关系式是否保持最优原则。若不保持，则不可用动态规划算法。在得到最优值的递归式之后，需要执行回溯以构造最优解。在使用动态规划算法自顶向下（Top-Down）求解时，每次产生的子问题并不总是新问题，有些子问题反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个问题只计算一次，而后将其解保存在一个表格中，当再次要解此子问题时，只是简单地调用（用常数时间）一下已有的结果。通常，不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。 例1．多段图问题 设G=(V,E)是一个赋权有向图，其顶点集V被划分成k>2个不相交的子集Vi: ，其中，V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇)，下图 中所有的边(u,v)的始点和终点都在相邻的两个子集Vi和Vi＋1中：， ＋1。

动态规划练习试题和解答1

动态规划练习题 [题1] 多米诺骨牌（DOMINO） 问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。 现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。 输入格式： 文件的第一行是一个整数n（1〈=n〈=1000〉，表示有n个多米诺骨牌在桌面上排成一行。接下来共有n行，每行包含两个整数a、b（0〈=a、b〈=6，中间用空格分开〉。第I+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数（0表示空）。 输出格式： 只有一个整数在文件的第一行。这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。 [题2] Perform巡回演出 题目描述: Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出). 由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表. 输入: 输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去. 每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d 个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没