叫我大掌櫃這款手遊中，其中有個活動是古林狩獵(每日中午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的搜尋類型有以下三種
- 0: 未排序並找出完全符合的數值。
- 1(預設): 遞增排序並找出小於或等於的最大值
- 2: 遞減排序並找出大於或等於的最小值
六、結論
果然花時間的運算交給電腦來處理，都只是幾秒鐘的事情，舒服。
後續可以將Excel整合進來，直接對Excel做讀寫檔。
或是改成Web版，網頁做UI，使用者輸入門客資料，傳到Python處理完再傳回來網頁做顯示，門客資料可存在Firebase。