动态规划

aimisiyou

    动态规划的基本思想是把待求解的问题分解成若干个子问题，先求解子问题，然后再从这些子问题的解得到原问题的解，其中用动态规划分解得到的子问题往往不是互相独立的。动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。求解步骤如下：

    1. 找出最优解的性质，并刻画其结构特征；

    2. 递归地定义最优值；

    3. 以自底向上的方式计算出最优值；

    4. 根据计算最优值时得到的信息，构造最优解。

例1：对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。
　　举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：
　　{3}and {1,2}

　　这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）
　　如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分发的子集合各数字和是相等的:
　　{1,6,7} and {2,3,4,5} {注 1+6+7=2+3+4+5}
　　{2,5,7} and {1,3,4,6}
　　{3,4,7} and {1,2,5,6}
　　{1,2,4,7} and {3,5,6}
　　给出N，你的程序应该输出所有划分方案.

例2：下一个双人游戏:N(2 <= N <= 100)个正整数的序列放在一个游戏平台上（例如4 7 2 9 5 2），两人轮流从序列的两端取数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。
　　编一个执行最优策略的程序，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。你的程序要始终为两位玩家都执行最优策略。

yangjian001

做一个热心并受欢迎的人

aimisiyou

http://cppblog.com/menjitianya/archive/2015/10/23/212084.html

aimisiyou

例题2 网上有许多相关的代码，但要么没有详细说明推导过程，要么就是错误的绕来绕去。
自己推导了下，其实不是很难。
A{i,j]:表示从i到j项，A能取到的最大和值(i<j)，sum[i,j]:表示从i到j项的和值
即有A[i,j]=max{ai+(sum[i+1,j]-A[i+1,j])，aj+(sum[i,j-1]-A[i,j-1])}
        =max{sum[i,j]-A[i+1,j]，sum[i,j]-A[i,j-1]}

(defun f (lst)
     (if (<= (length lst) 2)
         (setq va (apply 'max lst))
         (setq va (apply 'max
                         (list
                              (- (apply '+  lst) (f  (cdr lst)))
                             (- (apply '+  lst) (f  (reverse (cdr (reverse lst)))))
                         )
                    )
            )
    )
)
_$ (f '(4 7 2 9 5 2))
18
_$

aimisiyou

有时知道决策过程比知道简单的结果更加有意义。还是上题，A和B行成的整个决策有哪几条路径？如（2，4，7，5，9，2）是其中一条路径。那么需要找出所有路径？

aimisiyou

先由上往下求出各节点值，再由下往上依次求出各路径上的值（即决策过程），可得出所有路径。
故四条路径为：
（2，5，9，2，7，4）
（2，5，9，4，7，2）
（2，4，7，5，9，2）
（2，4，7，2，9，5）

通过观察发现，给定的数据若是按规律排列（如递增或递减），那么总路径条数仅有一条；若不是按规律排列（非递增或非递减），那么总路径条数一定是偶数。（对于不按规律排列的情况，想想如何证明？）

如何通过编程来找出所有路径？
比较无脑的方法就是枚举出所有可能，但复杂度是指数级2^(n-1)。
考虑将复杂度降低，减少运算次数。

aimisiyou

找出（5,9,2,11,8,13,6）的所有路径：
（6,13,8,11,2,9,5）
（6,13,8,11,5,9,2）
（6,13,5,9,8,11,2）
（6,13,5,9,2,11,8）
（5,9,6,13,8,11,2）
（5,9,6,13,2,11,8）
（5,9,2,11,6,13,8）
（5,9,2,11,8,13,6）

aimisiyou

(defun fmax (lst)
         (defun f(lst)
               (setq i 1)
              (mapcar '(lambda (x) (if (minusp (setq i (* i -1)) ) x  0 )) lst)
          )
          (if  (= 0 (rem (length lst) 2))
               (setq va (max
                             (apply '+ (f lst))  
                             (apply '+ (f (cdr lst)))
                         )
                )
               (setq va (max
                               (+ (car lst) (min (apply '+ (f (cdr lst)))  (apply '+ (f (cddr lst)))))
                               (+ (last lst) (min (apply '+ (f (cdr (reverse lst))))  (apply '+ (f (cddr (reverse lst))))))
                         )
                )
           )
)
_$ (fmax '(5 9 2 11 8 13 6))
21

aimisiyou

aimisiyou 发表于 2018-5-15 13:58
例题2 网上有许多相关的代码，但要么没有详细说明推导过程，要么就是错误的绕来绕去。
自己推导了下，其实 ...

A[i,j]=max{ai+(sum[i+1,j]-A[i+1,j])，aj+(sum[i,j-1]-A[i,j-1])}
        =max{sum[i,j]-A[i+1,j]，sum[i,j]-A[i,j-1]}
        =sum[i,j]-min{A[i+1,j],A[i,j-1]}
由此，每算一个A[i,j]就要算一次sum[i,j],加法运算次数太多(尤其是当i远远小于j时)，而且局部加法很多是重复的，严重影响效率，考虑优化。

从图中可以看出(定义从上往下依次为第一层、第二层……；显然，从第二层开始，每个节点上层有两个子节点)，从第三层开始，节点A[i,j]的值=该节点的较小子节点的较小子节点的值+对应值（若该节点的子节点在左边，对应值为第一层第j个数;若该节点的子节点在右边，对应值为第一层第i个数;），这样通过先查找再做一次加法运算来替换sum大量求和运算，显然大大提高了程序运行效率。
(defun f (lst)
  (setq i -1)
  (setq lst1 (mapcar '(lambda (x y)   
                         (progn
                            (setq i (+ i 1))
                            (list (if (<= x y) 0 1)
                                  (min x y)
                                  (max x y)   
                                  (if (< i 1) nil (nth (- i 1) lst))
                                  (nth (+ i 2) lst)
                            )
                         )        
                      )
                      (reverse (cdr (reverse lst)))
                      (cdr lst)
               )
   )
   (while (cdr lst1)
         (setq lst1 (mapcar '(lambda (x y)   
                               (list (setq j (if (<= (caddr x) (caddr y)) 0 1))   
                                     (min (caddr x) (caddr y))  
                                     (if (= j 0) (+ (cadr x) (last x))  (+ (cadr y) (cadddr y)))
                                     (cadddr x)
                                     (last y)
                                )
                              )        
                           (reverse (cdr (reverse lst1)))
                           (cdr lst1)
                      )
            )
   )
(caddr (car lst1))
)

_$ (f '(2 7 5 4 9 1 8 15 3 9 5 2 11 7 4 6))
53

aimisiyou

;;获取所有最优策略取法
(defun f (lst)
  (setq i -1)
  (setq lst1 (mapcar '(lambda (x y)   
                         (progn
                            (setq i (+ i 1))
                            (list (if (< x y) -1 (if (= x y) 0 1))
                                  (min x y)
                                  (max x y)   
                                  (if (< i 1) nil (nth (- i 1) lst))
                                  (nth (+ i 2) lst)
                                  (list
                                         (list
                                               (max x y)
                                               (min x y)
                                          )
                                   )
                            )
                         )        
                      )
                      (reverse (cdr (reverse lst)))
                      (cdr lst)
               )
   )
  (while (cdr lst1)
       (setq lst1 (mapcar '(lambda (x y)   
                              (list (setq j (if (< (caddr x) (caddr y)) -1 (if (= (caddr x) (caddr y)) 0 1)))   
                                    (min (caddr x) (caddr y))  
                                    (if (<= j 0) (+ (cadr x) (cadddr (cdr x)))  (+ (cadr y) (cadddr y)))
                                    (cadddr x)
                                    (cadddr (cdr y))
                                    (if (= j -1)
                                         (mapcar '(lambda (z) (cons (cadddr (cdr x)) z)) (last x) )
                                         (if (= j 1)
                                             (mapcar '(lambda (z) (cons (cadddr y) z)) (last y) )
                                             (append
                                                       (mapcar '(lambda (z) (cons (cadddr (cdr x)) z)) (last x) )
                                                       (mapcar '(lambda (z) (cons (cadddr y) z)) (last y) )
                                              )
                                         )
                                    )
                                )
                              )        
                           (reverse (cdr (reverse lst1)))
                           (cdr lst1)
                      )
            )
   )
  (last  (car lst1))
)


_$ (f '(5 9 2 11 8))
((8 11 2 9 5) (8 11 5 9 2) (5 9 8 11 2) (5 9 2 11 8))
_$ (f '(5 9 2 11 8 13 6))
((6 13 8 11 2 9 5) (6 13 8 11 5 9 2) (6 13 5 9 8 11 2) (6 13 5 9 2 11 8) (5 9 6 13 8 11 2) (5 9 6 13 2 11 8) (5 9 2 11 6 13 8) (5 9 2 11 8 13 6))
_$ (f '(2 7 5 4 9 1 8 15 3 9 5 2 11 7 4 6))
((6 4 2 7 11 7 5 2 4 5 9 9 1 3 15 8) (6 4 2 7 11 7 5 2 4 5 9 9 1 8 15 3) (6 4 2 7 11 7 5 2 4 5 9 9 1 3 15 8) (6 4 2 7 11 7 5 2 4 5 9 9 1 8 15 3) (6 4 2 7 11 7 5 2 4 9 1 5 9 3 15 8) (6 4 2 7 11 7 5 2 4 9 1 5 9 8 15 3) (6 4 2 7 11 7 5 2 4 9 1 8 15 5 9 3) (6 4 2 7 11 7 5 2 4 9 1 8 15 3 9 5) (6 4 2 7 5 7 11 2 4 5 9 9 1 3 15 8) (6 4 2 7 5 7 11 2 4 5 9 9 1 8 15 3) (6 4 2 7 5 7 11 2 4 5 9 9 1 3 15 8) (6 4 2 7 5 7 11 2 4 5 9 9 1 8 15 3) (6 4 2 7 5 7 11 2 4 9 1 5 9 3 15 8) (6 4 2 7 5 7 11 2 4 9 1 5 9 8 15 3) (6 4 2 7 5 7 11 2 4 9 1 8 15 5 9 3) (6 4 2 7 5 7 11 2 4 9 1 8 15 3 9 5))
_$