中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁(yè) > news >正文

河南省專(zhuān)業(yè)做網(wǎng)站公司長(zhǎng)沙專(zhuān)業(yè)競(jìng)價(jià)優(yōu)化公司

河南省專(zhuān)業(yè)做網(wǎng)站公司,長(zhǎng)沙專(zhuān)業(yè)競(jìng)價(jià)優(yōu)化公司,wordpress+單頁(yè)模版,html5笑話(huà)網(wǎng)站源碼題目描述: 小明幾乎每天早晨都會(huì)在一家包子鋪吃早餐。 他發(fā)現(xiàn)這家包子鋪有 N 種蒸籠,其中第 i 種蒸籠恰好能放 Ai 個(gè)包子。 每種蒸籠都有非常多籠,可以認(rèn)為是無(wú)限籠。 每當(dāng)有顧客想買(mǎi) X 個(gè)包子,賣(mài)包子的大叔就會(huì)迅速選出若干籠…

題目描述:

小明幾乎每天早晨都會(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)建整體框架:

  1. 輸入值,并且根據(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) ;}}
  2. 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。

  3. 我們之前分析出了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ù)。

  4. 最后我們只需要在遍歷一遍,看看哪些數(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;
}

01背包從后往前,完全背包從前往后!!

http://www.risenshineclean.com/news/54667.html

相關(guān)文章:

  • 做餐飲的網(wǎng)站營(yíng)銷(xiāo)推廣seo
  • 不會(huì)代碼怎么做網(wǎng)站免費(fèi)網(wǎng)頁(yè)在線(xiàn)客服系統(tǒng)
  • 深圳做網(wǎng)站公廣東免費(fèi)網(wǎng)絡(luò)推廣軟件
  • cc后綴網(wǎng)站長(zhǎng)沙網(wǎng)站優(yōu)化效果
  • 沈陽(yáng)制作網(wǎng)站的人做網(wǎng)頁(yè)用什么軟件好
  • 淘寶客網(wǎng)站建設(shè)教程西安seo公司
  • 自學(xué)python的網(wǎng)站電商代運(yùn)營(yíng)公司十強(qiáng)
  • 平面設(shè)計(jì)有什么網(wǎng)站女教師網(wǎng)課入06654侵錄屏
  • 電商網(wǎng)站運(yùn)營(yíng)方案百度優(yōu)化點(diǎn)擊軟件
  • 交友視頻網(wǎng)站建設(shè)網(wǎng)絡(luò)推廣靠譜嗎
  • 廣州英銘網(wǎng)站建設(shè)百度網(wǎng)盤(pán)官網(wǎng)下載
  • 企業(yè)網(wǎng)站建設(shè)公司司如何做好網(wǎng)絡(luò)銷(xiāo)售技巧
  • 企業(yè)網(wǎng)站建設(shè)優(yōu)化泉州百度競(jìng)價(jià)推廣
  • jsp怎么做網(wǎng)站的刪除數(shù)字營(yíng)銷(xiāo)服務(wù)商seo
  • 5年網(wǎng)站續(xù)費(fèi)多少錢(qián)做銷(xiāo)售找客戶(hù)渠道
  • 濟(jì)源建設(shè)工程管理處網(wǎng)站網(wǎng)絡(luò)推廣員要怎么做
  • 網(wǎng)站主頁(yè)不收錄志鴻優(yōu)化設(shè)計(jì)電子版
  • 網(wǎng)站建設(shè)座談會(huì)上的發(fā)言寧波pc營(yíng)銷(xiāo)型網(wǎng)站制作
  • 電子商務(wù)網(wǎng)站建設(shè)策劃書(shū)的流程疫情最新政策最新消息
  • 搭建一個(gè)網(wǎng)站花多少錢(qián)大數(shù)據(jù)營(yíng)銷(xiāo)精準(zhǔn)營(yíng)銷(xiāo)
  • 江蘇煙草電商網(wǎng)站怎么做如何網(wǎng)絡(luò)推廣新產(chǎn)品
  • 有關(guān)做美食的網(wǎng)站王通seo教程
  • 網(wǎng)站怎么發(fā)布做微商在線(xiàn)識(shí)別圖片找原圖
  • 溫州建設(shè)網(wǎng)站哪家好百度官方認(rèn)證
  • 百度做網(wǎng)站推廣怎么樣優(yōu)化網(wǎng)站seo
  • 游戲網(wǎng)站建設(shè)一條龍平臺(tái)推廣公眾平臺(tái)營(yíng)銷(xiāo)
  • 網(wǎng)站建設(shè)空標(biāo)記網(wǎng)站seo查詢(xún)站長(zhǎng)之家
  • 住房城鄉(xiāng)與建設(shè)廳網(wǎng)站企業(yè)網(wǎng)站推廣策略
  • 做網(wǎng)站廣告有哪些職位seo關(guān)鍵詞挖掘
  • 國(guó)內(nèi)企業(yè)網(wǎng)站設(shè)計(jì)網(wǎng)站排名優(yōu)化培訓(xùn)哪家好