河南省專(zhuān)業(yè)做網(wǎng)站公司長(zhǎng)沙專(zhuān)業(yè)競(jìng)價(jià)優(yōu)化公司
題目描述:
小明幾乎每天早晨都會(huì)在一家包子鋪吃早餐。
他發(fā)現(xiàn)這家包子鋪有?N?種蒸籠,其中第?i?種蒸籠恰好能放?Ai 個(gè)包子。
每種蒸籠都有非常多籠,可以認(rèn)為是無(wú)限籠。
每當(dāng)有顧客想買(mǎi)?X?個(gè)包子,賣(mài)包子的大叔就會(huì)迅速選出若干籠包子來(lái),使得這若干籠中恰好一共有?X?個(gè)包子。
比如一共有?3?種蒸籠,分別能放?3、4和?5?個(gè)包子。
當(dāng)顧客想買(mǎi)?11個(gè)包子時(shí),大叔就會(huì)選?2?籠?3?個(gè)的再加?1?籠?5?個(gè)的(也可能選出?1?籠?3?個(gè)的再加?2?籠?4?個(gè)的)。
當(dāng)然有時(shí)包子大叔無(wú)論如何也湊不出顧客想買(mǎi)的數(shù)量。
比如一共有?3?種蒸籠,分別能放?4、5和?6?個(gè)包子。
而顧客想買(mǎi)?7?個(gè)包子時(shí),大叔就湊不出來(lái)了。
小明想知道一共有多少種數(shù)目是包子大叔湊不出來(lái)的。
輸入格式:
第一行包含一個(gè)整數(shù)?N。
接下來(lái)?N?行,每行包含一個(gè)整數(shù)?Ai。
輸出格式:
輸出一個(gè)整數(shù)代表答案。
如果湊不出的數(shù)目有無(wú)限多個(gè),輸出INF。
數(shù)據(jù)范圍:
1≤N≤100,
1≤Ai≤100
輸入樣例1:
2
4
5
輸出樣例1:
6
輸入樣例2:
2
4
6
輸出樣例2:
INF
樣例解釋
對(duì)于樣例1,湊不出的數(shù)目包括:1, 2, 3, 6, 7, 11。
對(duì)于樣例2,所有奇數(shù)都湊不出來(lái),所以有無(wú)限多個(gè)。
前情提要:這道題目有關(guān)完全背包,01背包這兩道題目,如果沒(méi)看過(guò)這兩道題目的題解大家可以去看看,能幫助理解這道題目。鏈接我也放到這里了,點(diǎn)擊鏈接就行。
分析步驟:
? 第一:看到題目我們就能明白,每一籠包子是可以選無(wú)數(shù)多籠的,只要次數(shù)不超過(guò)我們指定的個(gè)數(shù),看看能組合出多少種組合來(lái),最后判斷一下有多少個(gè)數(shù)組合出來(lái)了,多少個(gè)數(shù)沒(méi)有組合出來(lái)那么這就是答案。由此可以得出第一個(gè)特點(diǎn):題目是?組合問(wèn)題,是完全背包問(wèn)題的變形:有幾個(gè)物品,每個(gè)物品無(wú)限個(gè),每個(gè)物品選任意個(gè),能否湊到某個(gè)重量。
? 第二:我們?nèi)绾?span style="color:#fe2c24;">判斷這個(gè)題目是否有無(wú)數(shù)個(gè)值會(huì)組合不出來(lái)呢?我們想一下什么樣的就組合不出來(lái),例如2,4,6最大公約數(shù)是2所以奇數(shù)組合不出來(lái),因?yàn)樗荒芙M合出gcd的倍數(shù)。例如30,60最大公約數(shù)是30,所以只要不是30的倍數(shù)的就一定組合不出來(lái),由此我們可以發(fā)現(xiàn)一些問(wèn)題組合數(shù)和gcd有關(guān),只要gcd不是1的話(huà)那么它就有無(wú)數(shù)種數(shù)組合不出來(lái)。這里用到裴蜀定理 ,任意兩個(gè)數(shù)的組合必定是他們gcd的倍數(shù),同樣可以推廣到更多數(shù):如果這些數(shù)的gcd的d不是1那么有無(wú)數(shù)個(gè)數(shù)組合不出來(lái)
? 第三:閆氏DP分析法:
-
根據(jù)閆氏DP分析法我們可以知道dp問(wèn)題可以將其分解為兩個(gè)步驟:第一種是狀態(tài)表示,第二種是狀態(tài)計(jì)算。
-
我們所有的背包問(wèn)題都是圍繞我們對(duì)于集合的定義來(lái)的,所以這個(gè)定義是非常重要的!!!我們將集合定義為:所有只從前i個(gè)包子中選擇,數(shù)量為j的集合是否能夠達(dá)到題目要求的包子數(shù),是個(gè)bool數(shù)組。
-
狀態(tài)計(jì)算:由于完全背包是可以無(wú)限次的選擇物品的,所以我們不能和01背包一樣,只將其分解為選或者不選,因?yàn)樗梢杂泻芏嗪芏喾N選擇,可以不選,可以選一種,可以選兩種...只要題目要求包子數(shù)量(背包體積)足夠大就可以。
-
如果他不選擇包子?i?那么這種情況相當(dāng)于從(1,i - 1)中選擇數(shù)量不超過(guò)j的情況是一樣的所以我們的表達(dá)式是:f[i-1][j]。
-
如果他選擇物品 i 那么這樣又該如何表示呢?我們并不知道他到底要選擇幾個(gè)物品,那應(yīng)該怎么做呢?假如我們選擇一個(gè)的話(huà)那么就應(yīng)該寫(xiě)為f[i-1][j-vi];假如我們選擇兩個(gè)的話(huà)那么就應(yīng)該寫(xiě)為f[i-1][j-2*vi];假如我們選擇k個(gè)的話(huà)那么就應(yīng)該寫(xiě)為f[i-1][j-k*vi],那么我們最終的答案就應(yīng)該在這些集合之中。
-
-
所以f(i,j) ?= f(i-1 , j) ||?f(i-1 , j - v) ||?f(i-1 , j - 2v) ||?........|| f(i-1 , j - (j/v)*v);
-
所以f(i,j-v) = f(i-1 , j - v) ||?f(i-1 , j - 2*v) ||?f(i-1 , 3*v) ||?........f(i-1 , j - (j/v)*v);
-
由上述兩個(gè)式子,我們可以知道如果將 j 替換成 j-vi 兩個(gè)式子非常相似。f[ i ] [ j ] = f[ i -1][ j ] ||?f[ i ][ j - vi ] ;
? 第四:書(shū)寫(xiě)主函數(shù),構(gòu)建整體框架:
-
輸入值,并且根據(jù)裴蜀定理求出最大公約數(shù)看看是不是1,如果不是1那么必定有無(wú)數(shù)個(gè)值組合不出來(lái),那么直接輸出INF。初始化一下我們的f數(shù)組全部賦值為0,初始化我們的f[0][0] = true。為什么?根據(jù)我們對(duì)集合的定義來(lái)分析:只從前i個(gè)包子中選擇,數(shù)量為j的集合是否能夠達(dá)到題目要求的包子數(shù)。那么f[0][0]代表前0個(gè)包子中選擇,數(shù)量為0的集合是可能的所以初始化為true。
for(int i = 1 ; i <= n ; ++ i){for(int j = 0 ; j <= 10000 ; ++ j){f[i][j] = f[i-1][j] || (j >= arr[i] ? f[i][j - arr[i]] : false) ;}}
-
d==1 的話(huà)我們就進(jìn)入雙重for循環(huán)。第一個(gè)for就是包子種類(lèi),第二個(gè)for就是包子數(shù)量。那么問(wèn)題來(lái)了。我們?cè)趺创_定數(shù)量最大值就是10000呢?那么當(dāng)qcd為1時(shí),最大不能表示出來(lái)的數(shù)必定有個(gè)上界,因?yàn)閮蓚€(gè)數(shù)a,b(當(dāng)gcd=1時(shí)),最大不能表示出數(shù)是:(a-1)(b-1)-1。當(dāng)數(shù)字更多的時(shí)候,這個(gè)上界必然更小(可選的數(shù)字變多了),而99和98是100內(nèi)最大的互質(zhì)的數(shù),所以這個(gè)上界選擇10000。
-
我們之前分析出了f[ i ] [ j ] = f[ i -1][ j ] ||?f[ i ][ j - vi ] ;但是注意一個(gè)問(wèn)題:選擇一個(gè),選擇兩個(gè),是在所需包子數(shù)大于我們的這一籠包子數(shù)的情況下才可以選,假如所需包子數(shù)都要小于這一籠包子數(shù)的話(huà)就不可以選了!所以我們選擇了用三目運(yùn)算符?(j >= arr[i] ? f[i][j - arr[i]] : false) ;這句話(huà)的意思是如果 j >= arr[i] 是對(duì)的話(huà)那么則返回f[i][j - arr[i]] ;如果不對(duì)則返回false,那么f[ i ] [ j ] = f[ i -1][ j ] ||?f[ i ][ j - vi ]這就是錯(cuò)了就代表組合不出這個(gè)數(shù)。
-
最后我們只需要在遍歷一遍,看看哪些數(shù)是組合不出來(lái)的,組合不出來(lái)就res++。
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110 ;int n ;
bool f[N][10010];
int arr[N];int gcd(int a , int b){return b ? gcd(b,a%b):a;
}int main()
{cin>>n;int d = 0;for(int i = 1 ; i <= n ; ++i){cin>>arr[i];d = gcd(d,arr[i]);}memset(f, 0, sizeof f);f[0][0] = true;if(d != 1) cout<<"INF"<<endl;else{for(int i = 1 ; i <= n ; ++ i){for(int j = 0 ; j <= 10000 ; ++ j){f[i][j] = f[i-1][j] || (j >= arr[i] ? f[i][j - arr[i]] : false) ;}}int res = 0;for(int i = 0 ; i <= 10000 ; i ++){if(!f[n][i]) res ++;}cout<<res;
}return 0;
}