拆单问题，将物品分成n个订单

Question

有如下N个物品，价格为 {g1,g2,g3,g4,…,gn}，将物品分成订单，每个订单物品数量不超过M(int),每个子订单总金额不超过Y，但尽可能大，求怎么分单才能使得订单数（Num）值最小？（ps:可以理解为所有基本数据为int类型）

Answer 1

此方法可行，价格列表越长，准确性越大，但是对内存和时间要求特别大，价格列表越长时间和内存指数增长

COUNT = 0
list_all=[]
sum = []
#实现全排列的函数
def perm(n, begin, end):
global COUNT
if begin >= end:
list_all.append(n)
COUNT += 1
else:
i = begin
for num in range(begin, end):
n[num], n[i] = n[i], n[num]
perm(n, begin + 1, end)
n[num], n[i] = n[i], n[num]

def analizy(M,Y):
for v in list_all:#遍历所有价格排列的可能

    l = [i for i in v]#将一个 list 映射为另一个 list，每个元素设为变量i，对每个可能价格列表切成M大小的子列表
    list_son=list([l[i:i + M] for i in range(0, len(l), M)])

    for a in list_son:#遍历字列表，对每个子列表求和，并判断符合最大商品数和小于最大金额的子列表，然后放到list——sonson列表中，其余的组成一个新列表重新开始，M此时递减
        list_sonson=[]
        list_rest=[]
        sum2=0
        for c in a:
            sum2+=c
        if len(a)==M and sum2<=Y:
            list_sonson.append(a)
            global sum1
            sum1=len(list_sonson)
            sum1+=sum1
        else:
            list_rest.extend(a)
            if len(list_rest)==0:
                break
            elif len(list_rest)==1:
                sum1+=1
            else:
                perm(list_rest, 0, len(list_rest))
                M-=1
                analizy(M, Y)

        sum.append(sum1)#把每一种价格排列，组成的组数放入sum1列表中，注意这里的顺序是和群排列的顺序一样的，一次可以找出对应的那价格排列

#价格列表
n = [4,5,35,46,12,59,25,46,45,29]
perm(n, 0, len(n))
analizy(M=3,Y=82)#M是最大商品数，Y是订单最大金额

#因为用min函数不能直接对列表求多个最小值相同及其下标。
min = min(sum)
list_dict=[]
for v in sum:
if v==min:
v_index=sum.index(v)
dic = {v:v_index}
list_dict.append(dic)

print("全排列结果有{}种".format(COUNT))
print("最小组数对应价格列表排列的下标和list_dict里对应的下标列表：\n{}".format(list_dict))#根据此列表可以找出对应的那个最少组数的价格排列，