原文鏈接：

http://www.wutianqi.com/?p=1181

大家在學(xué)習(xí)C++編程時(shí)，一般在輸入方面都是使用的cin.
而cin是使用空白（空格，制表符和換行符）來(lái)定字符串的界的。
這就導(dǎo)致了對(duì)于帶有空格的字符串，比如”I Love www.CppLeyuan.com”
只能讀入”I”，后面的都無(wú)法讀入。
這時(shí)怎么辦？

 一.對(duì)于字符數(shù)組：
方法一：getline()
讀入整行數(shù)據(jù)，它使用回車鍵輸入的換行符來(lái)確定輸入結(jié)尾。
調(diào)用方法: cin.getline(str, len);
第一個(gè)參數(shù)str是用來(lái)存儲(chǔ)輸入行的數(shù)組名稱，第二個(gè)參數(shù)len是要讀取的字符數(shù)。

方法二：get()

調(diào)用方法：cin.get(str, len);

那么兩者有何區(qū)別？
兩者都讀取一行輸入，直至換行符。
然后，getline將丟棄換行符，而get()將換行符保留在輸入序列里。
所以，再使用cin.get()輸入多行數(shù)據(jù)時(shí)，中間可以使用get()消除換行符。

因?yàn)間et(str, len)和get()都是cin的類成員，所以可以合并起來(lái)寫：

(歡迎大家去我論壇學(xué)習(xí):C++奮斗樂(lè)園：http://www.cppleyuan.com/)

二.對(duì)于string類
方法一:getline(cin, str)

這說(shuō)明這里的getline不是類方法。

PS:以后如果對(duì)輸入方面還有更多了解，會(huì)繼續(xù)補(bǔ)充，希望大家支持，多多交流。

原創(chuàng)鏈接：http://www.wutianqi.com/?p=1162

上次論壇里一個(gè)會(huì)員問(wèn)的。
感覺(jué)這個(gè)程序作為DFS入門是很理想的，大家應(yīng)該都能看懂。
貼出來(lái)和大家分享：

 

 1#include<iostream>
 2using namespace std;
 3int a[100] = {0};
 4int n;
 5int count=0; 
 6void dfs(int k)
 7{
 8   if(k >= n)
 9   {
10      for(int i = 0;i < n;i++)
11      {
12         cout<<a[i]<<" ";
13      }
14      count++;
15      cout<<endl;
16   }     
17   else
18   {
19      for(int i = 1;i <= n;i++)
20      {
21         a[k] = i; 
22         dfs(k + 1);        
23      }       
24   }    
25}
26int main()
27{
28   while(cin>>n)
29   {
30      count=0;
31      int k = 0;
32      dfs(k);  
33      cout<<count<<endl;             
34   }    
35}

 

---

http://www.wutianqi.com/?p=1157

---

集合A的冪集是由集合A的所有子集所組成的的集合。

 

如：A={1，2，3}，則A的冪集P（A）={{1，2，3}，{1，2}，{1，3}，{1}，{2，3}，{2}，{3}，{ }}。

求一個(gè)集合的冪集就是求一個(gè)集合的所有的子集，方法有窮舉法，分治法，回溯等，這里主要介紹一下回溯法。

回溯法是設(shè)計(jì)遞歸過(guò)程的一種重要的方法，它的求解過(guò)實(shí)質(zhì)上是一個(gè)先序遍歷一棵“狀態(tài)樹”的過(guò)程，只是這棵樹不是遍歷前預(yù)先建立的，而是隱含在遍歷過(guò)程中的。

冪集中的每個(gè)元素是一個(gè)集合，它或是空集，或含集合A中一個(gè)元素，或含集合A中兩個(gè)元素…… 或等于集合A。反之，從集合A 的每個(gè)元素來(lái)看，它只有兩種狀態(tài)：它或?qū)賰缂臒o(wú)素集，或不屬冪集的元素集。則求冪集p(A)的元素的過(guò)程可看成是依次對(duì)集合A中元素進(jìn)行“取”或“舍”的過(guò)程，并且可以用一棵二叉樹來(lái)表示過(guò)程中冪集元素的狀態(tài)變化過(guò)程，樹中的根結(jié)點(diǎn)表示冪集元素的初始狀態(tài)（空集）；葉子結(jié)點(diǎn)表示它的終結(jié)狀態(tài)，而第i層的分支結(jié)點(diǎn)，則表示已對(duì)集合A中前i-1個(gè)元素進(jìn)行了取舍處理的當(dāng)前狀態(tài)（左分支表示取，右分支表示舍 ）。因此求冪集元素的過(guò)程即為先序遍歷這棵狀態(tài)樹的過(guò)程。

具體算法如下：

C/C++描述：

 1#include <iostream>
 2#include <cstring>
 3#include <ctype.h>
 4#include <stdlib.h>
 5#include <string>
 6using namespace std;
 7 
 8char a[100];
 9char b[100];
10 
11void GetPowerSet(int i, char a[])
12{
13    char x;
14    int k;
15    int len = strlen(a);
16    if(i >= len)
17    {
18        if(b[0])
19            cout << b <<  endl;
20        else
21            cout << "XX" << endl;  // 表示空集
22    }
23    else
24    {
25        x = a[i];
26        k = strlen(b);
27        b[k] = x;
28        GetPowerSet(i+1, a);
29        b[k] = 0;
30        GetPowerSet(i+1, a);
31    }
32}
33 
34 
35int main()
36{
37    while(scanf("%s", a) != EOF)
38    {
39        printf("%s的冪集是:\n", a);
40        printf("------------\n");
41        GetPowerSet(0, a);
42        printf("------------\n");
43    }
44}

原文鏈接：
http://www.wutianqi.com/?p=1028

          回憶起以前我看這本書，聯(lián)系自己學(xué)編程這一年多，感觸頗多。記得這本書剛出來(lái)時(shí)，我就在中關(guān)村圖書大廈買了一本。至今已經(jīng)快一年了。故事情節(jié)依稀記得一點(diǎn)。

          里面講到了BOSS 絕的奮斗史，讀大學(xué)時(shí)和寢室一伙人到處折騰，給別人裝機(jī)子，去小公司找工作，以及后來(lái)的作為招聘人員去自己學(xué)校招員工，私下接外掛破解，和女友的坎坷經(jīng)歷直到最后的分手。

          絕影的人生并不好走，雖然大學(xué)還未畢業(yè)就找到工作了，但是可以看出他的艱辛，經(jīng)常熬夜趕項(xiàng)目；節(jié)假日不能陪家人，結(jié)果女友也要求分手了。

          我不知道該說(shuō)什么好，別人都說(shuō)嫁人要嫁程序員，程序員只關(guān)心電腦，不會(huì)在外面過(guò)那種花花綠綠的生活，這是褒義，還是貶義？也許只有說(shuō)這話的人心里才清楚。

          我大學(xué)是讀自動(dòng)化的，連我都不知道我為何要報(bào)自動(dòng)化，我只知道，高考沒(méi)考到自己預(yù)想的分?jǐn)?shù)，考了一個(gè)半吊子的分?jǐn)?shù)：568分，而一本分?jǐn)?shù)線是548.就這么高不高，低不低的。連我老爸當(dāng)年讀的中南財(cái)經(jīng)政法大學(xué)都讀不了，于是我也懶得管了，直接讓我父母報(bào)，結(jié)果第一志愿是北京化工大學(xué)的機(jī)械工程及其自動(dòng)化，第二志愿是北京化工大學(xué)的自動(dòng)化。最后第一志愿沒(méi)錄取，于是我到了北化的自動(dòng)化系。雖然讀了兩年大學(xué)，我還不知道我這個(gè)專業(yè)到底是干啥的，只知道這個(gè)專業(yè)是一個(gè)萬(wàn)金油，啥都行~~~

           大一剛進(jìn)校，因?yàn)楦呖纪暝诩姨焯焱婢W(wǎng)游，開(kāi)學(xué)了還沒(méi)回過(guò)神來(lái)，別人都忙于互相認(rèn)識(shí)，一起游覽北京的一些旅游景點(diǎn)，而我卻忙于在網(wǎng)吧與寢室兩地顛簸。那時(shí)剛開(kāi)學(xué)，班級(jí)和學(xué)校有許多的活動(dòng)，我一個(gè)都沒(méi)參加，記得開(kāi)學(xué)就有學(xué)校和院的各個(gè)部門招人手，我那時(shí)沒(méi)認(rèn)識(shí)到德育分的重要性，也沒(méi)有刻意去培養(yǎng)自己的結(jié)交能力(不過(guò)我的朋友還是非常多的~~在學(xué)校，許多人都和我很熟悉，因?yàn)槲覀€(gè)人性格是比較活潑開(kāi)朗的，且喜歡開(kāi)玩笑，所以都比較隨和。)，但學(xué)校又要求每人都得報(bào)2項(xiàng)，所以其中一項(xiàng)我沒(méi)去，另外一項(xiàng)別人打電話過(guò)來(lái)了，我也說(shuō)沒(méi)時(shí)間~~~（是不是很拽？）其實(shí)也不是不給他們面子，只是在我眼中，我不喜歡這些權(quán)勢(shì)及口頭上的較量，靠嘴皮子進(jìn)去，一點(diǎn)用都沒(méi)，而且在我看來(lái)，這些東西都是無(wú)聊至極的，一群把自己當(dāng)成官一樣來(lái)看待的，讓我感覺(jué)很不舒服。我喜歡那種靠自己真實(shí)實(shí)力較量的生活。并且在我看來(lái)，等工作了這些權(quán)勢(shì)競(jìng)爭(zhēng)的生活多的是，在大學(xué)去浪費(fèi)時(shí)間花在這上面太不值得了。就這么渾渾噩噩的一個(gè)學(xué)期快過(guò)完了，臨近寒假，發(fā)現(xiàn)別人雖然分一部分心思去弄學(xué)校各個(gè)部門的活，但是也確實(shí)培養(yǎng)了他們的個(gè)人能力，而我呢？除了會(huì)去網(wǎng)吧，還是去網(wǎng)吧。雖然那時(shí)成績(jī)不差，在班級(jí)30人中還能排在第10名。但是自己缺乏了其他獨(dú)特的能力。因?yàn)槲医佑|計(jì)算機(jī)很早，是從小學(xué)5年級(jí)開(kāi)始的，所以我想到了從計(jì)算機(jī)這方面發(fā)展，剛開(kāi)始對(duì)編程一竅不通，買了基本PS,FLASH,DW的書看，結(jié)果自己就是在美術(shù)細(xì)胞上太過(guò)于匱乏，始終弄不好，就這樣折騰了3個(gè)多月，最終放棄了，那時(shí)也知道了C語(yǔ)言，且知道下學(xué)期要學(xué)C語(yǔ)言，所以就提前自學(xué)了。我的編程生涯也就是從這個(gè)時(shí)候開(kāi)始的（起步很晚~~）。

           剛開(kāi)始學(xué)C語(yǔ)言，我就被吸引了，作為男生，我相信好多人都很YM那些開(kāi)發(fā)軟件的人，我也不例外，而接觸了C語(yǔ)言，我才知道，這就是可以開(kāi)發(fā)出軟件的東東，于是，我埋頭苦學(xué)…汗，其實(shí)也算不上苦學(xué)，就是把自己的課程都丟了，天天只看C語(yǔ)言的書，因?yàn)槲也皇怯?jì)算機(jī)專業(yè)的，沒(méi)人教我，也沒(méi)人給我經(jīng)驗(yàn)，我就只能靠自己，計(jì)算機(jī)編程這方面的書都很貴的，還好有父母的經(jīng)濟(jì)支持，這樣算一算，我10個(gè)月在買書上就花了2000元。我到現(xiàn)在都不知道怎么花的，反正牛人的書我都買了，還訂了好多雜志。記得看了譚老的《C語(yǔ)言程序》，《C Primer Plus》, 《The C Programming Language》 《C陷阱與缺陷》 《C專家編程》等等~~~太多了，我經(jīng)常沒(méi)去上課，一個(gè)人抱著書和電腦去圖書館學(xué)。結(jié)果自己專業(yè)沒(méi)顧著，大二下學(xué)期還弄了個(gè)年級(jí)300人，倒數(shù)10幾名~~

           大二上學(xué)期我報(bào)了等級(jí)考試的三級(jí)數(shù)據(jù)庫(kù)，也順利的一次通過(guò)。呵呵，現(xiàn)在想來(lái)，也沒(méi)啥高興的，畢竟那些都是虛的，只需要靠2本書死記就過(guò)的，沒(méi)有一點(diǎn)技術(shù)含量，不值得高興。到了現(xiàn)在，數(shù)據(jù)庫(kù)的一些知識(shí)也快忘光了。

           大二上學(xué)期的暑假，我開(kāi)始學(xué)習(xí)C++了。那時(shí)學(xué)了一段時(shí)間，寂寞了，于是建了幾個(gè)QQ群，在網(wǎng)上召集了一批C++愛(ài)好者一起交流，也就是那個(gè)時(shí)候，有了創(chuàng)辦一個(gè)論壇讓大家一起交流學(xué)習(xí)的想法。也就是在大二下學(xué)期開(kāi)學(xué)后，隨著群的人越來(lái)越多，許多人也提議弄一個(gè)專門學(xué)習(xí)交流的地方，于是我買了空間和域名，辦了一個(gè)論壇。因?yàn)槲矣X(jué)得人生就要奮斗，我們學(xué)習(xí)編程，何嘗不是在為以后而奮斗，所以我給群，以及論壇取名叫C++奮斗樂(lè)園。域名我也選擇了cppleyuan。

           最開(kāi)始接觸ACM不知道是在什么時(shí)候，應(yīng)該實(shí)在大一下學(xué)期或大二上學(xué)期吧。那時(shí)就覺(jué)得這挺有趣的，但是也沒(méi)買書學(xué)習(xí)算法，就這么直接找上了POJ，經(jīng)常把題目看懂就花了1個(gè)小時(shí)，然后做不出來(lái)，再分析別人代碼又是幾個(gè)小時(shí)~~~汗…后來(lái)覺(jué)得這東西不是我這種人弄的，就放棄了。不過(guò)還好，只是暫時(shí)放棄，在大二下學(xué)期開(kāi)學(xué)后1個(gè)月，也就是2010年4月份左右吧。我又開(kāi)始搞ACM了，因?yàn)閷W(xué)習(xí)C和C++也有一段時(shí)間了，對(duì)于編程也有了一定的認(rèn)識(shí)，不再是那個(gè)初入編程大門，懵懵懂懂亂學(xué)的人了，我買了劉如佳老師的《算法學(xué)習(xí)經(jīng)典入門》，《算法藝術(shù)與信息學(xué)競(jìng)賽》，吳文虎老師的《世界大學(xué)生程序設(shè)計(jì)競(jìng)賽》以及算法的圣經(jīng)—-《算法導(dǎo)論》。就這么開(kāi)始一個(gè)人在算法的海洋里探索了。也就是這個(gè)時(shí)候，因?yàn)樽约簩?duì)這方面有了解，并且覺(jué)得論壇不能只搞C++方面，所以我把論壇一部分分給了算法。畢竟算法是程序的靈魂。但是POJ對(duì)于我這個(gè)剛起步的小菜來(lái)說(shuō)還是難了些。所以我開(kāi)始轉(zhuǎn)向HDOJ了，7月10號(hào)注冊(cè)的。今天是8月17號(hào)，已經(jīng)刷了210道水題了。我感覺(jué)，每AC一道題目，就感覺(jué)自己快樂(lè)了一分。也許這就是算法的魅力把，也可能這就是男人喜歡對(duì)事物的絕對(duì)掌控，感覺(jué)自己學(xué)懂了這個(gè)算法，就感覺(jué)自己多了一項(xiàng)能力。

           假期我給論壇弄了C/C++小項(xiàng)目和ACM刷題活動(dòng)。當(dāng)時(shí)我還到處找資料，花了一下午為C/C++小項(xiàng)目的第一個(gè)寫了一個(gè)詳細(xì)的流程圖，結(jié)果到最后無(wú)人問(wèn)津，只有個(gè)別人做了，wujing的就做的很好，贊一個(gè)。不過(guò)還好，ACM刷題活動(dòng)倒是很受歡迎，每天都有一批人和我一起刷，包括MiYu,大帥，蘿莉，timest,ac-quest等等。當(dāng)然，amb教主我就不多說(shuō)了，我只能YM。小白就是專門和我競(jìng)爭(zhēng)的家伙。。。最近被他趕超了10題。郁悶。不過(guò)假期確實(shí)還是很開(kāi)心的。畢竟結(jié)交了一群志同道合的朋友。

          現(xiàn)在假期也快結(jié)束了，8月20號(hào)返校，還得搬校區(qū)。

         看的書很多，想的也很多。喜歡思考編程，思考人生哲理。平時(shí)除了編程的書，我就最喜歡看自然科學(xué)和人生哲理了，《當(dāng)下的力量》，《遇見(jiàn)心想事成的自己》，《秘密》這些書都很好，教會(huì)了我很多道理。感覺(jué)這些書就和算法一樣，講的都是內(nèi)涵。人生就像編程，編的是人生，讓人生合理，規(guī)劃好人生，人生才能成功。

           最后，我想感謝C++奮斗樂(lè)園的各位斑竹，感謝假期陪我刷題的哥們，感謝支持我的論壇會(huì)員們。Orz

         以上算是發(fā)泄自己的情感，也算是傾述自己的經(jīng)歷，或算是總結(jié)自己的經(jīng)驗(yàn)。不求能給大家什么幫助，只求大家能一起多交流點(diǎn)自己的經(jīng)驗(yàn)，互相借鑒，互相學(xué)習(xí)。
                                                                                                                                                                                                
                                                                                                                                                                          TankyWoo    
                                                                                                                                                                    2010年8月7號(hào)
我的博客：http://www.wutianqi.com/ 希望大家多多交流。

（原創(chuàng)鏈接：http://www.wutianqi.com/?p=264）
思想：對(duì)于不超過(guò)n的每個(gè)非負(fù)整數(shù)P，刪除2*P, 3*P…，當(dāng)處理

完所有數(shù)之后，還沒(méi)有被刪除的就是素?cái)?shù)。

若用vis[i]==1表示已被刪除，則代碼如下：
—————————————————–
代碼一：

1memset(vis, 0, sizeof(vis));
2for(int i = 2; i <= 100; i++)
3    for(int j = i*2; j <= 100; j += i)
4        vis[j] = 1;

上面的代碼效率已經(jīng)很高了。
但還可以繼續(xù)優(yōu)化。
看一個(gè)改進(jìn)的代碼：
——————————————————
代碼二：

 1int m = sqrt(double(n+0.5));
 2 
 3for(int i = 2; i <= m; i++)
 4    if(!vis[i])
 5    {
 6        prime[c++] = i;
 7        for(int j = i*i; j <= n; j += i)
 8        {
 9            vis[j] = 1;
10        }
11    }

——————————————————
先分析代碼一：
這個(gè)代碼就是簡(jiǎn)單的將Eratosthenes篩選法描述出來(lái)。不用多說(shuō)。
分析代碼二：
考慮幾點(diǎn)：
1.為何從i=2~m?
因?yàn)橄旅娴膉是從i*i開(kāi)始的。
2.為何j從i*i開(kāi)始？
因?yàn)槭紫仍趇=2時(shí)，偶數(shù)都已經(jīng)被刪除了。
其次，“對(duì)于不超過(guò)n的每個(gè)非負(fù)整數(shù)P”， P可以限定為素?cái)?shù)，
為什么？
因?yàn)椋?i 執(zhí)行到P時(shí)，P之前所有的數(shù)的倍數(shù)都已經(jīng)被刪除，若P

沒(méi)有被刪除，則P一定是素?cái)?shù)。
而P的倍數(shù)中，只需看：
(p-4)*p, (p-2)*p, p*p, p*(p+2), p*(p+4)
（因?yàn)镻為素?cái)?shù)，所以為奇數(shù)，而偶數(shù)已被刪除，不需要考慮p*(p

-1)等）（Tanky Woo的程序人生）
又因?yàn)?p-4)*p 已在 (p-4)的p倍中被刪去，故只考慮：
p*p, p*(p+2)….即可
這也是i只需要從2到m的原因。
當(dāng)然，上面 p*p, p*(p+2)…的前提是偶數(shù)都已經(jīng)被刪去，而代碼

二若改成 j += 2*i ,則沒(méi)有除去所有偶數(shù)，所以要想直接 加2*i

。只需在代碼二中memset()后面加：
for(int i = 4; i <= n; i++)
if(i % 2 == 0)
vis[i] = 1;
這樣，i只需從3開(kāi)始，而j每次可以直接加 2*i.
------------------------------------------------------
這里用代碼二給大家一個(gè)完整的代碼：

 1//版本二
 2//Author: Tanky Woo
 3//Blog: www.wutianqi.com
 4 
 5#include <stdio.h>
 6#include <string.h>
 7#include <math.h>
 8int vis[100];
 9int prime[100];
10int c = 0;
11int n;
12int main()
13{
14    scanf("%d", &n);
15    int cnt = 1;
16 
17    memset(vis, 0, sizeof(vis));
18    int m = sqrt(double(n+0.5));
19 
20    for(int i = 2; i <= m; i++)
21        if(!vis[i])
22        {
23            prime[c++] = i;
24            for(int j = i*i; j <= n; j += i)
25            {
26                vis[j] = 1;
27                //printf("%d\n", j);
28            }
29        }
30 
31    for(int i = 2; i < n; i++)
32    {
33        if(vis[i] == 0)
34        {
35            printf("%d ", i);
36            cnt++;
37            if(cnt % 10 == 0)
38                printf("\n");
39        }
40    }
41    printf("\ncnt = %d\n", cnt);
42    return 0;
43}

完畢。

---

歡迎大家和我交流。(我的博客:http://www.wutianqi.com/)

背包之01背包、完全背包、多重背包詳解

PS：大家覺(jué)得寫得還過(guò)得去，就幫我頂博客，謝謝。

首先說(shuō)下動(dòng)態(tài)規(guī)劃，動(dòng)態(tài)規(guī)劃這東西就和遞歸一樣，只能找局部關(guān)系，若想全部列出來(lái)，是很難的，比如漢諾塔。你可以說(shuō)先把除最后一層的其他所有層都移動(dòng)到2，再把最后一層移動(dòng)到3，最后再把其余的從2移動(dòng)到3，這是一個(gè)直觀的關(guān)系，但是想列舉出來(lái)是很難的，也許當(dāng)層數(shù)n=3時(shí)還可以模擬下，再大一些就不可能了，所以，諸如遞歸，動(dòng)態(tài)規(guī)劃之類的，不能細(xì)想，只能找局部關(guān)系。

1.漢諾塔圖片

（引至杭電課件:DP最關(guān)鍵的就是狀態(tài)，在DP時(shí)用到的數(shù)組時(shí)，也就是存儲(chǔ)的每個(gè)狀態(tài)的最優(yōu)值，也就是記憶化搜索）

要了解背包，首先得清楚動(dòng)態(tài)規(guī)劃：

動(dòng)態(tài)規(guī)劃算法可分解成從先到后的4個(gè)步驟：

1. 描述一個(gè)最優(yōu)解的結(jié)構(gòu)；

2. 遞歸地定義最優(yōu)解的值；

3. 以“自底向上”的方式計(jì)算最優(yōu)解的值；

4. 從已計(jì)算的信息中構(gòu)建出最優(yōu)解的路徑。

其中步驟1~3是動(dòng)態(tài)規(guī)劃求解問(wèn)題的基礎(chǔ)。如果題目只要求最優(yōu)解的值，則步驟4可以省略。

背包的基本模型就是給你一個(gè)容量為V的背包

在一定的限制條件下放進(jìn)最多(最少?)價(jià)值的東西

當(dāng)前狀態(tài)→ 以前狀態(tài)

看了dd大牛的《背包九講》(點(diǎn)擊下載)，迷糊中帶著一絲清醒，這里我也總結(jié)下01背包，完全背包，多重背包這三者的使用和區(qū)別，部分會(huì)引用dd大牛的《背包九講》，如果有錯(cuò)，歡迎指出。

(www.wutianqi.com留言即可)

首先我們把三種情況放在一起來(lái)看：

01背包（ZeroOnePack）: 有N件物品和一個(gè)容量為V的背包。（每種物品均只有一件）第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。

完全背包(CompletePack): 有N種物品和一個(gè)容量為V的背包，每種物品都有無(wú)限件可用。第i種物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。

多重背包(MultiplePack): 有N種物品和一個(gè)容量為V的背包。第i種物品最多有n[i]件可用，每件費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。

比較三個(gè)題目，會(huì)發(fā)現(xiàn)不同點(diǎn)在于每種背包的數(shù)量，01背包是每種只有一件，完全背包是每種無(wú)限件，而多重背包是每種有限件。

——————————————————————————————————————————————————————————–：

01背包（ZeroOnePack）: 有N件物品和一個(gè)容量為V的背包。（每種物品均只有一件）第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。

這是最基礎(chǔ)的背包問(wèn)題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。

用子問(wèn)題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

把這個(gè)過(guò)程理解下：在前i件物品放進(jìn)容量v的背包時(shí)，

它有兩種情況：

第一種是第i件不放進(jìn)去，這時(shí)所得價(jià)值為:f[i-1][v]

第二種是第i件放進(jìn)去，這時(shí)所得價(jià)值為：f[i-1][v-c[i]]+w[i]

（第二種是什么意思？就是如果第i件放進(jìn)去，那么在容量v-c[i]里就要放進(jìn)前i-1件物品）

最后比較第一種與第二種所得價(jià)值的大小，哪種相對(duì)大，f[i][v]的值就是哪種。

（這是基礎(chǔ)，要理解！）

這里是用二位數(shù)組存儲(chǔ)的，可以把空間優(yōu)化，用一位數(shù)組存儲(chǔ)。

用f[0..v]表示，f[v]表示把前i件物品放入容量為v的背包里得到的價(jià)值。把i從1~n(n件)循環(huán)后，最后f[v]表示所求最大值。

*這里f[v]就相當(dāng)于二位數(shù)組的f[i][v]。那么，如何得到f[i-1][v]和f[i-1][v-c[i]]+w[i]？（重點(diǎn)！思考）
首先要知道，我們是通過(guò)i從1到n的循環(huán)來(lái)依次表示前i件物品存入的狀態(tài)。即：for i=1..N
現(xiàn)在思考如何能在是f[v]表示當(dāng)前狀態(tài)是容量為v的背包所得價(jià)值，而又使f[v]和f[v-c[i]]+w[i]標(biāo)簽前一狀態(tài)的價(jià)值？

逆序！

這就是關(guān)鍵！

1for i=1..N
2   for v=V..0
3        f[v]=max{f[v],f[v-c[i]]+w[i]};
4

分析上面的代碼：當(dāng)內(nèi)循環(huán)是逆序時(shí)，就可以保證后一個(gè)f[v]和f[v-c[i]]+w[i]是前一狀態(tài)的！
這里給大家一組測(cè)試數(shù)據(jù)：

測(cè)試數(shù)據(jù)：
10,3
3,4
4,5
5,6

這個(gè)圖表畫得很好，借此來(lái)分析：

C[v]從物品i=1開(kāi)始，循環(huán)到物品3，期間，每次逆序得到容量v在前i件物品時(shí)可以得到的最大值。（請(qǐng)?jiān)诓莞寮埳献约寒嬕划?/span>）

這里以一道題目來(lái)具體看看：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=2602

代碼在這里：http://www.wutianqi.com/?p=533

分析：

具體根據(jù)上面的解釋以及我給出的代碼分析。這題很基礎(chǔ)，看懂上面的知識(shí)應(yīng)該就會(huì)做了。

——————————————————————————————————————————————————————————–

完全背包：

完全背包(CompletePack): 有N種物品和一個(gè)容量為V的背包，每種物品都有無(wú)限件可用。第i種物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。

完全背包按其思路仍然可以用一個(gè)二維數(shù)組來(lái)寫出：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

同樣可以轉(zhuǎn)換成一維數(shù)組來(lái)表示：

偽代碼如下：



for i=1..N
    for v=0..V
        f[v]=max{f[v],f[v-c[i]]+w[i]}

順序！

想必大家看出了和01背包的區(qū)別，這里的內(nèi)循環(huán)是順序的，而01背包是逆序的。
現(xiàn)在關(guān)鍵的是考慮：為何完全背包可以這么寫？
在次我們先來(lái)回憶下，01背包逆序的原因？是為了是max中的兩項(xiàng)是前一狀態(tài)值，這就對(duì)了。
那么這里，我們順序?qū)懀@里的max中的兩項(xiàng)當(dāng)然就是當(dāng)前狀態(tài)的值了，為何？
因?yàn)槊糠N背包都是無(wú)限的。當(dāng)我們把i從1到N循環(huán)時(shí)，f[v]表示容量為v在前i種背包時(shí)所得的價(jià)值，這里我們要添加的不是前一個(gè)背包，而是當(dāng)前背包。所以我們要考慮的當(dāng)然是當(dāng)前狀態(tài)。
這里同樣給大家一道題目：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=1114

代碼：http://www.wutianqi.com/?p=535

（分析代碼也是學(xué)習(xí)算法的一種途徑，有時(shí)并不一定要看算法分析，結(jié)合題目反而更容易理解。）

——————————————————————————————————————————————————————————–

多重背包

多重背包(MultiplePack): 有N種物品和一個(gè)容量為V的背包。第i種物品最多有n[i]件可用，每件費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。

這題目和完全背包問(wèn)題很類似。基本的方程只需將完全背包問(wèn)題的方程略微一改即可，因?yàn)閷?duì)于第i種物品有n[i]+1種策略：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值，則有狀態(tài)轉(zhuǎn)移方程：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

這里同樣轉(zhuǎn)換為01背包：

普通的轉(zhuǎn)換對(duì)于數(shù)量較多時(shí)，則可能會(huì)超時(shí)，可以轉(zhuǎn)換成二進(jìn)制（暫時(shí)不了解，所以先不講）

對(duì)于普通的。就是多了一個(gè)中間的循環(huán)，把j=0~bag[i]，表示把第i中背包從取0件枚舉到取bag[i]件。

給出一個(gè)例題：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=2191

代碼：http://www.wutianqi.com/?p=537

因?yàn)橄抻趥€(gè)人的能力，我只能講出個(gè)大概，請(qǐng)大家具體還是好好看看dd大牛的《背包九講》。

暫時(shí)講完后，隨著以后更深入的了解，我會(huì)把資料繼續(xù)完善，供大家一起學(xué)習(xí)探討。(我的博客：www.wutianqi.com如果大家有問(wèn)題或者資料里的內(nèi)容有錯(cuò)誤，可以留言給出，謝謝您的支持。)

原文下載地址：（Word版）
http://download.csdn.net/sour

個(gè)人原創(chuàng)，轉(zhuǎn)載請(qǐng)注明本文鏈接：http://www.wutianqi.com/?p=539

學(xué)校太讓人失望了，居然連POJ都上不去了，還好今天ambition在我用百練AC掉這題后送來(lái)了另外一個(gè)POJ的網(wǎng)址，雙喜臨門，害我興奮了半天，沒(méi)有POJ的日子痛苦啊。畢竟題目來(lái)源還得靠它。

這是曾經(jīng)沒(méi)有AC掉的題目，不過(guò)在《程序設(shè)計(jì)導(dǎo)引及在線實(shí)踐》上看過(guò)，看書寫代碼還是沒(méi)親自做的效果好。今天給假期題目來(lái)源找題，看中了這題，再次做，強(qiáng)化了一些基本功。

分析幾點(diǎn)：

一。A~Z對(duì)應(yīng)一個(gè)Hash數(shù)組

二。在每輸入一個(gè)數(shù)據(jù)時(shí)就對(duì)數(shù)據(jù)進(jìn)行處理，轉(zhuǎn)換字母，去掉’-’

三。qsort的運(yùn)行，具體看MSDN，這里就講一點(diǎn)。

    一個(gè)是二位數(shù)組的qsort用法：

1
            2
            3
            4
            5
            6
            

 int compare( const void *arg1, const void *arg2 )
            {
            return strcmp((char*)arg1, (char*)arg2 );
            }
            int arr[n][11];
            qsort(arr, n, sizeof(arr[0]), compare);

  二是qsort的幾個(gè)參數(shù)，這里一直不是記得很清楚。

1
            2
            3
            4
            5
            6
            

 void qsort(
            void *base,
            size_t num,
            size_t width,
            int (__cdecl *compare )(const void *, const void *)
            );

  注意：width: Element size in bytes

               cmp函數(shù)：如果是升序，則e1 > e2應(yīng)返回1，e1 = e2 應(yīng)返回0， e1 < e2 應(yīng)返回-1.降序則相反。

直接發(fā)代碼了：

時(shí)間有點(diǎn)大，是600多MS。

看見(jiàn)網(wǎng)上還有其他方法，大家可以去看看。

題目地址：

http://124.205.79.250/JudgeOnline/problem?id=1002

1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            11
            12
            13
            14
            15
            16
            17
            18
            19
            20
            21
            22
            23
            24
            25
            26
            27
            28
            29
            30
            31
            32
            33
            34
            35
            36
            37
            38
            39
            40
            41
            42
            43
            44
            45
            46
            47
            48
            49
            50
            51
            52
            53
            54
            55
            56
            57
            58
            59
            60
            61
            62
            63
            64
            65
            66
            67
            68
            69
            70
            71
            72
            73
            74
            

 // POJ 487-3279
            // Author: Tanky Woo
            #include <iostream>
            using namespace std;
             
            char hash[] = "22233344455566670778889990";
             
            char telphone[100001][20];
            char temp[20];
             
            int compare( const void *arg1, const void *arg2 )
            {
            return strcmp((char*)arg1, (char*)arg2 );
            }
             
            // www.wutianqi.com
            int main()
            {
            //freopen("input.txt", "r", stdin);
            int flag = 0;
            int nCases;
            scanf("%d", &nCases);
            for(int i = 0; i < nCases; ++i)
            {
            getchar();
            scanf("%s", telphone[i]);
            int len = strlen(telphone[i]);
            int t = 0;
            for(int j = 0; j < len; ++j)
            {
            if(telphone[i][j] >= 'A' && telphone[i][j] <= 'Z')
            temp[t++] = hash[telphone[i][j]-'A'];
            else if(telphone[i][j] >= '0' && telphone[i][j] <= '9')
            temp[t++] = telphone[i][j];
            else if(telphone[i][j] == '-')
            ;
            }
            strcpy(telphone[i], temp);
            }
             
            qsort(telphone, nCases, sizeof(telphone[0]), compare);
             
             
            for(int i = 0; i < nCases; ++i)
            {
             
            int cnt = 1;
            strcpy(temp, telphone[i]);
            int j;
            for(j = i+1; j < nCases; ++j)
            {
            if(strcmp(temp, telphone[j]) == 0)
            cnt++;
            else
            break;
            }
            if(cnt > 1)   //這個(gè)地方?jīng)]處理好，麻煩。。。
            {
            flag = 1;
            for(int k = 0; k < 3; ++k)
            printf("%c", temp[k]);
            printf("-");
            for(int k = 3; k < 7; ++k)
            printf("%c", temp[k]);
            printf(" %d\n", cnt);
            }
            i = j-1;
            }
            if(flag == 0)
            printf("No duplicates.\n");
             
             
            return 0;
            }