#!/usr/bin/env python

# encoding: utf-8

class wisdom(object):

    def __init__(self,n,g):

        self.n = n

        self.g = g

    def dist(self): #所有可能分配方案

         if self.n == 1:

             yield [self.g]

             return

         for i in range(self.g, -1, -1):#步长-1 递减

             for d in wisdom(self.n-1, self.g-i).dist():

                 yield [i] + d

    def solve(self):#最优方案

        D = {}

        if self.n in D:

            return D[self.n]

        for d in wisdom(self.n,self.g).dist():#遍历所有方案

            if sum(pirates_vote(d,i).vote() for i in range(self.n)) > self.n/2:

                D[self.n] = d

                return d

        D[self.n] = None

        return None

class pirates_vote(wisdom): #返回值为海盗是否支持，1:支持  0：反对；

    def __init__(self,plan,num): #支持与反对的判断条件是 plan 与 自己在方案中的位置；

        self.num = num # num表示在自己之后是否还有其他海盗

        self.plan = plan #方案 是一个有序的list

    def vote(self):

        n = len(self.plan) #该方案一共多少人

        if self.num == 0:

            return 1

        while wisdom(n-1,10).solve() == None:

            n -= 1

            self.num -= 1

        if self.num <= 0:

            return 1

        if wisdom(n-1,100).solve()[self.num-1] >= self.plan[self.num]:

            return 0 #如果下一个方案钱多，我就不支持这个方案

        return 1

llbb = wisdom(5,10)

print(list(llbb.dist()))

print(type(llbb.dist()))

print(llbb.solve())