AI賦能Java語言編程：從入門到高階 課件 第十四章 算法競賽中的Java編程

算法競賽中的Java編程JavaProgrammingInAlgorithmCompetitions第十四章目錄010203算法競賽基礎(chǔ)算法基礎(chǔ)算法設(shè)計(jì)方法01算法競賽簡介14.1算法競賽簡介算法競賽的歷史可以追溯到計(jì)算機(jī)科學(xué)的早期。隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，算法競賽也逐漸演變成了一項(xiàng)具有全球影響力的活動(dòng)。在算法競賽中，參賽者需要在規(guī)定的時(shí)間內(nèi)解決一系列復(fù)雜的問題。這些問題往往涉及到數(shù)據(jù)結(jié)構(gòu)、圖論、動(dòng)態(tài)規(guī)劃、數(shù)學(xué)等多個(gè)領(lǐng)域的知識。ACM國際大學(xué)生程序設(shè)計(jì)競賽（簡稱ACM/ICPC）無疑是最具影響力和挑戰(zhàn)性的賽事之一。ACM/ICPC是由美國計(jì)算機(jī)協(xié)會(huì)（ACM）主辦的年度競賽，起源于1970年。14.1算法競賽簡介在中國同樣有許多知名的算法設(shè)計(jì)競賽，其中最著名的是“藍(lán)橋杯全國軟件和信息技術(shù)專業(yè)人才大賽”，簡稱“藍(lán)橋杯”。藍(lán)橋杯競賽分為初賽和決賽兩個(gè)階段,比賽內(nèi)容涵蓋計(jì)算機(jī)基礎(chǔ)知識、算法設(shè)計(jì)、程序設(shè)計(jì)等方面。*算法競賽的核心是算法設(shè)計(jì)和優(yōu)化。02算法基礎(chǔ)函數(shù)的參算法是解決問題或執(zhí)行任務(wù)的一系列有序步驟。這些步驟明確定義，并且對于給定的輸入，算法能夠產(chǎn)生確定性的輸出。在Java編程語言中，我們可以通過不同的編程技術(shù)來實(shí)現(xiàn)算法，例如循環(huán)、遞歸、分治等。算法的關(guān)鍵特征包括明確定義的步驟、輸入與輸出的概念、有窮性，即在有限步驟內(nèi)終止，以及確定性，確保給定相同的輸入將始終產(chǎn)生相同的輸出。此外，算法必須是可行的，即在實(shí)際環(huán)境中可執(zhí)行，而且效率是一個(gè)重要的考慮因素，好的算法能夠在合理的時(shí)間內(nèi)解決問題，并在處理大規(guī)模數(shù)據(jù)時(shí)保持有效。14.2算法基礎(chǔ)14.2.1算法基本概念函數(shù)的參算法分析是一門關(guān)鍵的學(xué)科，它涉及到對算法在不同輸入條件下的行為進(jìn)行評估，并確定其效率和可估計(jì)性。通過算法分析可以了解程序的性能和質(zhì)量。在算法競賽中很多題目都對程序的運(yùn)行時(shí)間和內(nèi)存提出了要求。概念1——時(shí)間復(fù)雜度時(shí)間復(fù)雜度(TimeComplexity)是衡量算法運(yùn)行時(shí)間隨輸入規(guī)模增長而變化的度量，是一個(gè)代表算法輸入值的字符串的長度的函數(shù)。時(shí)間復(fù)雜度常用大O符號表述。常見的時(shí)間復(fù)雜度包括常數(shù)時(shí)間O(1)、線性時(shí)間O(n)、對數(shù)時(shí)間O(logn)等。14.2算法基礎(chǔ)14.2.2算法分析函數(shù)的參通過分析算法的執(zhí)行步驟數(shù)，我們可以估計(jì)算法的時(shí)間復(fù)雜度。在最壞情況下，即目標(biāo)元素在數(shù)組的最后一個(gè)位置或不存在于數(shù)組中時(shí)，算法需要遍歷整個(gè)數(shù)組。在這種情況下，時(shí)間復(fù)雜度是線性的，用大O符號表示為O(n)，其中n是數(shù)組的長度。14.2算法基礎(chǔ)publicstaticbooleansearchElement(int[]array,inttarget){for(intelement:array){if(element==target){returntrue;//找到目標(biāo)元素，返回true}}returnfalse;//未找到目標(biāo)元素，返回false}函數(shù)的參概念2——空間復(fù)雜度空間復(fù)雜度(SpaceComplexity)是算法在執(zhí)行過程中所需內(nèi)存空間的度量，表示一個(gè)算法完全執(zhí)行所需要的存儲(chǔ)空間大小。常見的空間復(fù)雜度包括常數(shù)空間O(1)、線性空間O(n)等。空間復(fù)雜度簡單的說就是使用了多少內(nèi)存，可以通過數(shù)組、字符串和其他數(shù)據(jù)結(jié)構(gòu)的大小和數(shù)量來代指。14.2算法基礎(chǔ)最壞情況復(fù)雜度表示算法在所有可能輸入中運(yùn)行時(shí)間的上界，即在最壞的輸入情況下算法的性能。在實(shí)際情況中，最壞情況復(fù)雜度更常用，因?yàn)樗峁┝藢λ惴ㄐ阅艿囊环N較為保守和簡化的估計(jì)。而平均情況復(fù)雜度表示算法在所有可能輸入中運(yùn)行時(shí)間的期望值，考慮輸入的概率分布。其在表示上用大Θ符號。平均復(fù)雜度更能反映算法在實(shí)際使用中的性能，通常較難準(zhǔn)確計(jì)算。14.2算法基礎(chǔ)函數(shù)的參14.2.3高級排序算法高級排序算法通常指那些在大多數(shù)情況下能夠在較短時(shí)間內(nèi)完成排序任務(wù)的算法。這些算法相對于基礎(chǔ)的排序算法通常有更好的平均和最壞情況復(fù)雜度?？焖倥判蚝拖柵判蚓褪莾煞N常用的高級排序算法。（一）快速排序快速排序(QuickSort)通過選擇一個(gè)基準(zhǔn)元素，將數(shù)組劃分為小于基準(zhǔn)的部分和大于基準(zhǔn)的部分，然后遞歸地對這兩部分進(jìn)行排序。14.2算法基礎(chǔ)函數(shù)的參其基本步驟如下：（1）選擇基準(zhǔn)元素：從數(shù)組中選擇一個(gè)元素作為基準(zhǔn)（pivot）。通?？梢赃x擇第一個(gè)、最后一個(gè)或中間元素。（2）劃分：將數(shù)組中小于基準(zhǔn)的元素移到基準(zhǔn)的左邊，大于基準(zhǔn)的元素移到基準(zhǔn)的右邊。這個(gè)過程稱為劃分。（3）遞歸：對劃分得到的左右子數(shù)組分別進(jìn)行遞歸快速排序。（4）合并：不需要顯式的合并步驟，因?yàn)閯澐诌^程已經(jīng)將數(shù)組排列成有序。14.2算法基礎(chǔ)函數(shù)的參publicstaticvoidquickSort(int[]arr,intlow,inthigh){if(low<high){ intpivotIndex=partition(arr,low,high);

quickSort(arr,low,pivotIndex-1);quickSort(arr,pivotIndex+1,high);}}publicstaticintpartition(int[]arr,intlow,inthigh){intpivot=arr[high];inti=low-1;for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(arr,i,j);}}swap(arr,i+1,high);returni+1;}14.2算法基礎(chǔ)函數(shù)的參（二）希爾排序希爾排序（ShellSort）是一種基于插入排序的改進(jìn)算法，它通過引入“增量”的概念來提高插入排序在處理大數(shù)據(jù)集時(shí)的效率?；舅枷胧菍⒋判虻臄?shù)組分成多個(gè)子數(shù)組（也稱為增量序列），對每個(gè)子數(shù)組進(jìn)行插入排序，然后逐步縮小增量，直到增量為1時(shí)，整個(gè)數(shù)組被當(dāng)作一個(gè)表來處理，算法終止。希爾排序的關(guān)鍵在于確定增量序列。常用的增量序列是Shell提出的序列（n/2k，其中n是數(shù)組長度，k是增量序列的索引），但也可以根據(jù)需要選擇其他序列。14.2算法基礎(chǔ)函數(shù)的參希爾排序的基本步驟如下：（1）選擇一個(gè)增量序列，通常是一系列遞減的正整數(shù)。（2）按增量進(jìn)行插入排序：對每個(gè)增量，將數(shù)組劃分成若干個(gè)子序列（每個(gè)子序列的元素在原始數(shù)組中間距相同）。對每個(gè)子序列進(jìn)行插入排序。（3）逐步縮小增量：重復(fù)步驟2，逐漸縮小增量，直至增量為1。希爾排序的時(shí)間復(fù)雜度取決于增量序列的選擇，沒有精確公式。在平均情況下，希爾排序的時(shí)間復(fù)雜度約為O(nlog^2n)到O(n^2)之間。14.2算法基礎(chǔ)函數(shù)的參publicstaticvoidshellSort(int[]arr){intn=arr.length;intgap=n/2;//初始增量

while(gap>0){for(inti=gap;i<n;i++){inttemp=arr[i];intj=i;//插入排序while(j>=gap&&arr[j-gap]>temp){arr[j]=arr[j-gap];j-=gap;}arr[j]=temp;}gap/=2;//縮小增量}}14.2算法基礎(chǔ)函數(shù)的參其基本步驟如下：（1）選擇基準(zhǔn)元素：從數(shù)組中選擇一個(gè)元素作為基準(zhǔn)（pivot）。通常可以選擇第一個(gè)、最后一個(gè)或中間元素。（2）劃分：將數(shù)組中小于基準(zhǔn)的元素移到基準(zhǔn)的左邊，大于基準(zhǔn)的元素移到基準(zhǔn)的右邊。這個(gè)過程稱為劃分。（3）遞歸：對劃分得到的左右子數(shù)組分別進(jìn)行遞歸快速排序。（4）合并：不需要顯式的合并步驟，因?yàn)閯澐诌^程已經(jīng)將數(shù)組排列成有序。14.2算法基礎(chǔ)03算法設(shè)計(jì)方法算法設(shè)計(jì)是計(jì)算機(jī)科學(xué)中的核心部分，它涉及到解決問題的一系列清晰指令。在Java編程中，算法設(shè)計(jì)方法起著至關(guān)重要的作用，因?yàn)樗梢詭椭绦騿T更有效地編寫代碼并解決復(fù)雜問題。編程競賽中絕大多數(shù)題目都需要選擇合適設(shè)計(jì)方法來得到最優(yōu)的答案。14.3.1枚舉法枚舉法是一種基礎(chǔ)的策略，通過遍歷所有可能的解決方案來找到問題的答案。這種方法又稱為暴力法或窮舉搜索，通常用于問題規(guī)模較小或者解決方案的數(shù)量有限的情況。枚舉法的核心是逐一檢查所有可能的選項(xiàng)，直到找到滿足條件的解。14.3算法設(shè)計(jì)方法枚舉法的基本步驟：（1）明確需要枚舉的變量和目標(biāo)條件（2）設(shè)計(jì)枚舉的順序和邏輯（3）實(shí)現(xiàn)算法（4）分析優(yōu)化優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，邏輯清晰；缺點(diǎn)是對于大規(guī)模問題而言，計(jì)算量巨大，效率低下，往往不適合實(shí)際應(yīng)用。7.3結(jié)構(gòu)體的初始化Copilot指令：//編寫Java程序，找出給定字符串中所有字符出現(xiàn)次數(shù)的最大公約數(shù)。//如果字符串為空或者只包含一個(gè)字符，則最大公約數(shù)應(yīng)為1。//如輸入：“abca”輸出：1解釋：字符‘a(chǎn)’出現(xiàn)2次，字符‘b’、‘c’出現(xiàn)1次，最大公約數(shù)是1。7.3結(jié)構(gòu)體的初始化例14.2

給定一個(gè)字符串，找出字符串中所有字符出現(xiàn)次數(shù)的最大公約數(shù)。如果字符串為空或者只包含一個(gè)字符，則最大公約數(shù)應(yīng)為1。如“abca”中字符‘a(chǎn)’出現(xiàn)兩次，字符‘b’、‘c’出現(xiàn)一次，最大公約數(shù)為1。publicclassCharacterGCD{publicstaticintfindGCDOfCharacters(Stringstr){if(str==null||str.isEmpty()){return1;}

int[]charCount=newint[26];//統(tǒng)計(jì)每個(gè)字符的出現(xiàn)次數(shù)for(charc:str.toCharArray()){charCount[c-'a']++;}//枚舉所有可能的公約數(shù)for(inti=26;i>1;i--){if(isValidGCD(charCount,i)){returni;}}return1;}7.3結(jié)構(gòu)體的初始化privatestaticbooleanisValidGCD(int[]charCount,intgcd){for(intcount:charCount){if(count%gcd!=0){returnfalse;}}returntrue;}publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);Stringinput=scanner.nextLine();System.out.println("字符串中的字符的最大公約數(shù)為:"+findGCDOfCharacters(input));}}該程序包含兩個(gè)主要部分：findGCDOfCharacters方法和isValidGCD方法。前者接收一個(gè)字符串并返回字符串中所有字符出現(xiàn)次數(shù)的最大公約數(shù)。如果輸入字符串為空或只有一個(gè)字符，最大公約數(shù)顯然是1，因此方法首先檢查這種情況。isValidGCD方法則接受一個(gè)整數(shù)數(shù)組charCount和一個(gè)整數(shù)gcd作為輸入，并返回一個(gè)布爾值，指示gcd是否為charCount中所有整數(shù)的公約數(shù)。它遍歷charCount數(shù)組并檢查每個(gè)元素的值是否能被gcd整除。7.3結(jié)構(gòu)體的初始化14.3.2貪心法貪心法是一種在每一步都采取當(dāng)前看起來最優(yōu)的選擇，從而希望能導(dǎo)致全局最優(yōu)解的算法策略。其設(shè)計(jì)思想是：對于一個(gè)復(fù)雜問題，如果它能夠被分解成若干個(gè)局部問題，而且這些局部問題都容易找到最優(yōu)解，那么全局問題的最優(yōu)解就可能來自于這些局部最優(yōu)解的組合。這種方法的特點(diǎn)是簡單、直觀，并且往往能快速給出問題的解。7.3結(jié)構(gòu)體的初始化具有“貪心選擇性質(zhì)”和“最優(yōu)子結(jié)構(gòu)”的問題才適合使用貪心法?！柏澬倪x擇性質(zhì)”指的是，對于問題的任意一個(gè)局部最優(yōu)解，都能產(chǎn)生全局最優(yōu)解。而“最優(yōu)子結(jié)構(gòu)”指的是問題的最優(yōu)解包含其子問題的最優(yōu)解。貪心法在計(jì)算機(jī)科學(xué)中有著廣泛的應(yīng)用，例如在網(wǎng)絡(luò)流、背包問題、動(dòng)態(tài)規(guī)劃等領(lǐng)域。其基本步驟為：（1）確定問題的最優(yōu)解的特征；（2）設(shè)計(jì)一個(gè)遞歸或迭代的過程，每一步都采取在當(dāng)前狀態(tài)下最好或最優(yōu)的選擇；（3）逐步擴(kuò)展這個(gè)過程，直到得到全局最優(yōu)解。7.3結(jié)構(gòu)體的初始化例14.3商店里收銀員正在給一位顧客結(jié)賬。顧客共花費(fèi)了37元，但沒有零錢而給了100元?，F(xiàn)有幾種不同金額的鈔票：50元、20元、10元、5元、1元，每種鈔票金額均符合要求，并且可以無限使用。問收銀員最少給多少張鈔票來找零。7.3結(jié)構(gòu)體的初始化Copilot指令：//設(shè)計(jì)Java程序，實(shí)現(xiàn)找零問題。顧客花費(fèi)了37元但給了100元，收銀員最少給多少張鈔票來找零。//現(xiàn)有幾種不同金額的鈔票：50元、20元、10元、5元、1元，每種鈔票金額均符合要求，并且可以無限使用。publicclassMinCoinsForChange{publicstaticintminCoins(intx){//鈔票面值數(shù)組int[]denominations={50,20,10,5,1};intminCoins=0;//遍歷每個(gè)面值的鈔票for(intdenom:denominations){//使用該面值的鈔票while(x>=denom){x-=denom;minCoins++;}}returnminCoins;}

7.3結(jié)構(gòu)體的初始化publicstaticvoidmain(String[]args){intamountGiven=100;//顧客支付的金額intamountToPay=37;//顧客花費(fèi)的金額intchangeToGive=amountGiven-amountToPay;//需要找零的金額intresult=minCoins(changeToGive);System.out.println("最少需要的鈔票數(shù)量為："+result);}}運(yùn)行代碼后可以得到最少需要鈔票數(shù)量為5。minCoins方法接受一個(gè)整數(shù)x作為需要找零的金額。其中使用了一個(gè)預(yù)定義的鈔票面值數(shù)組denominations，其中包含了50元、20元、10元、5元和1元這五種面值的鈔票。方法首先初始化鈔票數(shù)量minCoins為0。然后，它遍歷denominations數(shù)組中的每個(gè)面值的鈔票。對于每個(gè)面值使用貪心算法來計(jì)算最少鈔票數(shù)量。它不斷地從x中減去該面值的鈔票金額，并增加鈔票數(shù)量，直到x小于該面值的鈔票金額。貪心算法的關(guān)鍵在于如何合理地定義“局部最優(yōu)解”和如何有效地實(shí)現(xiàn)這些局部最優(yōu)解的組合。在實(shí)際應(yīng)用中，貪心算法通常能夠給出一個(gè)近似最優(yōu)解，對于許多實(shí)際問題來說，已經(jīng)足夠有效。7.3結(jié)構(gòu)體的初始化14.3.3分治法分治法（DivideandConquer）是算法設(shè)計(jì)中的一種基本策略，它將一個(gè)難以直接解決的大問題分解成若干個(gè)規(guī)模較小的相同或相似的問題，然后遞歸地解決這些子問題，最后將子問題的解合并以解決原問題。這種方法的名字“分而治之”準(zhǔn)確地描述了其思想：將問題分而治之，直到可以簡單解決，然后將解決方案組合起來解決原問題。之前所所學(xué)的快速排序就使用了分治法，先將數(shù)據(jù)分為較小的子集，對子集進(jìn)行排序后合并得到結(jié)果。7.3結(jié)構(gòu)體的初始化分治法包括分解、遞歸求解和合并三個(gè)步驟：1.分解將原問題分解為子問題。子問題盡可能地相互獨(dú)立且與原問題的結(jié)構(gòu)相同2.遞歸求解會(huì)遞歸地應(yīng)用分治解決子問題，意味著子問題可能會(huì)繼續(xù)被分解成更小的子問題，直到它們足夠小，可以直接求解。3.合并將子問題的解合并成一個(gè)最終的解，這個(gè)解能夠解決原問題。合并操作通常是分治法中最困難的部分，因?yàn)樗枰_保合并后的結(jié)果是正確的。7.3結(jié)構(gòu)體的初始化例14.4最近點(diǎn)對問題要求在一個(gè)給定的點(diǎn)集中找到距離最近的兩個(gè)點(diǎn)。假設(shè)點(diǎn)集為points=[(2,3),(1,3),(4,5),(5,1),(1,1),(3,4)]。請求出相距最近的兩個(gè)點(diǎn)之間的距離。在本題中枚舉法是一種可行的方法，但隨著點(diǎn)的數(shù)量增多，其運(yùn)行時(shí)間將呈二次方增長，可能導(dǎo)致超時(shí)，尤其在有運(yùn)行時(shí)間限制的競賽場景中。因此這不是一個(gè)高效的解決方案。7.3結(jié)構(gòu)體的初始化Copilot指令：//設(shè)計(jì)Java程序，使用分治法解決最近點(diǎn)對問題//點(diǎn)集為points=[(2,3),(1,3),(4,5),(5,1),(1,1),(3,4)]解題思路：1.按照x坐標(biāo)將點(diǎn)集排序。2.遞歸地將點(diǎn)集分為兩半。3.分別在左右子集中遞歸尋找最近點(diǎn)對。4.合并左右子集的結(jié)果，找到橫跨兩個(gè)子集的最近點(diǎn)對。5.比較橫跨兩個(gè)子集的最近點(diǎn)對與左右子集中的最近點(diǎn)對，選擇距離更短的那一對。7.3結(jié)構(gòu)體的初始化publicclassClosestPair{//計(jì)算兩點(diǎn)之間的距離privatestaticdoubledistance(Pointa,Pointb){returnMath.sqrt(Math.pow(a.x-b.x,2)+Math.pow(a.y-b.y,2));}//分治法解決最近點(diǎn)對問題publicstaticdoubleclosestPair(Point[]points){Arrays.sort(points,(a,b)->a.x-b.x);//排序點(diǎn)集returnclosestPairRecursive(points,0,points.length-1);}

7.3結(jié)構(gòu)體的初始化//遞歸函數(shù)，實(shí)際執(zhí)行分治操作privatestaticdoubleclosestPairRecursive(Point[]points,intstart,intend){intn=end-start+1;if(n<=3){//如果點(diǎn)集大小小于等于3，直接計(jì)算doubleminDistance=Double.MAX_VALUE;for(inti=start;i<end;i++){for(intj=i+1;j<=end;j++){doubledist=distance(points[i],points[j]);if(dist<minDistance){minDistance=dist;}}}returnminDistance;}

7.3結(jié)構(gòu)體的初始化else{//否則，將點(diǎn)集分為左右兩部分，遞歸求解intmid=(start+end)/2;doubledl=closestPairRecursive(points,start,mid);doubledr=closestPairRecursive(points,mid+1,end);doubled=Math.min(dl,dr);

//在中線上查找更近的點(diǎn)對Point[]strip=newPoint[n];System.arraycopy(points,start,strip,0,n);returnfindClosestInStrip(strip,d);}}//在分割線附近找到最近點(diǎn)對privatestaticdoublefindClosestInStrip(Point[]strip,doubled){intn=strip.length;Arrays.sort(strip,(a,b)->Ipare(a.y,b.y));for(inti=0;i<n;i++){for(intj=i+1;j<n&&(strip[j].y-strip[i].y)<d;j++){doubledist=distance(strip[i],strip[j]);if(dist<d){d=dist;}}}returnd;}7.3結(jié)構(gòu)體的初始化程序首先按照輸入的點(diǎn)集的x坐標(biāo)進(jìn)行排序，然后調(diào)用closestPair方法解決問題。在closestPair中，采用分治法遞歸將問題分解為子問題，并計(jì)算左右子問題的最近點(diǎn)對距離。對于規(guī)模小于等于3的子問題，程序采用暴力法直接計(jì)算點(diǎn)對距離。在合并過程中，需要考慮分割線附近的帶狀區(qū)域內(nèi)可能存在更近點(diǎn)對的情況，通過調(diào)用findClosestInStrip方法，在該區(qū)域內(nèi)找到最近點(diǎn)對的距離。findClosestInStrip方法首先將帶狀區(qū)域內(nèi)的點(diǎn)按照y坐標(biāo)進(jìn)行排序，然后遍歷點(diǎn)集，計(jì)算相鄰點(diǎn)對之間的距離，不斷更新最小距離。

整個(gè)算法的時(shí)間復(fù)雜度為O(nlogn)，其中n為點(diǎn)集的大小。這段代碼在通過遞歸分治和考慮中間區(qū)域的方式上，有效地解決了最近點(diǎn)對問題。7.3結(jié)構(gòu)體的初始化

13.3.4動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃（DynamicProgramming）是一種解決復(fù)雜問題的優(yōu)化技術(shù)，它通過將問題分解為子問題并記憶子問題的解，從而提高算法的效率。其基本思想是將一個(gè)大問題劃分成許多小問題，通過解決小問題來解決整個(gè)大問題。

這種分治策略需要滿足最優(yōu)子結(jié)構(gòu)，即問題的最優(yōu)解可以通過子問題的最優(yōu)解來構(gòu)造。

7.3結(jié)構(gòu)體的初始化動(dòng)態(tài)規(guī)劃的關(guān)鍵在于巧妙地定義問題的狀態(tài)以及建立清晰的狀態(tài)轉(zhuǎn)移方程。狀態(tài)是問題的關(guān)鍵信息，具體描述了問題的不同方面和隨著問題規(guī)模的變化而變化的特性。良好定義的狀態(tài)對于問題的建模至關(guān)重要。通過精準(zhǔn)地定義狀態(tài)轉(zhuǎn)移方程，能夠?qū)⒃紗栴}巧妙地劃分為一系列相互關(guān)聯(lián)的子問題，并詳細(xì)說明如何從一個(gè)狀態(tài)過渡到另一個(gè)狀態(tài)。這個(gè)過程是動(dòng)態(tài)規(guī)劃問題的核心，為解決復(fù)雜問題提供了框架和方法。7.3結(jié)構(gòu)體的初始化例14.5

有一個(gè)背包，最大容量為C=10?，F(xiàn)有4個(gè)物品，每個(gè)物品有重量w[i]和價(jià)值v[i]。要求選擇一些物品放入背包中，使得在不超過背包容量的前提下，背包中物品的總價(jià)值最大。數(shù)組w={2,3,4,5},v={3,4,5,6}。

在這個(gè)問題中，狀態(tài)可以被定義為“當(dāng)前選擇了前i個(gè)物品，背包剩余容量為j時(shí)的最大總價(jià)值”。具體而言，我們可以用二維數(shù)組dp[i][j]表示這個(gè)狀態(tài)。其中，i表示前i個(gè)物品，j表示背包剩余容量。dp[i][j]的值即為在這個(gè)狀態(tài)下的最大總價(jià)值。7.3結(jié)構(gòu)體的初始化在0-1背包問題中，我們希望求解的是在給定背包容量下，能夠獲得的最大總價(jià)值。為了達(dá)到這個(gè)目標(biāo)，我們需要思考每個(gè)物品放入或不放入背包的決策?？紤]第i個(gè)物品，有兩種選擇：（1）放入背包：如果選擇放入第i個(gè)物品，那么背包的剩余容量就減少了，我們需要找到在剩余容量下選擇前i-1個(gè)物品的最優(yōu)解。此時(shí)的總價(jià)值為dp[i-1][j-weights[i-1]]+values[i-1]。（2）不放入背包：如果選擇不放入第i個(gè)物品，那么背包的容量不變，我們需要找到在相同容量下選擇前i-1個(gè)物品的最優(yōu)解。此時(shí)的總價(jià)值為dp[i-1][j]。7.3結(jié)構(gòu)體的初始化得到狀態(tài)轉(zhuǎn)移方程：if(weights[i-1]<=j){dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weights[i-1]]+values[i-1]);}else{dp[i][j]=dp[i-1][j];}7.3結(jié)