“A、B均按最优策略执行，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。”
何谓“ ...
用动态规划推导如下：
A:表示从 i 到 j 项，轮取方可取到的最大和值(i<j);
sum:表示从 i 到 j 项的和值;
即有A=max{ai+(sum-A)，aj+(sum-A)}
=max{sum-A，sum-A}
=sum-min{A，A}
(defun fmax (lst)
(defun f(lst)
(setq i 1)
(mapcar '(lambda (x) (if (minusp (setq i (* i -1)) ) x0 )) 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 发表于 2018-5-28 11:04
如何证明，当数列项数为偶数时，双方都按最终和值最大策略，先手想取得最大和值必是全取偶数项或全取奇数项 ...
不是全取偶数项或者全取奇数项，而是每次都取剩下的偶数个数中，奇数和与偶数和较大的一方。检查这个策略是否与动态规划的结果相一致。
我估计即使这样，也存在不一致的例子。 5,1,2,11,2,1
偶数项和更大，但是第一步最优策略是选择奇数项的5，使得先手可以取走17
如果先选择偶数项的1，先手只能取走13 本帖最后由 aimisiyou 于 2018-6-6 14:33 编辑
A=max{ai+(sum-A)，aj+(sum-A)}
=max{sum-A，sum-A}
=sum-min{A,A}
由此，每算一个A就要算一次sum,加法运算次数太多(尤其是当i远远小于j时)，而且局部加法很多是重复的，严重影响效率，考虑优化。
从图中可以看出(定义从上往下依次为第一层、第二层……；显然，从第二层开始，每个节点上层有两个子节点)，从第三层开始，节点A的值=该节点的较小子节点的较小子节点的值+对应值（若该节点的子节点在左边，对应值为第一层第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 最近学python，来个：
def aplay(l):
k,m,n=l,len(l)-1,0
while n<m:k,n=,l,k[:-1],k)],n+1
print((k+sum(l))/2)
aplay() 本帖最后由 aimisiyou 于 2018-6-13 21:39 编辑
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))
页:
1
[2]