python3 窮舉組合找出N個數值相加總合等於目標值的組合 .feat 叫我大掌櫃 古林狩獵

叫我大掌櫃這款手遊中，其中有個活動是古林狩獵(每日中午12:00-14:00)

它的玩法是這樣，你有N隻戰力數值不一的門客，你要挑戰古林裡的野獸

而這些野獸的戰力會由小到大的出現，15萬起跳到幾億

基本上一隻門客只能出場一次(有特殊能力的門客除外)

情況一：門客A數值100萬，目標野獸100萬

那一換一的情況下，很剛好沒什麼問題

情況二：門客A數值100萬，目標野獸15萬

雖然結果一樣是1換1，但你同時也浪費了85萬的戰力，如果可以縮小每個對戰的差值，就可以將戰力做最大化輸出。

我目前作法都是在活動當下，心算或者按計算機去加總

活動限時兩小時內打完，但因為門客的戰力會浮動(因資源投入而提高)

所以每天活動可能都要重新計算門客組合去打一隻野獸，這讓我覺得好花時間

於是決定動手寫個程式來跑這個數值加總>=目標值的門客排列組合，省時多了，幾秒鐘就搞定組合

讓我們一步一步做看看

一、對門客戰力素質做出所有的組合(不重複)

我要做組合的門客總數是26，只挑出1-3個門客為一組的組合

所以總共會有2,951個組合，這個數量你要手寫窮舉一個一個列出來，可想而知要耗費多少時間....

還是交給專業的電腦來處理就好，公式如下

程式碼如下

from itertools import combinations
#門客戰力陣列
nums=[6291,1698,756,661,631.9,615.2,535.7,528,281.6,
      253.8,240.1,236.9,230.3,216.5,216,209,206.7,
      197.9,196.8,184.7,170.3,168,167,163.1,162.3,160.1]

result=[]
#使用Combinations函式將nums陣列裡的值以i個個數輸出組合，並加到res陣列中
#filter(None,list)，是為了將空陣列過濾掉
for i in range(4):
    result +=list(filter(None,combinations(nums,i)))
    
print("26選1-3門客為一組的組合個數為: {}\n".format(len(result)))
print("前30筆組合如下:")
for n in range(30):
    print(result[n])

程式執行結果如下圖

二、找出總合大於等於目標野獸戰力的組合

取得所有1-3位門客一組的組合後，我們透過比對目標值將不符合條件的組合去掉。

假設我現在要打一隻1200萬的野獸，那我們要將所有組合做數值加總，並挑出總合大於等於1200萬的組合，再從中挑出差值最小的。

程式碼如下

from itertools import combinations
#野獸目標值
goal=1200
#門客戰力陣列
nums=[6291,1698,756,661,631.9,615.2,535.7,528,281.6,
      253.8,240.1,236.9,230.3,216.5,216,209,206.7,
      197.9,196.8,184.7,170.3,168,167,163.1,162.3,160.1]

result=[]
#使用Combinations函式將nums陣列裡的值以i個個數輸出組合，並加到res陣列中
#filter(None,list)，是為了將空陣列過濾掉
for i in range(4):
    result +=list(filter(None,combinations(nums,i)))
    
print("1.26選1-3門客為一組的組合個數為: {}\n".format(len(result)))

#只留下總和>=1200萬以上的組合    
result=[x for x in result if sum(x) >= goal]

print("2.總和大於1200萬以上的組合個數為: {}\n".format(len(result)))
print("3.前10筆組合如下(未排序):")
for n in range(10):
    print(result[n])
    
#以總和數值做排序(小->大)
result.sort(key=sum)

print("\n4.前10筆組合如下(以總合值排序後):")
for n in range(10):
    print(result[n])

print("\n5.差值最小的組合為: {} \t\t總和: {}  \t差值: {} \n".format(result[0], round(sum(result[0]),1), round(float(sum(result[0]))-float(goal),1)))

程式執行結果如下圖

三、加入迴圈得到N隻野獸的對戰組合

最後我們將前面的步驟放到副程式裡，在主程式寫一個For迴圈讀入每一隻對戰野獸的目標值，藉以得到對戰組合

最終版程式碼如下，線上版點這

from itertools import combinations

#野獸目標值陣列
targets=[720,900,1000,1200,1450,1550,2100,2450,2650,3300,4000]
#門客戰力陣列
nums=[14640,2045,1663,1485,1485,1302,1057,733.5,683.3,646.2,
     493.9,444.5,389.4,384.7,384.3,366.9,358.1,357.3,357,
     350.7,342.8,338.5,338.4,338,331.3,328.5]

#這裡是副程式，gettop1方法，輸入參數為amount(組合個數)與goal(總合目標值)
def gettop1(amount,goal):
    result=[]
    for i in range(amount):
        result +=list(filter(None,combinations(nums,i)))
    result=[x for x in result if sum(x) >= goal]
    result.sort(key=sum)
    if (len(result) > 0):
        return result[0]
    return None

#總差值
deviations=0

#這裡是主程式
for target in targets:
    #呼叫副程式gettop1方法，丟入組合個數及目標值
    #組合個數丟入4，在程式中代表0到3，所以會是C26取3 + C26取2 + C26取1 + C26取0
    tmp = gettop1(5,target)
    print('------------目標野獸數值: {} 萬 ------------'.format(target))
    if (tmp is None):
        print("沒有找到結果。\n")
    else:
        #差值
        deviation = round(float(sum(tmp))-float(target),1)
        #加總差值
        deviations += deviation
        print("{} \t\t總合: {}  \t差值: {} \n".format(tmp, round(sum(tmp),1), deviation))
        #使用過的門客，從陣列中移除
        for element in tmp:
            nums.remove(element)

print("總差值:{}".format(deviations))

程式執行結果如下圖

做到這裡基本上，對戰組合就都有了，可以根據戰力去找到對應的門客。

四、加入外迴圈比較不同組合數，取得差值最佳解。

使用了一段時間後，發現偶爾需要調整組合數來比較差值最小化的解，等於用最少戰力達到最大化輸出

什麼意思呢，目前發現最佳解大概落在兩個組合

所以我增加一個外迴圈，來切換組合個數做比較。

最後給出最佳解。

更新後的程式碼如下，線上版點這

from itertools import combinations

targets=[]
nums=[]
resultmsg=""
olddeviation=0
#這裡是副程式，gettop1方法，輸入參數為amount(組合個數)與goal(總合目標值)
def gettop1(amount,goal):
    result=[]
    for i in range(amount):
        result +=list(filter(None,combinations(nums,i)))
    result=[x for x in result if sum(x) >= goal]
    result.sort(key=sum)
    if (len(result) > 0):
        return result[0]
    return None
    
def init():
    global targets
    global nums
    #野獸目標值陣列
    targets=[585,720,900,1000,1200,1450,1550,2100,2450,2650,3300,4000]
    #門客戰力陣列
    nums=[15104,2393,1882,1735,1524,1229,863.5,791.7,725.1,543.6,463.9,451.2,403,392.5,378.2,375.4,371.9,368.1,365,364.5,359.9,354.4,351.7,342.9,333.5]

#這裡是主程式   
for i in range(4,6):
    tmpmsg=""
    init() #初始化陣列值
    deviations=0 #總差值
    for target in targets:
        #呼叫副程式gettop1方法，丟入組合個數及目標值
        #組合個數丟入4，在程式中代表0到3，所以會是C26取3 + C26取2 + C26取1 + C26取0
        tmp = gettop1(i,target)
        tmpmsg+='------------目標野獸數值: {} 萬 ------------\n'.format(target)
        if (tmp is None):
            tmpmsg+="沒有找到結果。\n"
        else:
            #差值
            deviation = round(float(sum(tmp))-float(target),1)
            #加總差值
            deviations += deviation
            tmpmsg+="{} \t\t總合: {}  \t差值: {} \n".format(tmp, round(sum(tmp),1), deviation)
            #使用過的門客，從陣列中移除
            for element in tmp:
                nums.remove(element)
    if (olddeviation == 0):
        olddeviation = deviations
        tmpmsg+="\ni={}, 總差值:{}\n".format(i, deviations)
        resultmsg = tmpmsg
    if (olddeviation > deviations):
        olddeviation = deviations
print(resultmsg)

結果

五、整理至Excel

我目前有在Google上建了Excel來整理古林狩獵的資料，連結在這，貼給大家做個參考

我先將所有門客的戰力列出來(AB行)，對戰組合那邊只需要輸入賺錢(戰力)，名字會自己抓對應的，也會自動加總

抓對應戰力門客名字公式如下

=IFERROR(INDEX($A$2:$B$46,MATCH(F2,$B$2:$B$46,0),1),"")

IFERROR(運算式, "運算式發生錯誤時要顯示的字串")，字串給空值表示發生錯誤值時該欄位會填入空值，就不會出現【#N/A】

這邊用Index+match就為了透過門客的賺錢值找到對應的門客名字。

INDEX(參照範圍,列,欄)，概念就像是給(x,y)回傳該位置的值。

MATCH(你要查詢的門客賺錢目標值,門客賺錢的參照數列,搜尋類型)

MATCH的搜尋類型有以下三種

1. 0: 未排序並找出完全符合的數值。
2. 1(預設): 遞增排序並找出小於或等於的最大值
3. 2: 遞減排序並找出大於或等於的最小值

六、結論

果然花時間的運算交給電腦來處理，都只是幾秒鐘的事情，舒服。

後續可以將Excel整合進來，直接對Excel做讀寫檔。

或是改成Web版，網頁做UI，使用者輸入門客資料，傳到Python處理完再傳回來網頁做顯示，門客資料可存在Firebase。