一、題目

?????? 小明幾乎每天早晨都會(huì)在一家包子鋪吃早餐。他發(fā)現(xiàn)這家包子鋪有N種蒸籠，其中第i種蒸籠恰好能放Ai個(gè)包子。每種蒸籠都有非常多籠，可以認(rèn)為是無限籠。每當(dāng)有顧客想買X個(gè)包子，賣包子的大叔就會(huì)迅速選出若干籠包子來，使得這若干籠中恰好一共有X個(gè)包子。比如一共有 3 種蒸籠，分別能放 3、4 和 5 個(gè)包子。當(dāng)顧客想買 11 個(gè)包子時(shí)，大叔就會(huì)選 2 籠 3 個(gè)的再加 1 籠 5 個(gè)的（也可能選出 1 籠 3 個(gè)的再加 2 籠 4 個(gè)的）。當(dāng)然有時(shí)包子大叔無論如何也湊不出顧客想買的數(shù)量。比如一共有 3 種蒸籠，分別能放 4、5 和 6 個(gè)包子。而顧客想買 7 個(gè)包子時(shí)，大叔就湊不出來了。小明想知道一共有多少種數(shù)目是包子大叔湊不出來的。
??????? 如果湊不出的數(shù)目有無限多個(gè)，輸出 INF。

二、數(shù)學(xué)知識(shí)前提

裴蜀定理：

??????? 對(duì)任何整數(shù)a、b和它們的最大公約數(shù)d，關(guān)于未知數(shù)x和y的線性不定方程（稱為裴蜀等式）：若a,b是整數(shù),且gcd(a,b)=d，那么對(duì)于任意的整數(shù)x,y,ax+by都一定是d的倍數(shù)，特別地，一定存在整數(shù)x,y，使ax+by=d成立。

?????? 該定理也可以拓展到多個(gè)整數(shù)。同時(shí)在本題中要求如果湊不出的數(shù)目有無限多個(gè)，輸出 INF。由定理可知，對(duì)于幾個(gè)整數(shù)組合來說，他們能夠組合出來的數(shù)一定是d的倍數(shù)，如果這個(gè)d是1，那么在此基礎(chǔ)上能組合出任意數(shù)（當(dāng)然由于x，y在本題中也是整數(shù)，所以還是有組合不出來的數(shù)），反之則只能組合出d的倍數(shù)，即有無限個(gè)湊出來的數(shù)

三、解題思路

?????? 題目是有N個(gè)包子籠來組合，是一個(gè)完全背包的變種，所以用完全背包來做，首先檢測是否有無限個(gè)湊不出來的，即采用最大公約數(shù)來檢測。為了方便理解，存儲(chǔ)籠子數(shù)組A[i]時(shí)多加一個(gè)并將A[0]棄用，這樣i就代表第i種籠子。dp[i][j]數(shù)組采用bool類型，用來表示能否湊出來，行數(shù)為籠子種類數(shù)，列數(shù)盡量多，設(shè)為10000，代表需求的包子數(shù)。

四、狀態(tài)轉(zhuǎn)移

初始的時(shí)候全部為0（false），并且易知在沒有任何籠子的時(shí)候，什么數(shù)也拼不出來，即i=0時(shí)的那一行全部為0，而且在需求為0的情況下，全都可以湊出來，即j=0那一列全為true（dp[0][0]=true）.

打出表來，分析可知一種情況是在上一行已經(jīng)可以拼出來的情況，此時(shí)在這一行也可以拼出來。還有一種情況是上一行拼不出來，這時(shí)如果在第j列(即需求j個(gè)包子)的情況下減去k倍（k=1，2，3......）這一行代表的籠子包子數(shù)（A[i]）可以湊出來那么這個(gè)情況下也可以湊出來。方程表達(dá)為

由于dp[i][j-A[i]]=dp[i][j-2A[i]]······dp[i][j-kA[i]]，可以發(fā)現(xiàn)后面的式子都可以這樣表示，即如果dp[i][j-A[i]]可以，那后面的式子中至少有一個(gè)可以，如果dp[i][j-A[i]]不可以，那么后面式子也不必考慮，必定都不可以，所以可以化簡為

還有就是j-A[i]<0時(shí)，那肯定是false，綜合起來代碼如下

上述是我自己的理解，但是感覺還有點(diǎn)不對(duì)勁，所以我再寫一個(gè)別人寫的理解方式，比較偏向證明。

因?yàn)轫樞蜓h(huán)，在本行執(zhí)行dp時(shí)，上一行已經(jīng)完成，所以本行dp[i][j]可表示為如下

另外由于

觀察上述兩式可發(fā)現(xiàn)有重疊，所以可得

綜合起來代碼與剛才一樣。

dp完成之后，就可以在行數(shù)為N的那一行循環(huán)數(shù)出false的個(gè)數(shù)即為答案。

五、完整代碼

六、出現(xiàn)問題

對(duì)于動(dòng)態(tài)規(guī)劃、01背包，完全背包還是不太理解，需要繼續(xù)強(qiáng)化。

七、參考資料