2021年7月16日

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

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

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

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

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


情況一:門客A數值100萬,目標野獸100萬

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


情況二:門客A數值100萬,目標野獸15萬

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


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

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

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

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

讓我們一步一步做看看


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

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

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

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

程式碼如下

  1. from itertools import combinations
  2. #門客戰力陣列
  3. nums=[6291,1698,756,661,631.9,615.2,535.7,528,281.6,
  4. 253.8,240.1,236.9,230.3,216.5,216,209,206.7,
  5. 197.9,196.8,184.7,170.3,168,167,163.1,162.3,160.1]
  6.  
  7. result=[]
  8. #使用Combinations函式將nums陣列裡的值以i個個數輸出組合,並加到res陣列中
  9. #filter(None,list),是為了將空陣列過濾掉
  10. for i in range(4):
  11. result +=list(filter(None,combinations(nums,i)))
  12. print("26選1-3門客為一組的組合個數為: {}\n".format(len(result)))
  13. print("前30筆組合如下:")
  14. for n in range(30):
  15. print(result[n])

程式執行結果如下圖


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

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

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

程式碼如下

  1. from itertools import combinations
  2. #野獸目標值
  3. goal=1200
  4. #門客戰力陣列
  5. nums=[6291,1698,756,661,631.9,615.2,535.7,528,281.6,
  6. 253.8,240.1,236.9,230.3,216.5,216,209,206.7,
  7. 197.9,196.8,184.7,170.3,168,167,163.1,162.3,160.1]
  8.  
  9. result=[]
  10. #使用Combinations函式將nums陣列裡的值以i個個數輸出組合,並加到res陣列中
  11. #filter(None,list),是為了將空陣列過濾掉
  12. for i in range(4):
  13. result +=list(filter(None,combinations(nums,i)))
  14. print("1.26選1-3門客為一組的組合個數為: {}\n".format(len(result)))
  15.  
  16. #只留下總和>=1200萬以上的組合
  17. result=[x for x in result if sum(x) >= goal]
  18.  
  19. print("2.總和大於1200萬以上的組合個數為: {}\n".format(len(result)))
  20. print("3.前10筆組合如下(未排序):")
  21. for n in range(10):
  22. print(result[n])
  23. #以總和數值做排序(小->大)
  24. result.sort(key=sum)
  25.  
  26. print("\n4.前10筆組合如下(以總合值排序後):")
  27. for n in range(10):
  28. print(result[n])
  29.  
  30. print("\n5.差值最小的組合為: {} \t\t總和: {} \t差值: {} \n".format(result[0], round(sum(result[0]),1), round(float(sum(result[0]))-float(goal),1)))

程式執行結果如下圖


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

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

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

  1. from itertools import combinations
  2.  
  3. #野獸目標值陣列
  4. targets=[720,900,1000,1200,1450,1550,2100,2450,2650,3300,4000]
  5. #門客戰力陣列
  6. nums=[14640,2045,1663,1485,1485,1302,1057,733.5,683.3,646.2,
  7. 493.9,444.5,389.4,384.7,384.3,366.9,358.1,357.3,357,
  8. 350.7,342.8,338.5,338.4,338,331.3,328.5]
  9.  
  10. #這裡是副程式,gettop1方法,輸入參數為amount(組合個數)與goal(總合目標值)
  11. def gettop1(amount,goal):
  12. result=[]
  13. for i in range(amount):
  14. result +=list(filter(None,combinations(nums,i)))
  15. result=[x for x in result if sum(x) >= goal]
  16. result.sort(key=sum)
  17. if (len(result) > 0):
  18. return result[0]
  19. return None
  20.  
  21. #總差值
  22. deviations=0
  23.  
  24. #這裡是主程式
  25. for target in targets:
  26. #呼叫副程式gettop1方法,丟入組合個數及目標值
  27. #組合個數丟入4,在程式中代表0到3,所以會是C26取3 + C26取2 + C26取1 + C26取0
  28. tmp = gettop1(5,target)
  29. print('------------目標野獸數值: {} 萬 ------------'.format(target))
  30. if (tmp is None):
  31. print("沒有找到結果。\n")
  32. else:
  33. #差值
  34. deviation = round(float(sum(tmp))-float(target),1)
  35. #加總差值
  36. deviations += deviation
  37. print("{} \t\t總合: {} \t差值: {} \n".format(tmp, round(sum(tmp),1), deviation))
  38. #使用過的門客,從陣列中移除
  39. for element in tmp:
  40. nums.remove(element)
  41.  
  42. print("總差值:{}".format(deviations))

程式執行結果如下圖

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


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

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

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

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

最後給出最佳解。

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

  1. from itertools import combinations
  2.  
  3. targets=[]
  4. nums=[]
  5. resultmsg=""
  6. olddeviation=0
  7. #這裡是副程式,gettop1方法,輸入參數為amount(組合個數)與goal(總合目標值)
  8. def gettop1(amount,goal):
  9. result=[]
  10. for i in range(amount):
  11. result +=list(filter(None,combinations(nums,i)))
  12. result=[x for x in result if sum(x) >= goal]
  13. result.sort(key=sum)
  14. if (len(result) > 0):
  15. return result[0]
  16. return None
  17. def init():
  18. global targets
  19. global nums
  20. #野獸目標值陣列
  21. targets=[585,720,900,1000,1200,1450,1550,2100,2450,2650,3300,4000]
  22. #門客戰力陣列
  23. 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]
  24.  
  25. #這裡是主程式
  26. for i in range(4,6):
  27. tmpmsg=""
  28. init() #初始化陣列值
  29. deviations=0 #總差值
  30. for target in targets:
  31. #呼叫副程式gettop1方法,丟入組合個數及目標值
  32. #組合個數丟入4,在程式中代表0到3,所以會是C26取3 + C26取2 + C26取1 + C26取0
  33. tmp = gettop1(i,target)
  34. tmpmsg+='------------目標野獸數值: {} 萬 ------------\n'.format(target)
  35. if (tmp is None):
  36. tmpmsg+="沒有找到結果。\n"
  37. else:
  38. #差值
  39. deviation = round(float(sum(tmp))-float(target),1)
  40. #加總差值
  41. deviations += deviation
  42. tmpmsg+="{} \t\t總合: {} \t差值: {} \n".format(tmp, round(sum(tmp),1), deviation)
  43. #使用過的門客,從陣列中移除
  44. for element in tmp:
  45. nums.remove(element)
  46. if (olddeviation == 0):
  47. olddeviation = deviations
  48. tmpmsg+="\ni={}, 總差值:{}\n".format(i, deviations)
  49. resultmsg = tmpmsg
  50. if (olddeviation > deviations):
  51. olddeviation = deviations
  52. print(resultmsg)

結果


五、整理至Excel

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

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

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

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

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

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

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

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

MATCH的搜尋類型有以下三種

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

六、結論

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

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

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

沒有留言:

張貼留言