两个人选珠宝，设计算法求出最大价值

Question

举个例子，有一个项链上面有不同价值的珠宝，一个人选，剩下的归另一个人。
规则：选中i号位的珠宝，那么i-1号位和i+1号位的珠宝就不能再选了。
项链是一个环。

例子:
输入 4 10 8 输出 10 12
输入 10 4 8 5 输出 18 9
输入 3 2 10 2 3 7 输出 17 10
输入 1 1 1 1 1 输出 2 3

Answer 1

顺着思路写的，可能会有些冗余，有疑问可以再探讨

import copy


def demo(x):
    lx = [int(_) for _ in x.split(" ")]
    len_x = len(lx)
    # 因为中间会对列表做删除操作先把原始列表保存下来
    ori_lx = copy.deepcopy(lx)
    sx = len_x // 2 + 1
    a, b, la, lb, i = [], [], [], [], 0
    
    # 最多选择可宝石个数
    while i < sx:
        if not lx:
            break
        elif len(lx) == 1:
            # 如果 a已经拿到了第一个且 b 还没有拿到最后一个，那肯定是最后一个了，直接给 b
            if 0 in la and len_x-1 not in lb:
                b.append(lx[0])
            # 如果 a已经拿到了最后一个且 b 还没有拿到第一个，那肯定是第一个了，直接给 b
            elif len_x-1 in la and 0 not in lb:
                b.append(lx[0])
            # 否则给 a
            else:
                a.append(lx[0])
            break
        # 挑选价值最大的珠宝
        max_i = max(lx)
        # 获取当前珠宝所在位置
        max_index = lx.index(max_i)
        ori_max_index = ori_lx.index(max_i)
        before_index = after_index = max_index
        # 记录a已经选择的珠宝在整串项链的位置
        cur_index = ori_max_index + a.count(max_i) + b.count(max_i)
        la.append(cur_index)
        # 价值最大的珠宝给 a
        a.append(max_i)
        
        # 如果a选择的不是第一颗，则把前一颗给b
        if max_index > 0:
            before_index = max_index - 1
            b.append(lx[before_index])
            # 记录b已经拿到的珠宝在整串项链的位置
            lb.append(cur_index-1)
        # 如果a选择的不是最后一颗，则把后一颗给b
        if max_index + 1 < len(lx):
            b.append(lx[max_index + 1])
            after_index = max_index + 1
            # 记录b已经拿到的珠宝在整串项链的位置
            lb.append(cur_index + 1)
        # 剔除以选择的这几颗后继续选择
        lx = lx[0:before_index] + lx[after_index + 1:]
        i += 1
    print("最终结果", sum(a), sum(b))


if __name__ == "__main__":
    while 1:
        str_l = input("input: ")
        # str_l = "3 2 10 2 3 7"
        demo(str_l)

运行结果如下