⑴ 动态规划算法对所有问题都能得到整体最优解吗为什么
1、基本概念：
动态规划就是：每走一步，都会根据之前的情况来决定这一步的走向，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
2、基本思想与策略：
与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。
3、经典例题：
这里我们用2个经典例题来解释到底什么是动态规划。
⑵ 《股票最优投资组合案例研究 ——基于风险结合的动态规划法 》作者是谁
赵和平
⑶ 动态规划算法 通俗的讲解一下
这种技术采用自底向上的方式递推求值，将待求解的问题分解成若干个子问题，先求解子问题，并把子问题的解存储起来以便以后用来计算所需要求的解。简言之，动态规划的基本思想就是把全局的问题化为局部的问题，为了全局最优必须局部最优。多阶段决策问题是根据问题本身的特点，将其求解的过程划分为若干个相互独立又相互联系的阶段，在每一个阶段都需要做出决策，并且在一个阶段的决策确定以后再转移到下一个阶段，在每一阶段选取其最优决策，从而实现整个过程总体决策最优的目的
⑷ 动态规划算法程序例子
给你导弹拦截的吧：
[问题描述]
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，每个数据之间至少有一个空格），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
[输入输出样例]
INPUT：
389 207 155 300 299 170 158 65
OUTPUT：
6（最多能拦截的导弹数）
2（要拦截所有导弹最少要配备的系统数）
[问题分析]
我们先解决第一问。一套系统最多能拦多少导弹，跟它最后拦截的导弹高度有很大关系。假设a[i]表示拦截的最后一枚导弹是第i枚时，系统能拦得的最大导弹数。例如，样例中a[5]=3，表示：如果系统拦截的最后一枚导弹是299的话，最多可以拦截第1枚（389）、第4枚（300）、第5枚（299）三枚导弹。显然，a[1]~a[8]中的最大值就是第一问的答案。关键是怎样求得a[1]~a[8]。
假设现在已经求得a[1]~a[7]（注：在动态规划中，这样的假设往往是很必要的），那么怎样求a[8]呢？a[8]要求系统拦截的最后1枚导弹必须是65，也就意味着倒数第2枚被拦截的导弹高度必须不小于65，则符合要求的导弹有389、207、155、300、299、170、158。假如最后第二枚导弹是300，则a[8]=a[4]+1；假如倒数第2枚导弹是299，则a[8]=a[5]+1；类似地，a[8]还可能是a[1]+1、a[2]+1、……。当然，我们现在求得是以65结尾的最多导弹数目，因此a[8]要取所有可能值的最大值，即a[8]=max{a[1]+1,a[2]+1,……，a[7]+1}=max{a[i]}+1 (i=1..7)。
类似地，我们可以假设a[1]~a[6]为已知，来求得a[7]。同样，a[6]、a[5]、a[4]、a[3]、a[2]也是类似求法，而a[1]就是1，即如果系统拦截的最后1枚导弹是389，则只能拦截第1枚。
这样，求解过程可以用下列式子归纳：
a[1]=1
a[i]=max{a[j]}+1 （i>1，j=1,2,…,i-1，且j同时要满足：a[j]>=a[i]）
最后，只需把a[1]~a[8]中的最大值输出即可。这就是第一问的解法，这种解题方法就称为“动态规划”。
第二问比较有意思。由于它紧接着第一问，所以很容易受前面的影响，多次采用第一问的办法，然后得出总次数，其实这是不对的。要举反例并不难，比如长为7的高度序列“7 5 4 1 6 3 2”， 最长不上升序列为“7 5 4 3 2”，用多次求最长不上升序列的结果为3套系统；但其实只要2套，分别击落“7 5 4 1”与“6 3 2”。所以不能用“动态规划”做，那么，正确的做法又是什么呢？
我们的目标是用最少的系统击落所有导弹，至于系统之间怎么分配导弹数目则无关紧要，上面错误的想法正是承袭了“一套系统尽量多拦截导弹”的思维定势，忽视了最优解中各个系统拦截数较为平均的情况，本质上是一种贪心算法，但贪心的策略不对。如果从每套系统拦截的导弹方面来想行不通的话，我们就应该换一个思路，从拦截某个导弹所选的系统入手。
题目告诉我们，已有系统目前的瞄准高度必须不低于来犯导弹高度，所以，当已有的系统均无法拦截该导弹时，就不得不启用新系统。如果已有系统中有一个能拦截该导弹，我们是应该继续使用它，还是另起炉灶呢？事实是：无论用哪套系统，只要拦截了这枚导弹，那么系统的瞄准高度就等于导弹高度，这一点对旧的或新的系统都适用。而新系统能拦截的导弹高度最高，即新系统的性能优于任意一套已使用的系统。既然如此，我们当然应该选择已有的系统。如果已有系统中有多个可以拦截该导弹，究竟选哪一个呢？当前瞄准高度较高的系统的“潜力”较大，而瞄准高度较低的系统则不同，它能打下的导弹别的系统也能打下，它够不到的导弹却未必是别的系统所够不到的。所以，当有多个系统供选择时，要选瞄准高度最低的使用，当然瞄准高度同时也要大于等于来犯导弹高度。
解题时用一个数组sys记下当前已有系统的各个当前瞄准高度，该数组中实际元素的个数就是第二问的解答。
[参考程序]
program noip1999_2;
const max=1000;
var i,j,current,maxlong,minheight,select,tail,total:longint;
height,longest,sys:array [1..max] of longint;
line:string;
begin
write('Input test data:');
readln(line); {输入用字符串}
i:=1;
total:=0; {飞来的导弹数}
while i<=length(line) do {分解出若干个数，存储在height数组中}
begin
while (i<=length(line)) and (line[i]=' ') do i:=i+1; {过滤空格}
current:=0; {记录一个导弹的高度}
while (i<=length(line)) and (line[i]<>' ') do {将一个字符串变成数}
begin
current:=current*10+ord(line[i])-ord('0');
i:=i+1
end;
total:=total+1;
height[total]:=current {存储在height中}
end;
longest[1]:=1; {以下用动态规划求第一问}
for i:=2 to total do
begin
maxlong:=1;
for j:=1 to i-1 do
begin
if height[i]<=height[j]
then if longest[j]+1>maxlong
then maxlong:=longest[j]+1;
longest[i]:=maxlong {以第i个导弹为结束，能拦截的最多导弹数}
end;
end;
maxlong:=longest[1];
for i:=2 to total do
if longest[i]>maxlong then maxlong:=longest[i];
writeln(maxlong); {输出第一问的结果}
sys[1]:=height[1]; {以下求第二问}
tail:=1; {数组下标，最后也就是所需系统数}
for i:=2 to total do
begin
minheight:=maxint;
for j:=1 to tail do {找一套最适合的系统}
if sys[j]>height[i] then
if sys[j]<minheight then
begin minheight:=sys[j]; select:=j end;
if minheight=maxint {开一套新系统}
then begin tail:=tail+1; sys[tail]:=height[i] end
else sys[select]:=height[i]
end;
writeln(tail)
end.
[部分测试数据]
输入1：300 250 275 252 200 138 245
输出1：
5
2
输入2：181 205 471 782 1033 1058 1111
输出2：
1
7
输入3：465 978 486 476 324 575 384 278 214 657 218 445 123
输出3：
7
4
输入4：236 865 858 565 545 445 455 656 844 735 638 652 659 714 845
输出4：
6
7
够详细的吧
⑸ 动态规划算法（pascal）
在计算够不够开销时
20%这个数据是废的
你可以先减去预算再考虑存多少钱
比如手头钱的数目为a
预算为b
存在妈妈处的钱为c
可以先从a中减去b
然后c就等于c+a div 100 *100
var 略
begin
a:=0;
c:=0;
bo:=true;
for i:=1 to 12 do
begin
read(b[i]);
inc(a,300);
if a<b[i] then begin
writeln(i);
bo:=false;
break;
end
else begin
c:=c+a div 100*100;
dec(a,b[i]);
a:=a mod 100;
end;
end;
if bo then writeln(a+c+c div 5);
end.
⑹ 动态规划算法怎么计算
动态规划算法：
（1）分析最优解的性质，并刻画其结构特征。
（2）递归的定义最优解。
（3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。
（4）根据计算最优值时得到的信息，构造问题的最优解。
⑺ 详解动态规划算法
其实你可以这么去想。
能用动态规划解决的问题，肯定能用搜索解决。
但是搜素时间复杂度太高了，怎么优化呢？
你想到了记忆化搜索，就是搜完某个解之后把它保存起来，下一次搜到这个地方的时候，调用上一次的搜索出来的结果。这样就解决了处理重复状态的问题。
动态规划之所以速度快是因为解决了重复处理某个状态的问题。
记忆化搜索是动态规划的一种实现方法。
搜索到i状态，首先确定要解决i首先要解决什么状态。
那么那些状态必然可以转移给i状态。
于是你就确定了状态转移方程。
然后你需要确定边界条件。
将边界条件赋予初值。
此时就可以从前往后枚举状态进行状态转移拉。
⑻ 动态规划实现排队买票算法
不考虑时间效率就用递归。
比如让第一二人组队。加上后面所有人的时间得到总的时间T1
同理让第二三人组队，加上第一个人的时间和后面所有人的时间得到总的时间T2
在T1 T2 中选择小的为最终方案。
其中：加上后面所有人的时间得到总的时间，
加上第一个人的时间和后面所有人的时间得到总的时间，
又是规模较小的买票事件（即递归）
这样做简单好理解（前提是理解递归），但是时间很慢。
⑼ 动态规划算法的基本思想是什么
DP一定有状态，而贪心只是说这个题目最有满足什么条件就能得到最优解的情况
一般DP必须得求出他的状态和转移方程
⑽ 排队买票问题的动态规划算法
如果前i个人买票的最优买票方式一确定，比如第i-1个人买一张票，则前i-1个人的买票方式也一定是最优的。即问题的最优解包含子问题的最优解。
步骤1：用F（i）表示前i个人买票的最优方式，即所需最短时间；现在要决定F(i)需要考虑两种情况：
（1）第i个人的票自己买
（2）第i个人的票由第i-1个人买