這節(jié)課內(nèi)容我之前在貼吧發(fā)過三貼，分別是：

【1】一種基于lingo軟件的UR升級最佳喂法的通用解法

https://tieba.baidu.com/p/6541347702

【2】1-7級UR在不同同卡數(shù)下升8所需最小經(jīng)驗(yàn)及方案表

https://tieba.baidu.com/p/6607353641

【3】雙人卡多同卡疊喂最佳策略表

https://tieba.baidu.com/p/6975289475

????????第一帖闡述了如何把UR疊喂問題化為整數(shù)線性規(guī)劃問題并用軟件求解；第二貼更細(xì)化一步，加了剪枝的方法，嚴(yán)格論證了疊喂會(huì)用到的基本方案以及常見情況下的最優(yōu)解；第三帖在第二貼基礎(chǔ)上再擴(kuò)展出去，研究了雙人卡疊喂。這一系列研究徹底解決了UR疊喂最優(yōu)解的問題，且個(gè)人覺得研究思路和故事完整性都十分經(jīng)典，但三貼發(fā)表時(shí)間有先后，比較亂，故本次專欄重新整理匯總了一下，加了更有趣的例題，之前看過的話可以跳過。

1.???? 什么是UR疊喂問題？

????????在Lovelive SIF中，UR的技能等級從1級開始，最高8級封頂。技能等級極大影響到卡組強(qiáng)度，是個(gè)十分重要的指標(biāo)。提升技能等級有且只有兩種方法，一是喂“經(jīng)驗(yàn)卡”，每一等級都有相應(yīng)的經(jīng)驗(yàn)條，喂到相應(yīng)數(shù)目的經(jīng)驗(yàn)卡之后就能升級；二是喂相同的卡，簡稱同卡，喂不同等級的同卡可以一次性獲得數(shù)目不等的大量經(jīng)驗(yàn)值。當(dāng)然，作為獲得經(jīng)驗(yàn)的代價(jià)，喂完之后經(jīng)驗(yàn)卡或者同卡都會(huì)消失。每一級UR升級所需經(jīng)驗(yàn)值，以及作為被喂的對象時(shí)提供的經(jīng)驗(yàn)值如下表所示。

????????以1級為例，1級升2級需要300點(diǎn)經(jīng)驗(yàn)，若將1級卡直接喂給別的同卡，別的同卡可以獲得1000經(jīng)驗(yàn)；2級升3級需要600經(jīng)驗(yàn)，若將2級卡直接喂別的同卡，可以獲得2000經(jīng)驗(yàn)，以此類推。所以，將1級卡升滿到8級，累計(jì)需要29900經(jīng)驗(yàn)。8級之前，超出每一級的溢出經(jīng)驗(yàn)都會(huì)累計(jì)到下一級，但超過8級時(shí)溢出經(jīng)驗(yàn)做浪費(fèi)處理。額外經(jīng)驗(yàn)即為疊喂經(jīng)驗(yàn)-累計(jì)經(jīng)驗(yàn)，指將該等級的卡直接喂給別的同卡時(shí)，其等價(jià)的額外經(jīng)驗(yàn)值。

????????游戲中，同卡可以通過貼紙交換、自選禮包等途徑獲得，并不比經(jīng)驗(yàn)卡更難獲取（直接獲得的同卡都是1級的），因此大部分玩家為了加速升上8級，需要綜合利用同卡和經(jīng)驗(yàn)卡，來疊喂一張UR。此時(shí)，如何最大化利用同卡，成了本專欄研究的課題。

讓我們看幾個(gè)例題：

①???? 某玩家有相同的卡5張（均為1級），需要多少經(jīng)驗(yàn)卡才能喂出一張8級的卡？

????????仔細(xì)觀察表格，會(huì)發(fā)現(xiàn)4級或5級的疊喂效率最高，此時(shí)每同卡等價(jià)經(jīng)驗(yàn)3600。將5張卡中的1張作為底卡，剩下同卡4張，分別用經(jīng)驗(yàn)卡將其喂上4級，然后喂給底卡。這個(gè)過程消耗經(jīng)驗(yàn)卡2400*4，底卡獲得經(jīng)驗(yàn)6000*4=24000經(jīng)驗(yàn)升7級，查表可得，離下一級的經(jīng)驗(yàn)條是5900/12000。剩下不足部分再用經(jīng)驗(yàn)卡補(bǔ)齊，共消耗2400*4+(12000-5900)=15500。

????????故本題答案是需要15500點(diǎn)經(jīng)驗(yàn)卡+4張同卡，才能喂出1張8級卡，相比簡單粗暴直接喂29900點(diǎn)經(jīng)驗(yàn)卡省了近一半。是不是很容易？讓我們看下一題。

②??? 某玩家有相同的卡10張（均為1級），需要多????少經(jīng)驗(yàn)卡才能喂出一張8級的卡？

????????同理，將一張卡作為底卡，剩下同卡9張。如果全部喂上4級，底卡可以獲得6000*9=54000，遠(yuǎn)遠(yuǎn)超出了升滿所需的29900。從表格的額外經(jīng)驗(yàn)一欄可以看出，每張同卡從4級到1級的等價(jià)經(jīng)驗(yàn)是逐漸降低的，所以接著嘗試3級。如果全部喂上3級，底卡獲得4000*9=36000，還有溢出；接著進(jìn)一步調(diào)整喂3級和喂2級的數(shù)目，最終得出，9張同卡中6張喂3級，3張喂2級，共消耗900*6+300*3=6300經(jīng)驗(yàn)，底卡獲得4000*6+2000*3=30000升滿，故該玩家至少需要6300點(diǎn)純經(jīng)驗(yàn)+9同卡才能升滿，如下圖所示。

????????相信絕大部分第一次接觸的玩家都是這個(gè)思路，但真的是這樣嗎？？再仔細(xì)想一想？？

?? ????本題的陷阱在于，疊喂不僅可以一張卡喂到一定等級然后喂給底卡，在同卡數(shù)量遠(yuǎn)高于全部升4疊喂的所需數(shù)量時(shí)，先在同卡之間相互疊喂，然后再喂給底卡，往往比直接將同卡升到2或3級喂給底卡更為效率。例如，我們先給第一張卡喂300經(jīng)驗(yàn)升到2級，然后將該2級卡喂給1張新的1級卡，獲得2000經(jīng)驗(yàn)，再額外補(bǔ)400升到4級，再將4級卡喂給底卡獲得6000經(jīng)驗(yàn)。該方案共消耗2張同卡+700經(jīng)驗(yàn)套取了6000經(jīng)驗(yàn)，而一張升2一張升3同樣套取6000經(jīng)驗(yàn)，消耗300+900=1200經(jīng)驗(yàn)。同理，還可以第一張卡1級直接喂給第二張卡，第二張卡升3后喂給底卡；或者第一張卡升3后喂給第二張卡，第二張卡補(bǔ)經(jīng)驗(yàn)上5后喂給底卡；甚至還可以擴(kuò)展到3張甚至4張互相疊，方案無窮無盡……

????????我們接著看本例題的另兩種方案：

????????方案1即僅考慮一張卡疊喂的方案，消耗經(jīng)驗(yàn)卡6300點(diǎn)；方案2考慮了兩張卡疊喂的方案，消耗經(jīng)驗(yàn)5600點(diǎn)；方案3考慮了3張卡疊喂的方案，消耗經(jīng)驗(yàn)4100點(diǎn)。方案3和最初的方案1相比，節(jié)省了2200點(diǎn)經(jīng)驗(yàn)。那有沒有比方案3更省的方案？怎么證明一個(gè)方案是最優(yōu)的，沒有更優(yōu)？這就是本節(jié)課的內(nèi)容，具體過程較為復(fù)雜。從結(jié)論上來說，方案3已經(jīng)是最優(yōu)了，也許你可以找到一套同樣最優(yōu)的方案，但不可能比它更省，至于為什么是最優(yōu)，怎么求最優(yōu)，讓我們繼續(xù)看下去。

2.???? 整數(shù)線性規(guī)劃、運(yùn)籌學(xué)與Lingo入門

????????若把上題改為，某玩家有相同的卡10張，不考慮多張同卡之間的互相疊喂，僅考慮將單張同卡升到一定等級后直接喂給底卡，則需多少經(jīng)驗(yàn)卡才能喂出一張8級？上一節(jié)中，我們通過人工湊出了答案。如果用規(guī)范的數(shù)學(xué)語言來表示，則需先設(shè)變量：我們假設(shè)1級直接喂w張，升到2級喂x張，3級y張，4級z張。如果喂5級需要5400經(jīng)驗(yàn)+1同卡，獲得經(jīng)驗(yàn)9000點(diǎn)，和喂4級2400經(jīng)驗(yàn)獲得6000點(diǎn)再額外補(bǔ)3000點(diǎn)純經(jīng)驗(yàn)一致，也就是說，前者和后者完全等價(jià)，完全可以被后者替代，故不考慮為5級。具體變量如下表所示。

溢出時(shí)有：

未溢出時(shí)有：

????????其中，s.t.指限制條件，min=指求該式的最小值。我們需要在滿足限制條件的情況下，得出最小值具體的值，以及此時(shí)各變量的取值。對比溢出和未溢出，取最小即為我們需要的值。

????????像這種，在所有式子都是線性的情況下的求最值問題稱為線性規(guī)劃，屬于運(yùn)籌學(xué)及應(yīng)用數(shù)學(xué)的范疇。本題所有變量都是整數(shù)，又稱整數(shù)線性規(guī)劃，最常用的軟件為lingo。打開Lingo軟件，選擇demo，參照下圖格式輸入上圖的不等式組：

????????注意，每一行之間必須有分號，包括最后一行；一定要英語格式輸入各種符號；數(shù)字和變量間的乘號不能省略。Lingo軟件默認(rèn)所有變量都是大于等于0的，但不一定整數(shù)，因此需要輸入@gin()，表示括號里面的變量是整數(shù)。輸完后，點(diǎn)擊上面的靶標(biāo)求解，然后會(huì)跳出來結(jié)果：

????????黑框的variable指最優(yōu)化時(shí)各變量的取值，紅框的global opt指全局最優(yōu)，意為該結(jié)果可信，是最優(yōu)解。Objective指該情況下最值的取值。本題得6300，具體為x=3，y=6，即2級3次，3級6次。同理，非溢出情形得6900，w=1，x=2，y=6，再補(bǔ)900經(jīng)驗(yàn)，不如溢出方案。

????????Lingo背后的原理為單純形法，其時(shí)間復(fù)雜度僅為O（n），就算變量和限制條件非常多也能秒算。具體原理筆者也不甚了解，我們僅需通過這個(gè)例子知道，只要你能把不等式列出來，就能通過Lingo輕松秒算最優(yōu)解。就算不是線性規(guī)劃，涉及分?jǐn)?shù)、平方等運(yùn)算時(shí)，也能用Lingo來做，此時(shí)可能出現(xiàn)“局部最優(yōu)”，不一定是“全局最優(yōu)”。

????????本題我們將溢出和非溢出分別列式，計(jì)算最優(yōu)后再人為比較。Lingo也可以輸入語句將兩者合并到一個(gè)模型中，不過為了講解直觀，我們下文還是分開算。Lingo的詳細(xì)使用可以參考關(guān)于數(shù)學(xué)建模的課程和書籍，有非常多功能選項(xiàng)，本節(jié)課涉及的整數(shù)線性規(guī)劃僅為最基礎(chǔ)部分。

3.???? 基本疊喂方案的確立

3.1 一階疊喂基本方案

????????看完上一節(jié)，你可能會(huì)問，搞這么復(fù)雜，得出的結(jié)論和湊得不是一樣嗎？不要急，我們一步步來。我們把一次消耗幾張卡，就稱為幾階疊喂，上一節(jié)中，我們已經(jīng)得出了一階疊喂的四個(gè)基本方案：

????????5級疊喂和4級疊喂再額外加3000經(jīng)驗(yàn)完全等價(jià)，前者完全可以被后者替代，后者還更靈活，因此5級方案根本不用考慮，6級以上同理（低階方案+純經(jīng)驗(yàn)甚至可以更強(qiáng)）。我們把這些不可替代的方案稱為基本方案。

3.2 二階疊喂基本方案

????????然后，我們通過一階方案推導(dǎo)二階方案。二階方案只有一種可能：第二張卡把第一張卡吃了，再把第二張卡喂給底卡。決定底卡獲得多少經(jīng)驗(yàn)的僅僅只是第二張卡的等級，與它是如何吃的，怎么喂的無關(guān)。一張1級卡直接喂可以提供1000經(jīng)驗(yàn)，使第二張卡升到3級，因此二階方案至少從3級起步。如果我們想通過二階方案獲得一張3級的卡，再將3級卡喂給底卡，則最佳方案肯定是將1級卡直接喂給第二張1級卡升3（因?yàn)榇藭r(shí)消耗的經(jīng)驗(yàn)是0），記為1-3。如果我們想通過二階方案獲得1張4級的卡呢？同第二節(jié)，我們不計(jì)算把一張卡升到8，我們只算將其升到4（累計(jì)經(jīng)驗(yàn)2400）的，最省經(jīng)驗(yàn)的喂法。

溢出時(shí)有：

未溢出時(shí)有：

????????解得，最佳方案為未溢出方案，x=1，min=700。先將第一張喂300經(jīng)驗(yàn)升到2級后，喂給第二張卡，獲得2000經(jīng)驗(yàn)再補(bǔ)400經(jīng)驗(yàn)正好升4，然后將四級卡喂給底卡，我們將其記作2-4。整個(gè)過程消耗700經(jīng)驗(yàn)+2同卡，套取6000經(jīng)驗(yàn)。

????????同理，把上述不等式的具體數(shù)字改一改，我們繼續(xù)計(jì)算5級：用兩張卡倒騰出一張5級的最省經(jīng)驗(yàn)方案是未溢出方案，y=1，先將第一張喂900經(jīng)驗(yàn)升到3級后，喂給第二張卡，獲得4000經(jīng)驗(yàn)再補(bǔ)1400經(jīng)驗(yàn)正好升5，然后將5級卡喂給底卡，我們將其記作3-5。整個(gè)過程消耗2300經(jīng)驗(yàn)+2同卡，套取9000經(jīng)驗(yàn)。

????????6級時(shí)，最省經(jīng)驗(yàn)方案是未溢出方案，z=1，先將第一張喂2400經(jīng)驗(yàn)升到4級后，喂給第二張卡，獲得6000經(jīng)驗(yàn)再補(bǔ)4400經(jīng)驗(yàn)正好升6，然后將5級卡喂給底卡，我們將其記作4-6。整個(gè)過程消耗6800經(jīng)驗(yàn)+2同卡，套取12000經(jīng)驗(yàn)。但是，4-6完全可以被2-4再額外加6000經(jīng)驗(yàn)替代，后者同樣套取12000經(jīng)驗(yàn)，僅消耗6700經(jīng)驗(yàn)+2同卡。因此4-6不是二階疊喂的基本方案。7級時(shí)同理，我們整理得下表：

3.3?? 三階疊喂基本方案

????????我們繼續(xù)看三階疊喂，即如何在三張同卡之間倒騰，用最少的經(jīng)驗(yàn)卡得出一張恒定等級的同卡。三階不同于兩階，它有兩種可能：一是把第一張卡和第二張卡分別喂給第三張。二是先將第一張喂給第二張，再將第二張喂給第三張。前者對應(yīng)的是兩個(gè)一階方案的線性組合，后者對應(yīng)的是一個(gè)兩階方案,我們只需將之前得到的一階和二階基本方案作為備選，更新不等式，即可將這兩種情況全部囊括在內(nèi)，以5級為例：

溢出時(shí)有：

未溢出時(shí)有：

????????解得溢出方案最優(yōu)，j=1，min=700。即先將第一張卡喂300經(jīng)驗(yàn)到2級，再將其喂給第二張卡獲得2000經(jīng)驗(yàn)補(bǔ)400升4級，再將第二張卡喂給第三張卡，獲得6000經(jīng)驗(yàn)直接升5級，最后喂給底卡獲得9000經(jīng)驗(yàn)，整個(gè)過程消耗700經(jīng)驗(yàn)+3張同卡，套取9000經(jīng)驗(yàn)，記作2-4-5。同理，計(jì)算4級、6級的情形，并排除可以被替代的方案，整理得下表：

3.4 ? 更高階疊喂基本方案

????????我們繼續(xù)把一二三階的基本方案作為備選，更新不等式，來看看四階的基本方案。不管四張卡怎么倒騰成一張，要么是3個(gè)1階，要么是1個(gè)2階一個(gè)1階，要么一個(gè)三階，全部都被囊括在內(nèi)了。然后再將四階的基本方案納入備選，計(jì)算五階，以此類推，具體過程省略，得下表：

????????9階方案終于做到了0經(jīng)驗(yàn)套取一張7級卡，然并卵，都完敗其他方案組合，不能上榜。更高階方案想要?jiǎng)俪觯瑒荼匾?級才行。然而都到8級了還喂個(gè)啥……

????????因此，四階及更高階方案中，有且只有一種基本疊喂方案：1-3-4-5。將第一張卡直接喂給第二張，獲得1000經(jīng)驗(yàn)升3級，再繼續(xù)喂給第三張，獲得4000經(jīng)驗(yàn)升4級，繼續(xù)喂給第四張，獲得6000經(jīng)驗(yàn)升5級，最后將五級卡喂給底卡，消耗0經(jīng)驗(yàn)+4同卡套取9000經(jīng)驗(yàn)。

3.5 ? 基本疊喂方案總表

我們匯總上述基本方案到一張表內(nèi)，得：

????????無論怎么去疊，只要是最求最省經(jīng)驗(yàn)的方案，就一定是這張表的線性組合，出不了這張表的范圍，這就是基本疊喂方案的定義。UR疊喂的基本方案有且只有十種，如上表所述。具體原因我們本節(jié)已經(jīng)進(jìn)行了充分論證。

（準(zhǔn)確的說，只要是最求最省經(jīng)驗(yàn)的方案，這張表的線性組合一定可以解決問題。也許你可以找到不在表內(nèi)的方案同樣最優(yōu)，但不會(huì)找到更優(yōu)的）

4.???? UR疊喂方案表

4.1 常規(guī)UR疊喂方案表

????????有了基本疊喂方案表，再看一開始的例題，就很容易了。只需依葫蘆畫瓢，將十個(gè)變量全部加入不等式即可。解得溢出方案更優(yōu)，y=3，m=2，min=4100，即方案3為最優(yōu)方案，不可能更優(yōu)。我們根據(jù)同樣方法，計(jì)算得到下表：

????????套即為-的意思，可以看到，在同卡數(shù)多的最佳方案中，會(huì)涉及大量的“套娃方案”，單純的僅用一階方案的組合會(huì)損失大量經(jīng)驗(yàn)。

4.2 可換位的UR疊喂大表

????????在貼吧發(fā)布這個(gè)結(jié)論后，有吧友指出，如果我手上有一張4級0經(jīng)驗(yàn)的卡和5張1級同卡，如果按上表最佳方案的3*4+(3-5)+500，需要消耗1w經(jīng)驗(yàn)。如果我直接將1級同卡做底卡，將其他卡升到4級直接喂上去，只需9600，不過僅限于未覺醒（或自帶覺醒）且沒開槽。筆者通過對不等式進(jìn)行了一些調(diào)整，加入換位后的策略，得到了可換位的大表，標(biāo)注換位的指該情況下通過換位可以更省經(jīng)驗(yàn)：

在十種基本疊喂方案之外，具體添加的策略：

????????換位后的高階策略是我手動(dòng)列的，不是嚴(yán)格一階階推導(dǎo)的，不排除有遺漏，不過我感覺應(yīng)該不會(huì)。我們也可以通過同樣的方法制作“必須換位的大表”，用于簽名卡的疊喂升級問題……

????????至此，我們已經(jīng)解決了普通UR的疊喂問題。只要給出到8級缺少的經(jīng)驗(yàn)值和同卡數(shù)，就能輕松秒算最優(yōu)方案。

5.???? 雙人UR疊喂問題

????????雙人卡是近一年來游戲新出的一種卡，和普通UR不同，它的特點(diǎn)是分A卡和B卡，A、B卡的卡面、屬性、技能均不同。玩家抽卡時(shí)無法決定抽到A還是B，完全是隨機(jī)的。A、B卡可以通過消耗一個(gè)轉(zhuǎn)換幣互相轉(zhuǎn)換，轉(zhuǎn)換后技能等級、當(dāng)前經(jīng)驗(yàn)等全都不變。每個(gè)轉(zhuǎn)換幣需要約近十小時(shí)的肝力才能得到，屬于游戲內(nèi)的珍稀資源之一。因此，例如某玩家想養(yǎng)A卡但不想養(yǎng)B卡，抽了10次box，出A卡3張B卡7張，如何在最節(jié)省轉(zhuǎn)換幣和純經(jīng)驗(yàn)下疊喂成了新的課題。

????????本節(jié)做的基本假設(shè)是，雙人卡中一張想練，另一張不想練只是作為疊喂材料，且去除底卡后A、B卡都有抽到的最優(yōu)疊喂方案。我們把想練的卡稱為同側(cè)卡，不想練的卡稱為對側(cè)卡。我們先看兩個(gè)公理（因?yàn)橐谎劬陀X得是對的，不需要也不會(huì)證明，所以就稱公理了）：

?

公理1：想要對雙人卡疊喂，至少需要1個(gè)轉(zhuǎn)換幣。如果不消耗任何轉(zhuǎn)換幣，不可能用對側(cè)的卡來喂同側(cè)的卡。

公理2：相同同卡數(shù)（雙人卡同卡數(shù)指去除底卡后同側(cè)對側(cè)卡數(shù)之和）下，雙人卡疊喂的最優(yōu)方案所需的最小經(jīng)驗(yàn)數(shù)不可能小于普U疊喂方案表。這很容易理解，因?yàn)殡p人卡和普U疊喂比多了更多的限定條件，只可能比普U更多，不可能更省。

?

????????基于以上兩點(diǎn)，我們就能解決絕大部分情況下的雙人卡疊喂最優(yōu)方案問題。

????????我們先假設(shè)一種雙人卡的疊喂流程：將對側(cè)任意一張卡作底卡，將對側(cè)同卡疊喂完之后轉(zhuǎn)換為同側(cè)，再疊喂同側(cè)同卡到滿。以雙人卡抽到了同側(cè)卡3張，對側(cè)卡5張為例。將對側(cè)卡作為底卡后，剩同側(cè)3對側(cè)4共7同卡。查普U最佳疊喂方案表，7同卡方案為3*3+2*(3-5)。觀察該方案，一階疊喂3個(gè)，二階2個(gè)。我們先將兩個(gè)二階先疊給對側(cè)，把對側(cè)同卡耗完，然后轉(zhuǎn)換幣轉(zhuǎn)到同側(cè)，再繼續(xù)用同側(cè)卡疊三個(gè)一階。這樣下來，和普U疊喂方案比，僅多消耗一個(gè)轉(zhuǎn)換幣，最小經(jīng)驗(yàn)完全一致?；诠?,2，因此認(rèn)為這就是最優(yōu)方案。

????????如果7同卡不是同側(cè)3對側(cè)4，而是其他組合，你會(huì)發(fā)現(xiàn)，仍然可以拆。例如2和5，則對側(cè)疊三個(gè)一階一個(gè)兩階，轉(zhuǎn)換后繼續(xù)疊一個(gè)兩階。縱觀普U疊喂方案表，1-9卡的疊喂方案，不論同對側(cè)卡數(shù)具體是多少，都可以完全拆干凈。10-14卡的疊喂方案中，除個(gè)別同對側(cè)數(shù)字組合沒法拆干凈以外，大部分也都可以完全拆成對側(cè)和同側(cè)，分別疊喂即可。

????????然后，我們對這些沒法拆干凈的數(shù)字組合單獨(dú)拿出來研究。它們?nèi)缦卤硭荆?/p>

????????對于上表情況，我們無法將其完全拆成對側(cè)和同側(cè)兩部分。例如10卡的方案由2個(gè)2階和2個(gè)3階構(gòu)成，無論怎么組合都絕對組不出1。14卡方案由2個(gè)4階2個(gè)2階組成，偶數(shù)無論怎么加也不可能加出奇數(shù)。我們繼續(xù)對這部分的最優(yōu)方案論證。如果考慮消耗多個(gè)轉(zhuǎn)換幣來疊喂的情況會(huì)比較復(fù)雜，我們先考慮僅消耗一個(gè)轉(zhuǎn)換幣的情況。

?

公理3：在雙人卡疊喂問題中，如果僅打算消耗一個(gè)轉(zhuǎn)換幣，則僅有將對側(cè)卡作為底卡，并疊喂完對側(cè)卡所有同卡后轉(zhuǎn)換至同側(cè)，然后疊喂同側(cè)卡的流程才能用滿所有同卡。我們把這個(gè)流程稱為雙人卡基本疊喂流程。

?

????????公理3很容易理解，我需要的是同側(cè)卡不是對側(cè)卡，僅有一個(gè)轉(zhuǎn)換幣不可能把同側(cè)轉(zhuǎn)對側(cè)，肯定對側(cè)轉(zhuǎn)同側(cè)。如果沒有把對側(cè)卡疊完就轉(zhuǎn)同側(cè)了，那剩下的對側(cè)卡就用不上了。值得說明的是，這里的同卡指的是去除底卡后的同卡，如果對側(cè)卡僅1張時(shí)，將該卡作為底卡后，對側(cè)卡剩0，直接轉(zhuǎn)換至同側(cè)后處理，只是描述上和“把同側(cè)卡當(dāng)?shù)卓ǎ缓笪ㄒ灰粡垖?cè)卡轉(zhuǎn)過來疊喂”不同，實(shí)質(zhì)是一樣的，仍然符合公理3。

????????基于公理3，我們繼續(xù)研究這個(gè)雙人卡基本疊喂流程。這個(gè)流程和普U疊喂流程相比，分為兩部分：第一部分是對側(cè)疊喂，第二部分是同側(cè)疊喂。普U的最優(yōu)方案是基于基本疊喂方案的整數(shù)線性規(guī)劃得出的，同理，我們可以分別對對側(cè)和同側(cè)兩部分行整數(shù)線性規(guī)劃得到最優(yōu)解。但問題是我不知道兩部分的分界線是哪里，雖然可以把對側(cè)同卡數(shù)所對應(yīng)的所有基本方案的組合都試一遍，找出兩部分相加最小的方案，但過于繁瑣，可以肯定的是，這兩部分所用到的疊喂方案肯定不會(huì)超過基本疊喂方案表。整理得推論1：

?

推論1：雙人卡基本疊喂流程是僅用一個(gè)轉(zhuǎn)換幣的雙人卡疊喂的唯一流程，其用到的具體疊喂方案仍然在基本疊喂方案表范疇內(nèi)。

?

????????有了推論1，問題就可以繼續(xù)往前推進(jìn)了。我們只需在普U的多同卡疊喂的整數(shù)線性規(guī)劃時(shí)，額外對一、二、三、四階方案的個(gè)數(shù)進(jìn)行限制即可。例如，一個(gè)疊喂方案如果能拆出1，它肯定得有至少一個(gè)一階方案，此時(shí)我只需額外加入不等式：所有一階方案之和≥1（w+x+y+z≥1）即可；如果不是1而是4，則稍微有些復(fù)雜。4可以且僅可被拆為1111,112,22,13,4任意一種，他們需要額外增加的不等式分別是w+x+y+z≥4，w+x+y+z≥2&i+j+k≥1，i+j+k≥2，w+x+y+z≥1&m+n≥1，o≥1。分別對這五種情況算出各自的最優(yōu)方案，比較后得出五種情況的總最優(yōu)方案即為該情況下的最優(yōu)方案。其他同理。對上表非1的情況總結(jié)得下表：

整理上表和未列在表上的拆1方案，得到了雙人卡最優(yōu)疊喂方案大表：

????????然而，公理3是基于僅用一次轉(zhuǎn)換幣的。該表僅保證了在消耗一個(gè)轉(zhuǎn)換幣的時(shí)候最優(yōu)，不能保證消耗多個(gè)轉(zhuǎn)換幣會(huì)不會(huì)更優(yōu)。但是，通過這張表我們可以很清晰的看出，即使是沒法被完整拆分的同/對側(cè)卡數(shù)，基于公理2，其經(jīng)驗(yàn)損失僅為2-300，遠(yuǎn)低于一個(gè)轉(zhuǎn)換幣的成本。如果玩家愿意多花轉(zhuǎn)換幣減少經(jīng)驗(yàn)損耗，上表中的特殊數(shù)字組合并沒有連續(xù)，僅需提前將任意一張同或?qū)?cè)卡轉(zhuǎn)換后，即可直接按照無損的方案進(jìn)行。所以，綜上所述，我們論證了該表格就是雙人卡同卡疊喂的最優(yōu)方案表。

6.???? 組合疊喂問題

至此，我們已經(jīng)解決了單張UR的疊喂問題。Lingo不僅能算單張疊喂，還能算多張疊喂的組合策略，我們看幾個(gè)例題：

①小明手上有1級UR、5級UR、7級UR各一張，彩貼28張（假設(shè)可以全部換到14張任選的同卡，不考慮三換一或高階疊喂時(shí)產(chǎn)生的余數(shù)），求將他們?nèi)可?所需的最小純經(jīng)驗(yàn)數(shù)。

????????我們回顧之前的大表，1級UR有14種喂法，5級UR有12種喂法，7級UR有6種喂法，分別將其設(shè)為x1-x14，y1-y12，z1-z6。若x1=1，代表使用1張同卡+23900經(jīng)驗(yàn)將1級UR疊滿；若y12=1，代表使用12張同卡+0經(jīng)驗(yàn)將5級UR疊滿，以此類推。由于同卡數(shù)明顯多于全部4級疊喂需要的數(shù)目，因此出于簡便，不對需要消耗同卡數(shù)過少的情況建模。

則有：

lingo界面截圖（截圖省略@gin限定所有變量為整數(shù)的部分）：

????????解得x7=1，y5=1，z2=1，其余均為0，min=19600。其含義是1級UR通過3*3+2*(3-5)方案，5級UR通過4+2*(3-5)+500方案，7級UR通過2*4方案，各自疊到8級，最小消耗經(jīng)驗(yàn)為19600。計(jì)算又快又準(zhǔn)，Lingo是不是非常實(shí)用？

②???? 小明手上有1級UR（紅色）、5級UR（綠色）、7級UR（藍(lán)色）各一張，紅色經(jīng)驗(yàn)4000點(diǎn)，綠色經(jīng)驗(yàn)3000點(diǎn)，藍(lán)色經(jīng)驗(yàn)4000點(diǎn)，紫色經(jīng)驗(yàn)6000點(diǎn)，求若將所有UR全升到8，所需換的最少同卡數(shù)。

????????游戲中，同色經(jīng)驗(yàn)只能喂給同色UR，不能喂給異色，紫色可以通用，隨意喂給三色。這題比上一題增加了經(jīng)驗(yàn)數(shù)的細(xì)化。同樣，我們設(shè)x5-x14，y4-y12，z2-z6為各自方案的數(shù)目，另設(shè)中間變量p1、p2、p3分別代表紅色UR、綠色UR、藍(lán)色UR吃到的紫色經(jīng)驗(yàn)數(shù)。為表達(dá)簡便，我們設(shè)f(n)為x5-14各自對應(yīng)的消耗經(jīng)驗(yàn)數(shù)的映射，g(n)為y4-12各自對應(yīng)的消耗經(jīng)驗(yàn)數(shù)的映射，h(n)為z2-6各自對應(yīng)的消耗經(jīng)驗(yàn)數(shù)的映射，則有：

Lingo截圖（同省略整數(shù)定義部分）：

????????解得x8=1，y6=1，z2=1，min=16。意味著1級紅UR通過3*3+(3-5)+(2-4-5)方案，消耗4000紅經(jīng)驗(yàn)+1700紫經(jīng)驗(yàn)升滿；5級綠UR通過2*(3-5)+(2-4)+500方案，消耗3000綠經(jīng)驗(yàn)+2800紫經(jīng)驗(yàn)升滿；7級藍(lán)UR通過2*4方案，消耗4000藍(lán)經(jīng)驗(yàn)+800紫經(jīng)驗(yàn)升滿。至少需要換16張同卡。

????????但是??！Lingo只能給出目標(biāo)方程最小的一個(gè)解。如果目標(biāo)方程有多個(gè)解同樣最小時(shí)，就需要自己手動(dòng)的通過修改條件或增加不等式來試了。我們這邊通過修改紫色經(jīng)驗(yàn)總和，使其不斷往下降，看看降到什么時(shí)候會(huì)從16跳到17，會(huì)不會(huì)存在換同卡數(shù)相同，但可以更省經(jīng)驗(yàn)的組合方案。

????????最終解得，5300紫經(jīng)驗(yàn)是極限。方案為x7,y7,z2=1。消耗的總經(jīng)驗(yàn)和x8,y6,z2=1一致，均為16300。兩種方案都是可行的。雖然題設(shè)給了6000經(jīng)驗(yàn)，但可以省下700不會(huì)用上。

?

????????這種通過在不等式中加入中間變量的做法十分常用，需要掌握。

③??? 某雙人卡同側(cè)卡為pp，對側(cè)卡為cf。小紅抽了34張pp，31張cf，想疊喂成滿級的pp卡5張，cf卡2張。請幫他設(shè)計(jì)一套最省經(jīng)驗(yàn)及轉(zhuǎn)換幣的疊喂方案。

????????本題去除底卡后，不含底卡的同卡共34+31-7=58張，pp/cf=29/29張。無論如何疊喂都可以歸為三類：pp卡內(nèi)部疊，不帶cf，變量設(shè)為xn；cf卡內(nèi)部疊，變量設(shè)為yn；pp/cf按雙人卡疊喂規(guī)則一起疊，變量設(shè)為zn。和前兩題一樣， n代表疊喂的張數(shù)。比如說，按照7同卡疊喂的最佳方案疊一次（查普UR疊喂表，最佳方案是3*3+2*(3-5)，消耗純經(jīng)驗(yàn)7300+7同卡喂?jié)M），即x7=1。理論上來說n∈[1-14]，但為簡便，我們不對明顯不合理的疊喂方案建模，x的n取4-10，yz的n取4-14。同樣，設(shè)f(n)為xn，yn，zn各自對應(yīng)的消耗純經(jīng)驗(yàn)的映射（三者的映射完全一致，嚴(yán)格來說z10-z14需要分情況討論，不過我們先不管，這題后續(xù)也沒碰到?jīng)]法拆干凈的情況）。由題意，pp/cf同卡數(shù)量差不多，而需要的8級pp遠(yuǎn)多于cf，因此轉(zhuǎn)換幣要么cf/pp一起疊消耗一個(gè)，要么cf內(nèi)部疊完消耗一個(gè)轉(zhuǎn)成8級pp，不可能是pp疊滿8級再轉(zhuǎn)cf。因此轉(zhuǎn)換幣數(shù)目=sum yn+sum zn-2。

所設(shè)變量如下表所示：

有：

Lingo截圖：

????????我們先設(shè)轉(zhuǎn)換幣為1，解得x7=3，x8=1，y9=1，y10=2，min=37300。即pp內(nèi)部3個(gè)7疊1+1個(gè)8疊1，cf內(nèi)部2個(gè)10疊1+1個(gè)9疊1，最后一張8級PP轉(zhuǎn)CF即可。若假設(shè)轉(zhuǎn)換幣為2，解得pp內(nèi)部1個(gè)7疊1+2個(gè)8疊1，cf內(nèi)部3個(gè)9疊1，剩pp/cf=6/2，混搭后按雙人卡疊喂方案8疊1。共消耗純經(jīng)驗(yàn)36700，轉(zhuǎn)換幣2個(gè)，一個(gè)用于混搭疊喂，另一個(gè)用于CF轉(zhuǎn)PP。假設(shè)轉(zhuǎn)換幣為3或以上時(shí)，最小消耗純經(jīng)驗(yàn)不再變化。具體n疊1怎么操作可以查看之前的大表，這里不再復(fù)述。故本題最優(yōu)解是37300經(jīng)驗(yàn)+1轉(zhuǎn)換幣。

7.???? 思考題

這次思考題出的容易一些吧，組合疊喂問題有點(diǎn)太難了，第六節(jié)就當(dāng)例題展示了。

①? 簽名卡疊喂問題

????????小剛手上有一張4級的UR，最近通過簽名卡池，又抽到了7張同卡，其中1張簽名卡。即手上有1張1級的簽名U+1張4級同卡+6張1級同卡。請幫他設(shè)計(jì)一套最省經(jīng)驗(yàn)的疊喂方案，使簽名卡喂上8級。

????????估計(jì)看到這兒的都是玩游戲的不會(huì)有純粹學(xué)數(shù)學(xué)的了，以防萬一還是介紹一下，必須將簽名U作為底卡，將其他卡喂給它。和之前唯一不同的是，前面我們算的都是1級的同卡，這次同卡里面混了一張4級的，基本方案會(huì)有所改變。

（這題要算的話有點(diǎn)麻煩，但可以直接查之前的表，看會(huì)不會(huì)活用大表）

②? SSR疊喂問題

????????隨著自選SSR券的不斷增多，SSR同卡疊喂也不再是不可能。已知SSR的經(jīng)驗(yàn)表格如下所示，求SSR疊喂的基本方案。

全文到此結(jié)束，撒花，希望能給運(yùn)籌學(xué)的基本思路做一個(gè)科普吧，專欄參加不了游戲知識的限時(shí)活動(dòng)有點(diǎn)可惜。UP主也不是學(xué)理工科的，很多數(shù)學(xué)的東西是好奇然后查了用，試著摸索著就會(huì)了。不知道有沒有人看完的，歡迎評論、提問、指正~