动态规划中的一个证明问题

aimisiyou

hujunhua 发表于 2018-5-21 12:06
“A、B均按最优策略执行，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。”

何谓“ ...

用动态规划推导如下：
A[i,j]:表示从 i 到 j 项，轮取方可取到的最大和值(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]}
             =sum[i,j]-min{A[i+1,j]，A[i,j-1]}

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

hujunhua

程序简单，只能得到和，不能得到路径。

aimisiyou

如何证明，当数列项数为偶数时，双方都按最终和值最大策略，先手想取得最大和值必是全取偶数项或全取奇数项？

hujunhua

aimisiyou 发表于 2018-5-28 11:04
如何证明，当数列项数为偶数时，双方都按最终和值最大策略，先手想取得最大和值必是全取偶数项或全取奇数项 ...

不是全取偶数项或者全取奇数项，而是每次都取剩下的偶数个数中，奇数和与偶数和较大的一方。检查这个策略是否与动态规划的结果相一致。

我估计即使这样，也存在不一致的例子。

mathe

5,1,2,11,2,1
偶数项和更大，但是第一步最优策略是选择奇数项的5，使得先手可以取走17
如果先选择偶数项的1，先手只能取走13

aimisiyou

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

zhouguang

最近学python，来个：

1. def aplay(l):
   
2. k,m,n=l,len(l)-1,0
   
3. while n<m:k,n=[max(l2-k1,l1-k2) for l1,l2,k1,k2 in zip(l[:-n-1],l[n+1:],k[:-1],k[1:])],n+1
   
4. print((k[0]+sum(l))/2)
   
5. aplay([5,9,2,11,8,13,6])

复制代码

aimisiyou

aimisiyou 发表于 2018-5-21 12:18
哦表述错误了。最优策略应该是整局下来总分达到最大。

;;获取所有最优策略取法
(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 '(5 3 2 11 8 13 6))
((6 13 8 11 5 3 2) (6 13 5 3 8 11 2) (6 13 5 3 2 11 8) (5 3 6 13 8 11 2) (5 3 6 13 2 11 8) (5 3 2 11 6 13 8) (5 3 2 11 8 13 6))