《算法設(shè)計》課程實施大綱

《算法設(shè)計》課程實施大綱教學(xué)理念要設(shè)計一個簡單易行的正確算法是一件困難的工作，他需要算法的編寫者有獨到的創(chuàng)新能力，嚴謹?shù)乃季S能力。所以在教學(xué)過程中就要注重培養(yǎng)學(xué)生這方面的能力。在教學(xué)過程中要圍繞算法設(shè)計技術(shù)組織素材，對每種算法技術(shù)選擇多個典型范例進行分析。將直觀性與嚴謹性完美地結(jié)合起來。每章從實際問題出發(fā)，經(jīng)過具體、深入、細致的分析，自然且富有啟發(fā)性地引出相應(yīng)的算法設(shè)計思想，并對算法的正確性、復(fù)雜性進行恰當?shù)姆治?、認證。以各種算法設(shè)計技術(shù)（如貪心法、分治策略、動態(tài)規(guī)劃、網(wǎng)絡(luò)流、近似算法、隨機算法等）為主線來安排教學(xué)內(nèi)容，突出了算法設(shè)計的思想和分析的基本原則，為從事實際問題的算法設(shè)計與分析工作提供清晰的、整體的思路和方法。通過使用豐富的教學(xué)方法，不但深入系統(tǒng)地闡述算法設(shè)計與分析的理論，而且給出大量的典型范例和參考文獻。以算法為主線來處理算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系。這種教學(xué)安排突出了算法設(shè)計的中心思想，避免了與數(shù)據(jù)結(jié)構(gòu)課程在內(nèi)容上的重復(fù)，更加適合于教學(xué)計劃。使得教學(xué)內(nèi)容由淺入深，由具體到抽象，從算法設(shè)計技術(shù)與分析方法自然過渡到計算復(fù)雜性理論，選配大量難度適當?shù)木毩?xí)，并給出求解范例。從而達到相應(yīng)的教學(xué)目標。2．課程介紹2.1課程的性質(zhì)計算機科學(xué)是一種創(chuàng)造性思維活動，其教育必須面向設(shè)計。計算機算法設(shè)計與分析正是一門面向設(shè)計，且處于計算機學(xué)科核心地位的教育課程。設(shè)計一個高效的程序不僅需要編程小技巧，更需要合理的數(shù)據(jù)組織和清晰高效的算法，這正是計算機科學(xué)領(lǐng)域里數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計所研究的主要內(nèi)容。算法設(shè)計這門課程就是通過對常用的，有代表性的算法的研究，讓學(xué)生理解并且掌握算法設(shè)計的基本技術(shù)。培養(yǎng)學(xué)生分析算法復(fù)雜度的初步能力，鍛煉學(xué)生的邏輯思維能力和想象能力，讓學(xué)生了解算法理論的發(fā)展。通過該課程的學(xué)習(xí)提高學(xué)生運用算法理論解決其它學(xué)科的實際問題，從而不斷提高學(xué)生的獨立科研能力以及理論聯(lián)系實際的動手操作能力。2.2課程在學(xué)科專業(yè)結(jié)構(gòu)中的地位、作用“算法設(shè)計”課程是計算機科學(xué)與技術(shù)專業(yè)的核心專業(yè)基礎(chǔ)課之一，在計算機專業(yè)人才培養(yǎng)中具有重要的意義。教學(xué)內(nèi)容的難度大，涉及的學(xué)生人數(shù)多。該課程在教學(xué)內(nèi)容、教學(xué)手段、實驗教學(xué)、課程考核、教研教改、師資隊伍、網(wǎng)絡(luò)資源建設(shè)、師生科研工作等方面已形成了有優(yōu)勢的教學(xué)體系。該課程一直采用國家教育部推薦的優(yōu)秀教材，教學(xué)內(nèi)容豐富。先進，主講教師的課堂教學(xué)十分注重理論聯(lián)系實際，信息量大，重點突出，條理清晰，語言生動，互動和啟發(fā)性強，運用多媒體教學(xué)手段恰當，網(wǎng)絡(luò)教學(xué)資源較豐富。課外輔導(dǎo)、答疑、實驗指導(dǎo)、考核和教學(xué)管理規(guī)范，文檔齊全。該課程較重視教學(xué)改革研究，教學(xué)內(nèi)容和考核形式有利于培養(yǎng)學(xué)生的學(xué)習(xí)能力和創(chuàng)新精神?！八惴ㄔO(shè)計”這門課程的教學(xué)難度大，但課程組的老師能夠以對學(xué)生高度負責的態(tài)度認真對待每一個教學(xué)環(huán)節(jié)，注重教學(xué)內(nèi)容和教學(xué)方法研究，加強課外輔導(dǎo)和答疑等輔助性教學(xué)環(huán)節(jié)，盡可能及時解決學(xué)生學(xué)習(xí)中存在的問題，學(xué)生反映好。該教研室還經(jīng)常舉行公開課和教學(xué)評價，充分聽取廣大老師的意見，力求對教學(xué)精益求精。2.3課程的前沿及發(fā)展趨勢當今時代，在純粹科學(xué)研究，通信、交通運輸、工業(yè)設(shè)計和企事業(yè)管理部門，在社會軍事、政治和商業(yè)的斗爭中涌現(xiàn)出大量的算法問題。若按經(jīng)典的純粹數(shù)學(xué)家們所熟悉的窮舉方法求解，則計算時間動輒達到天文數(shù)字，根本沒有實用價值。數(shù)學(xué)界許多有經(jīng)驗的人認為對于這些問題根本上就不存在完整、精確、而又不是太慢的求解算法?？赡苁沁@個世紀最重要的數(shù)學(xué)問題了。算法可以看作是解決問題的一類特殊方法，它不是問題的答案，而是經(jīng)過精確定義的、用來獲得答案的求解過程。因此，無論是否涉及計算機，特定的算法設(shè)計及技術(shù)都可以看作是問題求解的有效策略。著名的計算機科學(xué)家史努特是這樣論述這個問題的：受過良好訓(xùn)練的計算機科學(xué)家知道如何處理算法，如何構(gòu)造算法、操作算法、理解算法以及分析算法。現(xiàn)在設(shè)計算法，主要是方便編程進行運算解決實際問題，因為電腦只會簡單的運算，不轉(zhuǎn)化成它的語言，它無法識別，從電腦問世以來，各種層出不窮的新電腦的產(chǎn)生，但是不管有多少品牌的電腦，算法始終是靈魂，沒有了程序，沒有了算法，它就是一個普通的硬件，甚至什么都做不了，現(xiàn)在算法也是越來越復(fù)雜，但是復(fù)雜的算法是建立在簡單的算法基礎(chǔ)之上的，不過就算是最簡單的算法，比如描述輸入、輸出，已經(jīng)是最簡單了，也需要人來編寫算法，而計算機自己是無法編寫算法，更不用說轉(zhuǎn)化成程序進行運算了。如何讓電腦成為真正的智能，這是現(xiàn)在全世界都在關(guān)注的，如果僅僅是移入芯片，讓電腦執(zhí)行各種已經(jīng)設(shè)計好的程序，按部就班按照人類的思維進行運算，那也就不算只能，頂多是仿智能，所以，未來算法的走向，是如何能使電腦也會編寫算法，轉(zhuǎn)化成程序，也就是自動思考，解決我們?nèi)祟愄岢龅膯栴}。算法可以看作是解決問題的一類特殊方法，它不是問題的答案，而是經(jīng)過精確定義的、用來獲得答案的求解過程。因此，無論是否涉及計算機，特定的算法設(shè)計及技術(shù)都可以看作是問題求解的有效策略。著名的計算機科學(xué)家史努特是這樣論述這個問題的：受過良好訓(xùn)練的計算機科學(xué)家知道如何處理算法，如何構(gòu)造算法、操作算法、理解算法以及分析算法。 2.4學(xué)習(xí)本課程的必要性“計算機既是數(shù)學(xué)的創(chuàng)造物,又是數(shù)學(xué)的創(chuàng)造者”,而算法既是計算機理論和實踐的核心,也是數(shù)學(xué)的最基本內(nèi)容之一。甚至有人說,數(shù)學(xué)學(xué)習(xí)的主要作用是形成“算法思維”。算法有著悠久的發(fā)展歷史,中國古代數(shù)學(xué)曾經(jīng)以算法為特色,取得了舉世矚目的輝煌成就。在已經(jīng)逐步進入信息化社會的今天,算法的基本知識、方法、思想日益融入人們社會生活的方方面面,已經(jīng)也應(yīng)該成為現(xiàn)代人所應(yīng)具備的一種基本素質(zhì)。算法學(xué)習(xí)有助于我們?nèi)娴睦斫膺\算能力很多時候,人們對運算存在一些誤解,認為運算就是按照各種運算法則進行加、減、乘、除,從而學(xué)習(xí)運算就是背誦書本中給出的計算法則,形成一些基本的計算技巧,也就是說,能夠根據(jù)熟記的法則,迅速的計算給定式子的正確答案。實際上,按照算法規(guī)則進行邏輯推理而獲得正確結(jié)果僅僅是計算的很小的一個方面,更重要的是,在運算中構(gòu)造、設(shè)計、選擇一個合理的算法,理解相應(yīng)的算理。在算法學(xué)習(xí)中,我們要讓學(xué)生給出一個問題的不同算法,并比較這些算法的優(yōu)劣,并作出選擇,從而提高效率,而這個過程才是一個真正的運算過程,因此算法學(xué)習(xí)使得我們更加全面的理解運算能力。算法學(xué)習(xí)能夠培養(yǎng)學(xué)生的邏輯思維能力我們常常說數(shù)學(xué)是思維的體操,能夠訓(xùn)練學(xué)生的思維能力。算法作為數(shù)學(xué)的一個基本內(nèi)容,在培養(yǎng)學(xué)生的邏輯思維能力上能夠發(fā)揮重要的作用。算法是解題方法的精確描述。算法一方面具有具體化、程序化、機械化的特點,同時又有高度抽象性、概括性和精確性。因此,將解決具體問題的方法整理成算法的過程是一個條理化,精確化和邏輯化的過程,有助于培養(yǎng)學(xué)生的邏輯思維能力。3．教師簡介4．先修課程數(shù)學(xué)分析、高等代數(shù)、C語言、離散數(shù)學(xué)、程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)5．課程目標5.1知識與技能方面通過對本課程的學(xué)習(xí)與研究，使學(xué)生掌握算法設(shè)計的基本知識，培養(yǎng)對算法的計算復(fù)雜性正確分析的能力，為獨立設(shè)計算法和對算法復(fù)雜性分析奠定堅實的理論基礎(chǔ)，對學(xué)生將來從事計算機系統(tǒng)結(jié)構(gòu)、系統(tǒng)軟件和應(yīng)用軟件的研究與開發(fā)提供一個廣泛扎實的計算機算法知識基礎(chǔ)。在剛開始學(xué)習(xí)的時候就應(yīng)該弄清楚各種變量的定義方法,還要掌握各種類型的輸入、輸出格式。這一步做到后，上機就沒有多大的問題了。在對函數(shù)的學(xué)習(xí)過程中，一定要弄明白函數(shù)的作用和具體格式。值得強調(diào)的是在寫循環(huán)程序時，一定要弄清楚循環(huán)的條件。對每一個知識點，都應(yīng)該立即編出對應(yīng)的程序，有時可能還會有語法錯誤，碰到更好的方法也可以試一下，很多時候你想想代碼怎么寫和你真的寫出來了是有很大的差距的。最終通過認真學(xué)習(xí)掌握最基本的知識點，打好堅實的理論基礎(chǔ)，這一點尤其重要。；另外還要掌握一定的算法設(shè)計技能，這也是學(xué)習(xí)這門課程的目的。堅實的理論基礎(chǔ)加上靈活的算法技巧才有可能設(shè)計出可靠有效的算法。5.2過程與方法方面對每一教學(xué)內(nèi)容，首先介紹一種算法設(shè)計策略的基本思想，然后從解決計算機科學(xué)和應(yīng)用中的實際問題入手，由簡到繁地描述幾個經(jīng)典的精巧算法。同時對每個算法所需的時間和空間進行分析，使學(xué)生既能學(xué)到一些常用的精巧算法，又能通過對算法設(shè)計策略的反復(fù)應(yīng)用，牢固掌握這些算法設(shè)計的基本策略，以期收到融會貫通之效。在為各種算法設(shè)計策略選擇用于展示其設(shè)計思想與技巧的具體應(yīng)用問題時，有意義重復(fù)選擇某些經(jīng)典問題，使學(xué)生能深刻地體會到一個問題可以用多種設(shè)計策略求解。同時通過對解同一問題的不同算法的比較，使學(xué)生更容易體會到每一種具體算法的設(shè)計要點。隨著內(nèi)容的逐步展開，學(xué)生也將進一步感受到綜合應(yīng)用多種設(shè)計策略可以更有效地解決問題。要寫出一個好的算法絕不是一蹴而就的事情，它需要不斷的修改不斷的完善，這也是自我能力提高的一個過程。所以，學(xué)生應(yīng)該認真對待每一個算法的完成過程，以及它涉及到的不同方法。即使最后的計算結(jié)果不是那么的理想，但是我們知道之后應(yīng)該如何改進，這個過程需要每一個算法的設(shè)計者自己去體會和領(lǐng)悟，只有這樣才能夠從每一個算法的設(shè)計過程中有所收獲有所提高，只有這樣才真正的達到了教學(xué)的目標。5.3情感、態(tài)度與價值觀方面教師要注重學(xué)生的情感體驗和實踐。課程目標中無論是熱愛集體具有責任感，競爭意識，團結(jié)合作和奉獻精神等，都需要學(xué)生的獨立思考和生活體驗，需要在教學(xué)中不斷創(chuàng)造條件促進學(xué)生的實踐，豐富他們的情感體驗，感悟和理解社會的思想道德價值要求，逐步形成正確的道德觀和良好的行為習(xí)慣。教師要注意學(xué)生的自主學(xué)習(xí)。學(xué)生只有主動地對教材所涉及到的方方面面內(nèi)容進行探究，才能與老師上課所提到的問題產(chǎn)生共鳴，并在經(jīng)過自覺的加工組織后，最終升華至健康積極的價值觀層面。在教學(xué)中要突出情感、態(tài)度、價值觀的主導(dǎo)地位，學(xué)生的品德心理的發(fā)展是以認知、情感、行為三者為主體的綜合發(fā)展。但是，長期以來我們更多的是看重學(xué)生的認知發(fā)展，關(guān)心學(xué)生對某個結(jié)論是否記住，記得是否準確，對某項技能是否掌握，運用得是否得心應(yīng)手，而忽略了對學(xué)生在認知過程中產(chǎn)生的情感體驗和正確得價值觀的形成。造成學(xué)生的學(xué)習(xí)情緒低下，知行不能統(tǒng)一。因此，教師在教學(xué)過程中應(yīng)注重引導(dǎo)和促進學(xué)生在知情行方面的和諧發(fā)展，充分發(fā)揮情感和態(tài)度價值觀的主導(dǎo)作用，備課中首先考慮如何以認知的手段達到情感、態(tài)度、價值觀的目標，做到以情導(dǎo)行。具體來說，就是處理好新教材中的探究園、實踐與評價和心靈導(dǎo)航的關(guān)系，帶領(lǐng)學(xué)生通過活動的探究來領(lǐng)會導(dǎo)航上的知識點。盡量設(shè)立多種活動來激發(fā)學(xué)生的情感體驗。教師要通過創(chuàng)設(shè)一定的情景或開展多項活動來引起學(xué)生的注意、產(chǎn)生興趣，表示認同，愿意接受，同時引起情緒上的變化，并產(chǎn)生情感上的體驗。通過這些活動和體驗，引起學(xué)生對所學(xué)內(nèi)容的注意和興趣，產(chǎn)生想學(xué)的需要。值得注意的是，在這一環(huán)節(jié)，教師要善于烘托情感氛圍，選擇恰當?shù)囊妆粚W(xué)生接受的切入點。在選擇切入點時，既要考慮其中具有的豐富情感因素；又要考慮到學(xué)生實際的心理發(fā)展水平。通過引導(dǎo)學(xué)生自主學(xué)習(xí)，自我探索來內(nèi)化學(xué)生的態(tài)度和價值觀。學(xué)生在情感體驗的過程中，會伴隨著一些語言和行為上的贊同、反對等態(tài)度、價值觀的傾向性，但是這些贊同和反對還僅僅是一種受情感或情緒的影響而產(chǎn)生的表面的傾向，很容易受他人的言語影響而改變。因此，還需要教師引導(dǎo)他們形成正確的評價，并把這種評價內(nèi)化成為他們固有的價值觀。而這種內(nèi)化需要靠學(xué)生自己去探索，不斷深化才能完成。這樣經(jīng)過學(xué)生的自我探索，就把基于情感情緒而產(chǎn)生的態(tài)度價值觀傾向性，通過有機合理的整合，不斷深化形成較為穩(wěn)固系統(tǒng)的價值觀。6．課程內(nèi)容6.1課程的內(nèi)容概要 算法及算法復(fù)雜性基本概念，算法描述，有效算法最常用的設(shè)計策略——遞歸和分治法，動態(tài)規(guī)劃法的設(shè)計要點與適用性，貪心算法，回溯法和分支限界法，許多難解問題的高效算法——概率算法，以及NP完全理論和NP難問題的近似解法。傳統(tǒng)算法實例分析，算法領(lǐng)域研究熱點介紹。本課程在學(xué)習(xí)之前，最好具有離散數(shù)學(xué)、程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)等方面的知識。什么是算法設(shè)計，如何進行算法設(shè)計，需要準備哪些預(yù)備知識，算法及其重要特性，算法的描述方法以及算法設(shè)計的一般過程，對于算法設(shè)計的概念的掌握程度要求了解，明白應(yīng)該怎么做，怎樣才能設(shè)計好一個算法，從學(xué)習(xí)概念學(xué)生可以了解什么是算法設(shè)計，如何通過分析實際問題設(shè)計出優(yōu)良，可操作的高效的算法。在此基礎(chǔ)上通過本課程的學(xué)習(xí)，掌握算法的定義及基本概念、計算模型和復(fù)雜度的質(zhì)量；為分析算法的復(fù)雜性做準備，在這個基礎(chǔ)上，學(xué)習(xí)一些常用的算法設(shè)計策略，掌握其基本思想和相應(yīng)算法，編制出相應(yīng)程序上機調(diào)試。6.2教學(xué)重點、難點（1）遞歸的概念；分治法的基本思想；分治法的典型例子，如：二分搜索技術(shù)、大整數(shù)乘法、最接近點對問題。了解遞歸概念和分治法的基本思想，以及各種典型例子的分治思想，要求可以熟練的編寫出按分治法設(shè)計的算法問題。（2）矩陣連乘問題；動態(tài)規(guī)劃算法的基本要素；動態(tài)規(guī)劃法的典型例子，如：最長公共子序列、凸多邊形最優(yōu)三角剖分、圖像壓縮、電路布線、流水作業(yè)調(diào)度、0－1背包問題、最優(yōu)二叉搜索樹。（3）了解動態(tài)規(guī)劃的基本思想，以及各種典型例子的動態(tài)規(guī)劃思想，要求可以熟練的編寫出按動態(tài)低歸設(shè)計的算法問題。活動安排問題；貪心算法的基本要素；貪心算法的典型例子，如：最優(yōu)裝載、哈夫曼編碼、單源最短路徑、最小生成樹。（4）了解貪心算法的基本思想，以及各種典型例子的貪心算法思想，如:活動安排問題，最優(yōu)裝載等。要求可以熟練的編寫出按貪心算法設(shè)計的算法問題?；厮莘ǖ乃惴蚣埽换厮莘ǖ牡湫屠?，如：裝載問題、批處理作業(yè)調(diào)度、符號三角形問題、n后問題、0－1背包問題、圖的m著色問題、旅行售貨員問題、圓排列問題、電路板排列問題。（5）了解回溯法的基本思想，以及各種典型例子的回溯思想，如：裝載問題，批處理作業(yè)調(diào)度，n后問題等。要求可以熟練的編寫出按回溯法設(shè)計的算法問題。分支限界法的基本思想；分支限界法的典型例子，如：單源最短路徑問題、裝載問題、布線問題、0－1背包問題、最大團問題、旅行售貨員問題、電路板排列問題、批處理作業(yè)調(diào)度。（6）了解分支限界法的基本思想，以及各種典型例子的分支限界法思想，如：單源最短路徑問題、布線問題、0-1背包問題等。要求可以熟練的編寫出按分支限界法設(shè)計的算法問題。隨機數(shù)；數(shù)值概率算法；舍伍德算法；拉斯維加斯算法；蒙特卡羅算法。（7）了解隨機數(shù)與偽隨機的概念與產(chǎn)生；掌握數(shù)值概率算法，用隨機投點法計算∏值、計算定積分等；掌握舍伍德算法，并用之解決線性時間選擇和跳躍表等問題；掌握拉斯維加斯算法，并用之解決n后問題和整數(shù)因子分解問題等；掌握蒙特卡羅算法，并用之解決素數(shù)測試等問題。6.3學(xué)時安排理論課時6第一章：算法設(shè)計的基本概念第二章：NP完全理論第一節(jié)：什么是NP問題第一節(jié)：NP問題的一般解法理論課時6第二章：NP完全理論第二節(jié)：NP問題的求解方法概述第三章：蠻力法第一節(jié)：什么是蠻力法及蠻力法的設(shè)計思路第一節(jié)：蠻力法計算步驟理論課時6第三章：蠻力法第二節(jié)：查找問題中的蠻力法第三章：蠻力法第三節(jié)：排序問題中的蠻力法第三節(jié)：排序問題中的蠻力法計算步驟理論課時6第三章：蠻力法第四節(jié)：組合和圖論問題中的蠻力法第四節(jié)：組合和圖論問題中的蠻力法計算步驟習(xí)題課理論課時6第四章：分治法第一節(jié)：分治法的基本概念和設(shè)計思想第四章：分治法第二節(jié)：遞歸算法第二節(jié)：遞歸算法計算步驟理論課時6第四章：分治法第三節(jié)：排序問題中的分治法第四章：分治法第四節(jié)：組合問題中的分治法第四節(jié)：組合問題中的分治法計算步驟理論課時6第四章：分治法第五節(jié)：幾何問題中的分治法第五節(jié)：幾何問題中的分治法計算步驟習(xí)題課理論課時6第五章：減治法第一節(jié)：基本概念及其在查找問題中的應(yīng)用第五章：減治法第二節(jié)：排序和組合問題中的減治法第二節(jié)：排序和組合問題中的減治法計算步驟7.課程實施7.1教學(xué)單元一7.1.1教學(xué)日期第一周周一、周二、周四7.1.這一個教學(xué)單元學(xué)生要學(xué)習(xí)算法設(shè)計的概念，即什么是算法設(shè)計，如何進行算法設(shè)計，需要準備哪些預(yù)備知識，算法及其重要特性，算法的描述方法以及算法設(shè)計的一般過程，對于算法設(shè)計的概念的掌握程度要求了解，明白應(yīng)該怎么做，怎樣才能設(shè)計好一個算法，從學(xué)習(xí)概念學(xué)生可以了解什么是算法設(shè)計，如何通過分析實際問題設(shè)計出優(yōu)良，可操作的高效的算法。第二個要學(xué)習(xí)的部分就是NP完全理論，NP完全理論是理論信息學(xué)中的計算復(fù)雜度理論領(lǐng)域里的NPC，簡單的說，如果任何一個NP問題都能通過一個多項式時間算法轉(zhuǎn)換為某個NP問題，那么這個NP問題就稱為NPC問題。換言之，如果這個問題解決了，那么所有NP問題也都能解決了。第一個被證明是NPC的問題是3SAT問題。首先需要介紹P(Polynomial,多項式)問題.P問題是可以在多項式時間內(nèi)被確定機(通常意義的計算機)解決的問題.NP(Non-DeterministicPolynomial,非確定多項式)問題,是指可以在多項式時間內(nèi)被非確定機(他可以猜,他總是能猜到最能滿足你需要的那種選擇,如果你讓他解決n皇后問題,他只要猜n次就能完成----每次都是那么幸運)解決的問題.這里有一個著名的問題----千禧難題之首,是說P問題是否等于NP問題,也即是否所有在非確定機上多項式可解的問題都能在確定機上用多項式時間求解。學(xué)生需要初步了解什么是NP完全問題。7.1.3教學(xué)內(nèi)容（含重點、難點）首先講算法設(shè)計的概念，分為五個部分。第一部分為什么要學(xué)習(xí)算法，第二部分是算法及其重要特性，第三部分是算法的描述方法，第四部分是算法設(shè)計的一般過程，第五部分是如何設(shè)計算法，章建躍博士曾經(jīng)說過：“理解數(shù)學(xué)”是第一基石。教什么比怎么教更重要，數(shù)學(xué)課要教數(shù)學(xué)，這就要求教師自己先理解好數(shù)學(xué)：了解數(shù)學(xué)的背景，掌握概念的邏輯意義，理解內(nèi)容所反映的思想方法，把握概念的“多元聯(lián)系表示”，挖掘知識所蘊含的科學(xué)方法、理性精神等價值資源。在這節(jié)課的備課過程中，教師認真研究了在本節(jié)課之前，學(xué)生學(xué)習(xí)了哪些知識，進而發(fā)現(xiàn)，學(xué)生已經(jīng)積累了大量的算法的實踐經(jīng)驗，只不過沒有明確提出“算法”這一概念。同時，為了進一步培養(yǎng)學(xué)生歸納總結(jié)、提煉概括的能力，因而教師沒有像一般老師那樣從二元一次方程組的解法提煉出算法的概念，而是通過教師講一個有嚴格程序和步驟的問題，引導(dǎo)學(xué)生回顧相關(guān)實例（“坐標方法”解決幾何問題的三部曲、求圓的方程常用“待定系數(shù)法”，那么它的大致步驟是怎樣的、實際問題使用數(shù)學(xué)建模的步驟、給點精確度，用二分法求函數(shù)零點近似值的步驟），再從這些實例中提煉出算法的概念。這樣也就充分體現(xiàn)了從學(xué)生“最近發(fā)展區(qū)”設(shè)計問題，從而提高了課堂教學(xué)的有效性。本節(jié)課“數(shù)學(xué)味道”特別濃，充分體現(xiàn)了“數(shù)學(xué)課要教數(shù)學(xué)”．一方面，本節(jié)課在選材上沒有把算法泛化，所選的實例全都是數(shù)學(xué)問題；另一方面，本節(jié)課更注重了數(shù)學(xué)思想方法的滲透，充分挖掘出蘊含在算法概念之中的算法思想，通過實例讓學(xué)生體會算法思想，再通過算法的設(shè)計讓學(xué)生運用算法特征設(shè)計具體案例，達到培養(yǎng)學(xué)生理性思維能力的目的。本節(jié)課，教師在充分挖掘了教學(xué)內(nèi)容的內(nèi)在聯(lián)系，充分分析了學(xué)情后，確定的教學(xué)目標具有具體而準確、科學(xué)而有效的特點。這節(jié)課的教學(xué)目標不像一般課教學(xué)目標的那樣抽象而空泛，而是具體、明確的，每一個教學(xué)目標都與具體教學(xué)流程遙相呼應(yīng)，都可以落實到具體的教學(xué)流程之中。而且目標中將“知識目標”、“能力目標”、“情感目標”融為一體，充實而準確．因此，這節(jié)課的教學(xué)目標是具體而準確的。這節(jié)課的教學(xué)目標符合學(xué)生“認知規(guī)律”以遞進形式呈現(xiàn)：“體會、了解、初步形成——認識、完善——理解、準確把握、學(xué)會”，而且在師生的共同努力下，跳一跳就可以達到，因而該目標是科學(xué)的、有效的。接著講NP完全問題，這里有一個著名的問題----千禧難題之首,是說P問題是否等于NP問題,也即是否所有在非確定機上多項式可解的問題都能在確定機上用多項式時間求解。這樣一來,只要我們找到一個NPC問題的多項式解,所有的NP問題都可以多項式時間內(nèi)劃歸成這個NPC問題,再用多項式時間解決,這樣NP就等于P了。換一種說法,如果一個問題的復(fù)雜度是該問題的一個實例規(guī)模n的多項式函數(shù)，則這種可以在多項式時間內(nèi)解決的問題屬于P類問題.通俗地稱所有復(fù)雜度為多項式時間的問題為易解的問題類，否則為難解的問題。有些問題很難找到多項式時間的算法（或許根本不存在）。例如“找出無向圖中哈密頓回路”問題。但如果給了該問題的一個答案，可以在多項式時間內(nèi)判斷這個答案是否正確。例如說對于哈密頓回路問題，給一個任意的回路，很容易判斷它是否是哈密頓回路（只要看是不是所有的頂點都在回路中就可以了）。這里給出NP問題的另一個定義,這種可以在多項式時間內(nèi)驗證一個解是否正確的問題稱為NP問題，亦稱為驗證問題類。簡單的說，存在多項式時間的算法的一類問題，稱之為P類問題；而像梵塔問題，推銷員旅行問題等問題，至今沒有找到多項式時間算法解的一類問題，稱之為NP問題。同時，P類問題是NP問題的一個子集。本單元重點是算法設(shè)計的概念，難點是NP完全理論。7.1.算法設(shè)計的概念里主要講解算法設(shè)計的一般過程，算法是問題的解決方案，這個解決方案本身并不是問題的答案，而是能獲得答案的指令序列。不言而喻，由于實際問題千奇百怪，問題求解的方法千變?nèi)f化，所以，算法的設(shè)計過程是一個靈活的充滿智慧的過程，他要求設(shè)計人員根據(jù)實際情況，，具體情況具體分析。可以肯定的是，發(fā)明算法是一個非常具有創(chuàng)造性和值得付出精力的過程。在設(shè)計算法時，遵循下列步驟可以在一定程度上指導(dǎo)算法的設(shè)計。第一個是理解問題，在面對一個算法任務(wù)時，算法設(shè)計者往往不能準確的理解要求他做的是什么，對算法希望實現(xiàn)什么只有一個大致的想法就匆忙地落筆寫算法，其后果往往是寫出的算法漏洞百出。在設(shè)計算法是需要做的第一件事就是完全理解要解決的問題，仔細閱讀問題的描述，手工處理一些小例子。對設(shè)計算法來說，這是一項重要的技能：準確的理解算法的輸入是什么？要求算法做的是什么？即明確算法的入口和出口，這是設(shè)計算法的切入點。第二個部分是預(yù)計所有可能的輸入，算法的輸入確定了該算法所解問題的一個實例。事實上，無法保證一個算法永遠不會遇到一個錯誤的輸入，一個對大部分輸入都運行正確而只有一個輸入不行的算法，就像一顆等待爆炸的炸彈。第三個部分是在精確解和近似解之間做選擇，計算機科學(xué)研究的目標是用計算機來求解人類所面臨的各種問題。但是，有些問題無法求得精確解，例如計算pi值，求平方根，解非線性方程，求定積分等；有些問題由于其固有的復(fù)雜性，求精確解需要花費太長的時間，其中最著名的要算旅行商問題，此時，只能求出近似解，有時需要根據(jù)問題以及問題所受的資源限制，在近似解和精確解之間做選擇。第四部分是確定適當?shù)臄?shù)據(jù)結(jié)構(gòu)。第五部分是算法設(shè)計技術(shù)。第六部分是描述算法。第七部分是跟蹤算法。第八部分是分析算法的效率。最后一部分是根據(jù)算法編寫代碼。對于NP完全問題，首先需要介紹P(Polynomial,多項式)問題.P問題是可以在多項式時間內(nèi)被確定機(通常意義的計算機)解決的問題.NP(Non-DeterministicPolynomial,非確定多項式)問題,是指可以在多項式時間內(nèi)被非確定機(他可以猜,他總是能猜到最能滿足你需要的那種選擇,如果你讓他解決n皇后問題,他只要猜n次就能完成----每次都是那么幸運)解決的問題.這里有一個著名的問題----千禧難題之首,是說P問題是否等于NP問題,也即是否所有在非確定機上多項式可解的問題都能在確定機上用多項式時間求解。這樣一來,只要我們找到一個NPC問題的多項式解,所有的NP問題都可以多項式時間內(nèi)劃歸成這個NPC問題,再用多項式時間解決,這樣NP就等于P了。換一種說法,如果一個問題的復(fù)雜度是該問題的一個實例規(guī)模n的多項式函數(shù)，則這種可以在多項式時間內(nèi)解決的問題屬于P類問題.通俗地稱所有復(fù)雜度為多項式時間的問題為易解的問題類，否則為難解的問題。有些問題很難找到多項式時間的算法（或許根本不存在）。例如“找出無向圖中哈密頓回路”問題。但如果給了該問題的一個答案，可以在多項式時間內(nèi)判斷這個答案是否正確。例如說對于哈密頓回路問題，給一個任意的回路，很容易判斷它是否是哈密頓回路（只要看是不是所有的頂點都在回路中就可以了）。這里給出NP問題的另一個定義,這種可以在多項式時間內(nèi)驗證一個解是否正確的問題稱為NP問題，亦稱為驗證問題類。簡單的說，存在多項式時間的算法的一類問題，稱之為P類問題；而像梵塔問題，推銷員旅行問題等問題，至今沒有找到多項式時間算法解的一類問題，稱之為NP問題。同時，P類問題是NP問題的一個子集。7.1.5教學(xué)方法主要是采用ppt教學(xué)，這樣形象直觀，允許學(xué)生有不懂的問題馬上提出來，這樣互動會及時解決學(xué)生的疑惑，然后就是舉例子，這樣讓學(xué)生頭腦里有一個大致的印象，可以理解得更深，當然課講完了后，就會給學(xué)生布置作業(yè)及課后反思，這樣才能進一步提升對所學(xué)知識的鞏固，不會遺忘，還會思考些新的東西，這樣，就可以達到教與學(xué)真正的溝通。首先它是指具體的教學(xué)方法，從屬于教學(xué)方法論，是教學(xué)方法論的一個層面。教學(xué)方法論由教學(xué)方法指導(dǎo)思想、基本方法、具體方法、教學(xué)方式四個層面組成。教學(xué)方法包括教師教的方法（教授法）和學(xué)生學(xué)的方法（學(xué)習(xí)方法）兩大方面，是教授方法與學(xué)習(xí)方法的統(tǒng)一。教授法必須依據(jù)學(xué)習(xí)法，否則便會因缺乏針對性和可行性而不能有效地達到預(yù)期的目的。但由于教師在教學(xué)過程中處于主導(dǎo)地位，所以在教法與學(xué)法中，教法處于主導(dǎo)地位。教學(xué)方法不同于教學(xué)方式，但與教學(xué)方式有著密切的聯(lián)系。教學(xué)方式是構(gòu)成教學(xué)方法的細節(jié)，是運用各種教學(xué)方法的技術(shù)。任何一種教學(xué)方法都由一系列的教學(xué)方式組成，可以分解為多種教學(xué)方式；另一方面，教學(xué)方法是一連串有目的的活動，能獨立完成某項教學(xué)任務(wù)，而教學(xué)方式只被運用于教學(xué)方法中，并為促成教學(xué)方法所要完成的教學(xué)任務(wù)服務(wù)，其本身不能完成一項教學(xué)任務(wù)。7.1.作業(yè)就是算法設(shè)計的概念后面的全部習(xí)題，課后反思主要探討背包問題。背包問題(Knapsackproblem)是在1978年由Merkel和Hellman提出的，是一種組合優(yōu)化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。相似問題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學(xué)，計算復(fù)雜性理論、密碼學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中。也可以將背包問題描述為決定性問題，即在總重量不超過W的前提下，總價值是否能達到V？背包問題是熟知的不可計算問題，背包體制以其加密，解密速度快而引人注目。但是，大多數(shù)一次背包體制均被破譯了，因此很少有人使用它。它的主要思路是假定某人擁有大量物品，重量各不同。此人通過秘密地選擇一部分物品并將它們放到背包中并加密消息。背包中的物品總重量是公開的，所有可能的物品也是公開的，但背包中的物品是保密的。附加一定的限制條件，給出重量，而要列出可能的物品，在計算上是不可實現(xiàn)的。背包問題是熟知的不可計算問題，背包體制以其加密，解密速度快而引人注目。但是，大多數(shù)一次背包體制均被破譯了，因此很少有人使用它。有N件物品和一個容量為V的背包。第i件物品的重量是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大。這是最基礎(chǔ)的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}?？梢詨嚎s空間，f[v]=max{f[v],f[v-c[i]]+w[i]}這個方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價值為f[i-1][v]；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。注意f[v]有意義當且僅當存在一個前i件物品的子集，其費用總和為v。所以按照這個方程遞推完畢后，最終的答案并不一定是f[N][V]，而是f[N][0..V]的最大值。如果將狀態(tài)的定義中的“恰”字去掉，在轉(zhuǎn)移方程中就要再加入一項f[v-1]，這樣就可以保證f[N][V]就是最后的答案。至于為什么這樣就可以，由你自己來體會了。以上方法的時間和空間復(fù)雜度均為O(N*V），其中時間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到O(N）。先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán)i=1..N，每次算出來二維數(shù)組f[i][0..V]的所有值。那么，如果只用一個數(shù)組f[0..V]，能不能保證第i次循環(huán)結(jié)束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢？[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[v]時（也即在第i次主循環(huán)中推f[v]時）能夠得到f[v]和f[v-c[i]]的值呢？事實上，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態(tài)f[i-1][v-c[i]]的值。偽代碼如下：ori=1..Nforv=V..0f[v]=max{f[v],f[v-c[i]]+w[i]};其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當于我們的轉(zhuǎn)移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因為的f[v-c[i]]就相當于原來的f[i-1][v-c[i]]。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學(xué)習(xí)只用一維數(shù)組解01背包問題是十分必要的。0/1背包問題是最基本的背包問題，它包含了背包問題中設(shè)計狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成0/1背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu)化的空間復(fù)雜度。這個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時的思路，令f[i,v]表示前i種物品恰放入一個容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣：f[i,v]=max{f[i,v-vi]+wi,f[i-1,v]}。這跟01背包問題一樣有O(N*V）個狀態(tài)需要求解，但求解每個狀態(tài)的時間則不是常數(shù)了，求解狀態(tài)f[v]的時間是O(v/c），總的復(fù)雜度是超過O(VN）的。將01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進這個復(fù)雜度。完全背包問題有一個很簡單有效的優(yōu)化，是這樣的：若兩件物品i、j滿足c<=c[j]且w>=w[j]，則將物品j去掉，不用考慮。這個優(yōu)化的正確性顯然：任何情況下都可將價值小體積高的j換成物美價廉的i，得到至少不會更差的方案。對于隨機生成的數(shù)據(jù)，這個方法往往會大大減少物品的件數(shù)，從而加快速度。然而這個并不能改善最壞情況的復(fù)雜度，因為有可能特別設(shè)計的數(shù)據(jù)可以一件物品也去不掉。既然01背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉(zhuǎn)化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c件，于是可以把第i種物品轉(zhuǎn)化為V/c件體積及價值均不變的物品，然后求解這個01背包問題。這樣完全沒有改進基本思路的時間復(fù)雜度，但這畢竟給了我們將完全背包問題轉(zhuǎn)化為01背包問題的思路：將一種物品拆成多件物品。你會發(fā)現(xiàn)，這個偽代碼與P01的偽代碼只有v的循環(huán)次序不同而已。為什么這樣一改就可行呢？首先想想為什么P01中要按照v=V..0的逆序來循環(huán)。這是因為要保證第i次循環(huán)中的狀態(tài)f[v]是由狀態(tài)f[v-c]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，依據(jù)的是一個絕無已經(jīng)選入第i件物品的子結(jié)果f[v-c]。而完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結(jié)果f[v-c]，所以就可以并且必須采用v=0..V的順序循環(huán)。這就是這個簡單的程序為何成立的道理。完全背包問題也是一個相當基礎(chǔ)的背包問題，它有兩個狀態(tài)轉(zhuǎn)移方程，分別在“基本思路”以及“O(VN）的算法“的小節(jié)中給出。希望你能夠?qū)@兩個狀態(tài)轉(zhuǎn)移方程都仔細地體會，不僅記住，也要弄明白它們是怎么得出來的，最好能夠自己想一種得到這些方程的方法。事實上，對每一道動態(tài)規(guī)劃題目都思考其方程的意義以及如何得來，是加深對動態(tài)規(guī)劃的理解、提高動態(tài)規(guī)劃功力的好方法。如果將P01、P02、P03混合起來。也就是說，有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數(shù)有一個上限（多重背包）。應(yīng)該怎么求解呢？如果再加上有的物品最多可以取有限次，那么原則上也可以給出O(VN）的解法：遇到多重背包類型的物品用單調(diào)隊列解即可。但如果不考慮超過NOIP范圍的算法的話，用P03中將每個這類物品分成O(logn）個01背包的物品的方法也已經(jīng)很優(yōu)了。有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且存之不論，但它在本講中已經(jīng)得到了充分的體現(xiàn)。本來01背包、完全背包、多重背包都不是什么難題，但將它們簡單地組合起來以后就得到了這樣一道一定能嚇倒不少人的題目。但只要基礎(chǔ)扎實，領(lǐng)會三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。有N種物品和一個容量為V的背包。第i種物品最多有n件可用，每件體積是c，價值是w。求解將哪些物品裝入背包可使這些物品的體積總和不超過背包容量，且價值總和最大。這題目和完全背包問題很類似?；镜姆匠讨恍鑼⑼耆嘲鼏栴}的方程略微一改即可，因為對于第i種物品有n+1種策略：取0件，取1件……取n件。令f[v]表示前i種物品恰放入一個容量為v的背包的最大權(quán)值，則：f[v]=max{f[v-k*c]+k*w|0<=k<=n}。復(fù)雜度是O(V*∑n）。另一種好想好寫的基該方法是轉(zhuǎn)化為01背包求解：把第i種物品換成n件01背包中的物品，則得到了物品數(shù)為∑n的01背包問題，直接求解，復(fù)雜度仍然是O(V*∑n）。但是我們期望將它轉(zhuǎn)化為01背包問題之后能夠像完全背包一樣降低復(fù)雜度。仍然考慮二進制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略——取0..n件——均能等價于取若干件代換以后的物品。另外，取超過n件的策略必不能出現(xiàn)。方法是：將第i種物品分成若干件物品，其中每件物品有一個系數(shù)，這件物品的費用和價值均是原來的費用和價值乘以這個系數(shù)。使這些系數(shù)分別為1,2,4,...,2^(k-1），n-2^k+1，且k是滿足n-2^k+1>0的最大整數(shù)。例如，如果n為13，就將這種物品分成系數(shù)分別為1,2,4,6的四件物品。分成的這幾件物品的系數(shù)和為n，表明不可能取多于n件的第i種物品。另外這種方法也能保證對于0..n間的每一個整數(shù)，均可以用若干個系數(shù)的和表示，這個證明可以分0..2^k-1和2^k..n兩段來分別討論得出，并不難，希望你自己思考嘗試一下。這樣就將第i種物品分成了O(logn）種物品，將原問題轉(zhuǎn)化為了復(fù)雜度為O(V*∑logn）的01背包問題，是很大的改進。多重背包問題同樣有O(VN）的算法。這個算法基于基本算法的狀態(tài)轉(zhuǎn)移方程，但應(yīng)用單調(diào)隊列的方法使每個狀態(tài)的值可以以均攤O⑴的時間求解。由于用單調(diào)隊列優(yōu)化的DP已超出了NOIP的范圍，故本文不再展開講解。我最初了解到這個方法是在樓天成的“男人八題”幻燈片上。這里我們看到了將一個算法的復(fù)雜度由O(V*∑n）改進到O(V*∑logn）的過程，還知道了存在應(yīng)用超出NOIP范圍的知識的O(VN）算法。希望你特別注意“拆分物品”的思想和方法，自己證明一下它的正確性，并用盡量簡潔的程序來實現(xiàn)。二維費用的背包問題是指：對于每件物品，具有兩種不同的費用；選擇這件物品必須同時付出這兩種代價；對于每種代價都有一個可付出的最大值（背包容量）。問怎樣選擇物品可以得到最大的價值。設(shè)這兩種代價分別為代價1和代價2，第i件物品所需的兩種代價分別為a和b。兩種代價可付出的最大值（兩種背包容量）分別為V和U。物品的價值為w。費用加了一維，只需狀態(tài)也加一維即可。設(shè)f[v]表示前i件物品付出兩種代價分別為v和u時可獲得的最大價值。狀態(tài)轉(zhuǎn)移方程就是：fi[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}。如前述方法，可以只使用二維的數(shù)組：當每件物品只可以取一次時變量v和u采用逆序的循環(huán)，當物品有如完全背包問題時采用順序的循環(huán)。當物品有如多重背包問題時拆分物品。有時，“二維費用”的條件是以這樣一種隱含的方式給出的：最多只能取M件物品。這事實上相當于每件物品多了一種“件數(shù)”的費用，每個物品的件數(shù)費用均為1，可以付出的最大件數(shù)費用為M。換句話說，設(shè)f[v][m]表示付出費用v、最多選m件時可得到的最大價值，則根據(jù)物品的類型（01、完全、多重）用不同的方法循環(huán)更新，最后在f[0..V][0..M]范圍內(nèi)尋找答案。另外，如果要求“恰取M件物品”，則在f[0..V][M]范圍內(nèi)尋找答案。事實上，當發(fā)現(xiàn)由熟悉的動態(tài)規(guī)劃題目變形得來的題目時，在原來的狀態(tài)中加一維以滿足新的限制是一種比較通用的方法。希望你能從本講中初步體會到這種方法。這種背包問題的物品間存在某種“依賴”的關(guān)系。也就是說，i依賴于j，表示若選物品i，則必須選物品j。為了簡化起見，我們先設(shè)沒有某個物品既依賴于別的物品，又被別的物品所依賴；另外，沒有某件物品同時依賴多件物品。這個問題由NOIP2006金明的預(yù)算方案一題擴展而來。遵從該題的提法，將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個問題的簡化條件可知所有的物品由若干主件和依賴于每個主件的一個附件集合組成。按照背包問題的一般思路，僅考慮一個主件和它的附件集合。可是，可用的策略非常多，包括：一個也不選，僅選擇主件，選擇主件后再選擇一個附件，選擇主件后再選擇兩個附件……無法用狀態(tài)轉(zhuǎn)移方程來表示如此多的策略。（事實上，設(shè)有n個附件，則策略有2^n+1個，為指數(shù)級。）考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所以一個主件和它的附件集合實際上對應(yīng)于P06中的一個物品組，每個選擇了主件又選擇了若干個附件的策略對應(yīng)于這個物品組中的一個物品，其費用和價值都是這個策略中的物品的值的和。但僅僅是這一步轉(zhuǎn)化并不能給出一個好的算法，因為物品組中的物品還是像原問題的策略一樣多。再考慮P06中的一句話：可以對每組中的物品應(yīng)用P02中“一個簡單有效的優(yōu)化”。這提示我們，對于一個物品組中的物品，所有費用相同的物品只留一個價值最大的，不影響結(jié)果。所以，我們可以對主件i的“附件集合”先進行一次01背包，得到費用依次為0..V-c所有這些值時相應(yīng)的最大價值f'[0..V-c]。那么這個主件及它的附件集合相當于V-c+1個物品的物品組，其中費用為c+k的物品的價值為f'[k]+w。也就是說原來指數(shù)級的策略中有很多策略都是冗余的，通過一次01背包后，將主件i轉(zhuǎn)化為V-c+1個物品的物品組，就可以直接應(yīng)用P06的算法解決問題了。更一般的問題是：依賴關(guān)系以圖論中“森林”的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制只是每個物品最多只依賴于一個物品（只有一個主件）且不出現(xiàn)循環(huán)依賴。7.1.課前我主要是準備了些例子，對于一些經(jīng)典的算法，比如貪婪法，枚舉法，遞歸法，對于貪婪法：貪婪法一般可以快速得到滿意的解，因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。對于枚舉法：枚舉法是利用計算機運算速度快、精確度高的特點，對要解決問題的所有可能情況，一個不漏地進行檢驗，從中找出符合要求的答案，因此枚舉法是通過犧牲時間來換取答案的全面性。在數(shù)學(xué)和計算機科學(xué)理論中，一個集的枚舉是列出某些有窮序列集的所有成員的程序，或者是一種特定類型對象的計數(shù)。這兩種類型經(jīng)常（但不總是）重疊。對于遞歸法：遞歸算法是一種直接或者間接地調(diào)用自身算法的過程。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。遞歸算法解決問題的特點：(1)遞歸就是在過程或函數(shù)里調(diào)用自身。(2)在使用遞歸策略時，必須有一個明確的遞歸結(jié)束條件，稱為遞歸出口。(3)遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設(shè)計程序。(4)在遞歸調(diào)用的過程當中系統(tǒng)為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數(shù)過多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計程序。7.1.組合數(shù)學(xué)6-8頁，算法設(shè)計與分析3-4頁，嚴蔚敏.數(shù)據(jù)機構(gòu)第一章7.2教學(xué)單元二7.2.1教學(xué)日期第二周周一、周二、周四7.2.讓學(xué)生進一步掌握以下內(nèi)容：（1）NP完全理論（2）NP問題的求解方法概述初步掌握（1）什么是蠻力法及蠻力法的設(shè)計思路（2）蠻力法計算步驟7.2.有些計算問題是確定性的，比如加減乘除之類，你只要按照公式推導(dǎo)，按部就班一步步來，就可以得到結(jié)果。但是，有些問題是無法按部就班直接地計算出來。比如，找大質(zhì)數(shù)的問題。有沒有公式，你一套公式，就可以一步步推算出來，下一個質(zhì)數(shù)應(yīng)該是多少呢？這樣的公式是沒有的。再比如，大的合數(shù)分解質(zhì)因數(shù)的問題，有沒有一個公式，把合數(shù)代進去，就直接可以算出，它的因子各自是多少？也沒有這樣的公式。這種問題的答案，是無法直接計算得到的，只能通過間接的“猜算”來得到結(jié)果。這就是非確定性問題。而這些問題的通常有個算法，它不能直接告訴你答案是什么，但可以告訴你，某個可能的結(jié)果是正確的答案還是錯誤的。這個可以告訴你“猜算”的答案正確與否的算法，假如可以在多項式時間內(nèi)算出來，就叫做多項式非確定性問題。而如果這個問題的所有可能答案，都是可以在多項式時間內(nèi)進行正確與否的驗算的話，就叫完全多項式非確定問題。完全多項式非確定性問題可以用窮舉法得到答案，一個個檢驗下去，最終便能得到結(jié)果。但是這樣算法的復(fù)雜程度，是指數(shù)關(guān)系，因此計算的時間隨問題的復(fù)雜程度成指數(shù)的增長，很快便變得不可計算了。人們發(fā)現(xiàn)，所有的完全多項式非確定性問題，都可以轉(zhuǎn)換為一類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案，都可以在多項式時間內(nèi)計算，人們于是就猜想，是否這類問題存在一個確定性算法，可以在多項式時間內(nèi)直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。解決這個猜想，無非兩種可能，一種是找到一個這樣的算法，只要針對某個特定NP完全問題找到一個算法，所有這類問題都可以迎刃而解了，因為他們可以轉(zhuǎn)化為同一個問題。另外的一種可能，就是這樣的算法是不存在的。那么就要從數(shù)學(xué)理論上證明它為什么不存在。最常被引用的結(jié)果之一設(shè)計神喻。假想你有一個魔法機器可以解決單個問題，例如決定一個給定的數(shù)字是否為質(zhì)數(shù)，但可以瞬間解決這個問題。我們的新問題是，若我們被允許任意利用這個機器，是否存在我們可以在多項式時間內(nèi)驗證但無法在多項式時間內(nèi)解決的問題？結(jié)果是，依賴于機器能解決的問題，P=NP和P≠NP二者都可以證明。這個結(jié)論的后果是，任何可以修改來證明該機器的存在性的結(jié)果不能解決問題。不幸的是，幾乎所有經(jīng)典的方法和大部分已知的方法可以這樣修改（我們稱它們在相對化）。如果這還不算太糟的話，1993年Razborov和Rudich證明的一個結(jié)果表明，給定一個特定的可信的假設(shè)，在某種意義下“自然”的證明不能解決P=NP問題。這表明一些現(xiàn)在似乎最有希望的方法不太可能成功。隨著更多這類的定理得到證明，該定理的可能證明有越來越多的陷阱要規(guī)避。這實際上也是為什么NP完全問題有用的原因：若有一個多項式時間算法，或者沒有一個這樣的算法，對于NP完全問題存在，這將用一種相信不被上述結(jié)果排除在外的方法來解決P=NP問題。P=NP問題可以用邏輯命題的特定類的可表達性的術(shù)語來重新表述。所有P中的語言可以用一階邏輯加上最小不動點操作（實際上，這允許了遞歸函數(shù)的定義）來表達。類似地，NP是可以用存在性二階邏輯來表達—也就是，在關(guān)系、函數(shù)、和子集上排除了全域量詞的二階邏輯。多項式等級，PH中的語言對應(yīng)與所有的二階邏輯。這樣，“P是NP的真子集嗎”這樣的問題可以表述為“是否存在性二階邏輯能夠表達帶最小不動點操作的一階邏輯的所不能表達的語言？”普林斯頓大學(xué)計算機系樓將二進制代碼表述的“P=NP?”問題刻進頂樓西面的磚頭上。如果證明了P=NP，磚頭可以很方便的換成表示“P=NP！”?？的螤柎髮W(xué)的HubertChen博士提供了這個玩笑式的P不等于NP的證明：“反證法。設(shè)P=NP。令y為一個P=NP的證明。證明y可以用一個合格的計算機科學(xué)家在多項式時間內(nèi)驗證，我們認定這樣的科學(xué)家的存在性為真。但是，因為P=NP，該證明y可以在多項式時間內(nèi)由這樣的科學(xué)家發(fā)現(xiàn)。但是這樣的發(fā)現(xiàn)還沒有發(fā)生（雖然這樣的科學(xué)家試圖發(fā)現(xiàn)這樣的一個證明），我們得到矛盾。常用搜索方法（1）近鄰法近鄰法（nearestneighbor)推銷員從某個城鎮(zhèn)出發(fā)，永遠選擇前往最近且尚未去過的城鎮(zhèn)，最后再返回原先的出發(fā)點。這方法簡單，也許是多數(shù)人的直覺做法，但是近鄰法的短視使其表現(xiàn)非常不好，通常后段的路程會非常痛苦。（2）插入法插入法（insertion)先產(chǎn)生連接部分點的子路線，再根據(jù)某種法則將其它的點逐一加入路線。比如最近插入法（nearestinsertion），先針對外圍的點建構(gòu)子路線，然后從剩余的點里面評估何者加入后路線總長度增加的幅度最小，再將這個點加入路線。又比如最遠插入法（farthest，insertion），是從剩余的點里面選擇距離子路線最遠的點，有點先苦后甜的滋味。（3）模擬退火算法模擬退火算法（RecuitAlgorithm)來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準則，粒子在溫度T時趨于平衡的概率為e-ΔE/(kT），其中E為溫度T時的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當前解重復(fù)“產(chǎn)生新解→計算目標函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解。（4）遺傳算法遺傳算法是仿真生物遺傳學(xué)和自然選擇機理，通過人工方式所構(gòu)造的一類搜索算法，從某種程度上說遺傳算法是對生物進化過程進行的數(shù)學(xué)方式仿真。生物種群的生存過程普遍遵循達爾文進化準則，群體中的個體根據(jù)對環(huán)境的適應(yīng)能力而被大自然所選擇或淘汰。進化過程的結(jié)果反映在個體的結(jié)構(gòu)上，其染色體包含若干基因，相應(yīng)的表現(xiàn)型和基因型的聯(lián)系體現(xiàn)了個體的外部特性與內(nèi)部機理間邏輯關(guān)系。通過個體之間的交叉、變異來適應(yīng)大自然環(huán)境。生物染色體用數(shù)學(xué)方式或計算機方式來體現(xiàn)就是一串數(shù)碼，仍叫染色體，有時也叫個體；適應(yīng)能力是對應(yīng)著一個染色體的一個數(shù)值來衡量；染色體的選擇或淘汰則按所面對的問題是求最大還是最小來進行。（5）神經(jīng)網(wǎng)絡(luò)算法根據(jù)一個簡化的統(tǒng)計，人腦由百億條神經(jīng)組成—每條神經(jīng)平均連結(jié)到其它幾千條神經(jīng)。通過這種連結(jié)方式，神經(jīng)可以收發(fā)不同數(shù)量的能量。神經(jīng)的一個非常重要的功能是它們對能量的接受并不是立即作出響應(yīng)，而是將它們累加起來，當這個累加的總和達到某個臨界閾值時，它們將它們自己的那部分能量發(fā)送給其它的神經(jīng)。大腦通過調(diào)節(jié)這些連結(jié)的數(shù)目和強度進行學(xué)習(xí)。盡管這是個生物行為的簡化描述。但同樣可以充分有力地被看作是神經(jīng)網(wǎng)絡(luò)的模型。（6）蠻力法蠻力法就是一種解決問題的最簡單最直觀的最容易理解方法，雖然它簡單，而且在實際應(yīng)用中因為效率的原因可能不能派上用場，但是還是不能忽略它。在解決小規(guī)模問題的時候也不失為一個方法，而且也是更復(fù)雜算法的基礎(chǔ)。1.蠻力法的基本思想蠻力法是一種簡單直接地解決問題的方法.2．選擇排序問題描述及算法講解演示；歸納算法時間效率關(guān)系式；推導(dǎo)并求解除選擇排序的時間效率為Θ(n2)。3．冒泡排序冒泡排序算法講解演示；歸納算法時間效率關(guān)系式；推導(dǎo)并求解除選擇排序的時間效率為Θ(n2)4．順序查找和蠻力字符串匹配查找和字符串匹配問題描述及算法講解演示；歸納算法時間效率關(guān)系式。5．最近對問題最近對問題的描述及模型；最近對問題的蠻力算法及時間效率分析。6．凸包問題凸包的定義及舉例及問題的描述；凸包問題的蠻力解決方法及時間效率分析。7．窮舉查找旅行商問題、背包問題、分配問題。7.2.本課程是信息與計算科學(xué)專業(yè)的重要專業(yè)方向理論課，是軟件開發(fā)賴以生存的重要基礎(chǔ)。在教學(xué)方法上，采用課堂講授，課后自學(xué)，課堂討論等教學(xué)形式。本課程屬于專業(yè)方向理論課程。在傳授知識原理的前提下，配合實際應(yīng)用例子，由淺入深善于誘導(dǎo)，使學(xué)生從被動吸收知識的狀態(tài)下，轉(zhuǎn)化到主動索取知識的狀態(tài)中來，并采用多媒體輔助教學(xué)，加大課堂授課的知識含量。注重培養(yǎng)學(xué)生的學(xué)習(xí)興趣，提高學(xué)生的基本素質(zhì)。7.2.為了培養(yǎng)學(xué)生整理歸納，綜合分析和處理問題的能力，每章都安排一部分內(nèi)容，課上教師只給出自學(xué)提綱，不作詳細講解，課后學(xué)生自學(xué)。課堂討論的目的是活躍學(xué)習(xí)氣氛，開拓思路。教師應(yīng)認真組織，安排重點發(fā)言，充分調(diào)動每一名同學(xué)的學(xué)習(xí)積極性，做好總結(jié)。課外作業(yè)為了讓學(xué)生鞏固所學(xué)的知識，每章都布置一定數(shù)量課外作業(yè)。這樣，就可以達到教與學(xué)真正的溝通。7.2.6作業(yè)安排及課后反思算法設(shè)計后面相應(yīng)的習(xí)題，嘗試應(yīng)用蠻力法解決找旅行商問題、背包問題、分配問題。通過這個單元的教學(xué)，我試著教學(xué)生如何運用蠻力法解決找旅行商問題，背包問題。通過對相關(guān)理論知識的講解和典型習(xí)題的講解，引導(dǎo)學(xué)生自己解決此類問題。雖然一開始接受起來有些吃力，教學(xué)內(nèi)容不能夠按要求完成，但通過幾節(jié)課的耐心講解，學(xué)生開始學(xué)會自己獨立的思考，通過課堂討論，課后練習(xí)的綜合練習(xí)，學(xué)生有了很大的提高。通過這幾次的上課，我了解到光是自己講理論是不行的，必須和學(xué)生互動起來，教他們?nèi)绾巫约邯毩⒌乃伎?，如何通過學(xué)過的知識來解決新的難題。知識點就那么多，在掌握了一些必要的知識點以后，如何運用起來，如何去解決不同的問題，這才是教學(xué)的內(nèi)容和目的。也只有學(xué)生真的能夠把所學(xué)的知識運用到實際中，這些知識才是有意義的，否則，掌握再多的理論那也只是理論，沒有任何的實用價值。所以一定要通過大量的練習(xí)題和實際問題來幫助同學(xué)提高這方面的能力。7.2.提前預(yù)習(xí)教材相關(guān)部分，了解相關(guān)內(nèi)容。搜集相關(guān)的練習(xí)題在課堂上講解，羅列所用到的知識點以及經(jīng)典的解題技巧。7.2算法設(shè)計與分析13-17頁，嚴蔚敏.數(shù)據(jù)機構(gòu)第二、三章7.3教學(xué)單元三7.3.1教學(xué)日期第三周周一、周二、周四7.3.2教學(xué)目標讓學(xué)生進一步掌握以下內(nèi)容：（1）查找問題中的蠻力法（2）排序問題中的蠻力法（3）排序問題中的蠻力法計算步驟7.3.3教學(xué)內(nèi)容（含重點、難點）（1）蠻力法的設(shè)計思想：直接基于問題的描述（2）蠻力法所依賴的基本技術(shù)——掃描技術(shù)（3）關(guān)鍵——依次處理所有元素（4）基本的掃描技術(shù)——遍歷集合的遍歷線性表的遍歷樹的遍歷圖的遍歷雖然巧妙和高效的算法很少來自于蠻力法，基于以下原因，蠻力法也是一種重要的算法設(shè)計技術(shù)：（1）理論上，蠻力法可以解決可計算領(lǐng)域的各種問題。（2）蠻力法經(jīng)常用來解決一些較小規(guī)模的問題。（3）對于一些重要的問題蠻力法可以產(chǎn)生一些合理的算法，他們具備一些實用價值，而且不受問題規(guī)模的限制。（4）蠻力法可以作為某類問題時間性能的底線，來衡量同樣的更高效的算法。集合的遍歷：viewplaincopyprint?importjava.util.ArrayList;importjava.util.Iterator;importjava.util.List;publicclassTest{publicstaticvoidmain(String[]args){Listlist=newArrayList();list.add(3);list.add(2);list.add(10);list.add(4);list.add(70);/*System.out.println("---方法一-----");for(Iteratoriterator=list.iterator();iterator.hasNext();){inti=(Integer)iterator.next();System.out.println(i);}/*System.out.println("---方法二-----");Iteratoriterator=list.iterator();while(iterator.hasNext()){inti=(Integer)iterator.next();System.out.println(i);}System.out.println("---方法三-----");for(Objectobject:list){System.out.println(object);}*/System.out.println("---方法四-----");for(inti=0;i<list.size();i++){intj=(Integer)list.get(i);System.out.println(j);}}}給定一個輸入序列，建立順序表，訪問輸出順序表中各結(jié)點的內(nèi)容。給定一個輸入序列，建立線性鏈表，訪問輸出線性鏈表中各結(jié)點的內(nèi)容。線性結(jié)構(gòu)中的所有結(jié)點按它們之間的關(guān)系可以排成一個線性序列：k1，k2，?，kn其中k1是開始結(jié)點，kn是終端結(jié)點，ki是ki+1的前驅(qū)結(jié)點，而ki+1是ki的后繼結(jié)點(i=1，2，?，n-1)。通常把上述線性序列稱為“線性表”，把線性結(jié)構(gòu)中的結(jié)點稱為元素或“表目”。將一個線性表存放到計算機中，可以采用不同的方法，其中最簡單而自然的就是順序的方法，即把表目按其索引值從小到大一個接一個地存放在相鄰的單元里。順序方法存儲的線性表簡稱“順序表”，順序表是一種緊湊結(jié)構(gòu)。常用的鏈表有單鏈表和雙鏈表。在單鏈表中分配給每個結(jié)點的存儲單元可分為兩個部分：一部分存放結(jié)點的數(shù)據(jù)，稱為data域，另一部分存放指向結(jié)點后續(xù)結(jié)點的指針，稱為next域，終端結(jié)點沒有后繼結(jié)點，其next域為NULL，在計算機中可以表示成零或負數(shù)，另外還需要一個表頭變量head指向鏈表的第一個結(jié)點。其中k1是開始結(jié)點，kn是終端結(jié)點，ki是ki+1的前驅(qū)結(jié)點，而ki+1是ki的后繼結(jié)點(i=1，2，?，n-1)。通常把上述線性序列稱為“線性表”，把線性結(jié)構(gòu)中的結(jié)點稱為元素或“表目”。將一個線性表存放到計算機中，可以采用不同的方法，其中最簡單而自然的就是順序的方法，即把表目按其索引值從小到大一個接一個地存放在相鄰的單元里。順序方法存儲的線性表簡稱“順序表”，順序表是一種緊湊結(jié)構(gòu)。常用的鏈表有單鏈表和雙鏈表。在單鏈表中分配給每個結(jié)點的存儲單元可分為兩個部分：一部分存放結(jié)點的數(shù)據(jù)，稱為data域，另一部分存放指向結(jié)點后續(xù)結(jié)點的指針，稱為next域，終端結(jié)點沒有后繼結(jié)點，其next域為NULL，在計算機中可以表示成零或負數(shù)，另外還需要一個表頭變量head指向鏈表的第一個結(jié)點。7.3.4教學(xué)過程算法的實現(xiàn)：viewplaincopyprint?importjava.util.ArrayList;importjava.util.Iterator;importjava.util.List;publicclassTest{publicstaticvoidmain(String[]args){Listlist=newArrayList();list.add(3);list.add(2);list.add(10);list.add(4);list.add(70);線性結(jié)構(gòu)中的所有結(jié)點按它們之間的關(guān)系可以排成一個線性序列：k1，k2，?，kn其中k1是開始結(jié)點，kn是終端結(jié)點，ki是ki+1的前驅(qū)結(jié)點，而ki+1是ki的后繼結(jié)點(i=1，2，?，n-1)。通常把上述線性序列稱為“線性表”，把線性結(jié)構(gòu)中的結(jié)點稱為元素或“表目”。為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死那些實際上不可能產(chǎn)生所需解的活結(jié)點，以減少問題的計算量。這種具有限界函數(shù)的深度優(yōu)先生成法稱回溯法。對于有n種可選物品的0/1背包問題，其解空長度為n的0-1向量組成,可用子集數(shù)表示。在搜索解空間樹時，只要其左兒子結(jié)點是一個可行結(jié)點，搜索就進入左子樹。當右子樹中有可能包含最優(yōu)解時就進入右子樹搜索。分支限界法類似于回溯法，也是在問題的解空間上搜索問題解的算法。一般情況下，分支限界法與回溯法的求解目標不同。回溯法的求解目標是找出解空間中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標函數(shù)值達到極大或極小的解，即在某種意義下的最優(yōu)解。首先，要對輸入數(shù)據(jù)進行預(yù)處理，將各物品依其單位重量價值從大到小進行排列。在下面描述的優(yōu)先隊列分支限界法中，節(jié)點的優(yōu)先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。算法首先檢查當前擴展結(jié)點的左兒子結(jié)點的可行性。如果該左兒子結(jié)點是可行結(jié)點，則將它加入到子集樹和活結(jié)點優(yōu)先隊列中。當前擴展結(jié)點的右兒子結(jié)點一定是可行結(jié)點，僅當右兒子結(jié)點滿足上界約束時才將它加入子集樹和活結(jié)點優(yōu)先隊列。當擴展到葉節(jié)點時為問題的最優(yōu)值。算法的實現(xiàn)：intp;//物體價值};structHEAP//堆元素結(jié)構(gòu)體{KNAPNODE*p;//結(jié)點數(shù)據(jù)intb;//所指結(jié)點的上界};//交換兩個堆元素voidswap(HEAP&a,HEAP&b){HEAPtemp=a;a=b;b=temp;}//堆中元素上移voidmov_up(HEAPH[],inti){booldone=false;if(i!=1){while(!done&&i!=1){if(H[i].b>H[i/2].b){swap(H[i],H[i/2]);}else{done=true;}i=i/2;}}}//堆中元素下移voidmov_down(HEAPH[],intn,inti){booldone=false;if((2*i)<=n){while(!done&&((i=2*i)<=n)){if(i+1<=n&&H[i+1].b>H[i].b){i++;}if(H[i/2].b<H[i].b){swap(H[i/2],H[i]);}else{done=true;}}}}//往堆中插入結(jié)點voidinsert(HEAPH[],HEAPx,int&n){n++;H[n]=x;mov_up(H,n);}//刪除堆中結(jié)點voiddel(HEAPH[],int&n,inti){HEAPx,y;x=H[i];y=H[n];n--;if(i<=n){H[i]=yif(y.b>=x.){mov_up(H,i);}else{mov_down(H,n,i);}}}//獲得堆頂元素并刪除HEAPdel_top(HEAPH[],int&n){HEAPx=H[1];del(H,n,1);returnx;}//計算分支節(jié)點的上界voidbound(KNAPNODE*node,intM,goodsa[],intn){inti=node->k;floatw=node->w;floatp=node->p;if(node->w>M){//物體重量超過背包載重量node->b=0;//上界置為0}else{while((w+a[i].w<=M)&&(i<n)){w+=a[i].w;//計算背包已裝入載重p+=a[i++].p;//計算背包已裝入價值}if(i<n){node->b=p+(M-w)*a[i].p/a[i].w;}else{node->b=p;}}}//用分支限界法實現(xiàn)0/1背包問題intKnapSack4(intn,goodsa[],intC,intX[]){inti,k=0;//堆中元素個數(shù)的計數(shù)器初始化為0intv;KNAPNODE*xnode,*ynode,*znode;HEAPx,y,z,*heap;heap=newHEAP[n*n];//分配堆的存儲空間for(i=0;i<n;i++){a[i].sign=i;//記錄物體的初始編號}sort(a,a+n,m);//對物體按照價值重量比排序xnode=newKNAPNODE;//建立父親結(jié)點for(i=0;i<n;i++){//初始化結(jié)點xnode->s1[i]=false;}xnode->k=xnode->w=xnode->p=0;while(xnode->k<n){ynode=newKNAPNODE;//建立結(jié)點y*ynode=*xnode;//結(jié)點x的數(shù)據(jù)復(fù)制到結(jié)點yynode->s1[ynode->k]=true;//裝入第k個物體ynode->w+=a[ynode->k].w;//背包中物體重量累計ynode->p+=a[ynode->k].p;//背包中物體價值累計ynode->k++;//搜索深度++bound(ynode,C,a,n);//計算結(jié)點y的上界y.b=ynode->b;y.p=ynode;insert(heap,y,k);//結(jié)點y按上界的值插入堆中znode=newKNAPNODE;//建立結(jié)點z*znode=*xnode;//結(jié)點x的數(shù)據(jù)復(fù)制到結(jié)點zznode->k++;