回溯法解決01背包問(wèn)題回溯法解決01背包問(wèn)題回溯法解決01背包問(wèn)題回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題1、算法思想2、問(wèn)題描述3、設(shè)計(jì)實(shí)現(xiàn)

回溯法解決01背包問(wèn)題1、算法思想

回溯法解決01背包問(wèn)題1、算法思想

回溯法解決01背包問(wèn)題回溯法解決01背包問(wèn)題

回溯法：是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問(wèn)題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其原先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。課堂上老師已經(jīng)講解過(guò)用回溯法解決n-皇后問(wèn)題，m-圖著色問(wèn)題以及哈密頓環(huán)問(wèn)題，他們有相同的特征即問(wèn)題的求解目標(biāo)都是求滿足約束條件的全部可行解。而0/1背包是最優(yōu)化問(wèn)題，還需要使用限界函數(shù)剪去已能確認(rèn)不含最優(yōu)答案結(jié)點(diǎn)的子樹。回溯法解決01背包問(wèn)題回溯法：是一個(gè)回溯法解決01背包問(wèn)題回溯法：是一個(gè)回溯法解決0/1背包問(wèn)題運(yùn)用回溯法解題通常包含以下三個(gè)步驟：

a.針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；

b.確定易于搜索的解空間結(jié)構(gòu)；

c.以深度優(yōu)先的方式搜索解空間，并且在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索；回溯法解決0/1背包問(wèn)題運(yùn)用回溯法解題通常包含以下三個(gè)步驟：回溯法解決0/1背包問(wèn)題運(yùn)用回溯法解題通常包含以下三個(gè)步驟：0/1背包問(wèn)題概述

在0/1背包問(wèn)題中，需對(duì)容量為c的背包進(jìn)行裝載。從n個(gè)物品中選取裝入背包的物品，每件物品

i的重量為wi,價(jià)值為pi。對(duì)于可行的背包裝載，背包中的物品的總重量不能超過(guò)背包的容量，最佳裝載是指所裝入的物品價(jià)值最高，即取得最大值。約束條件為c和。在這個(gè)表達(dá)式中，需求出xi的值。xi=1表示物品i裝入背包中，xi=0表示物品i不裝入背包。0/1背包問(wèn)題概述在0/1背包問(wèn)題中，需對(duì)容0/1背包問(wèn)題概述在0/1背包問(wèn)題中，需對(duì)容回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

問(wèn)題舉例最優(yōu)值上界對(duì)于0-1背包問(wèn)題回溯法的一個(gè)實(shí)例，n=4，M=7，p=[9,10,7,4],w=[3,5,2,1].這4個(gè)物品的單位重量?jī)r(jià)值分別為[3,2,3,5,4].以物品為單位價(jià)值的遞減序裝入物品。先裝入物品4，然后裝入物品3和1.裝入這3個(gè)物品后，剩余的背包容量為1，只能裝入0.2個(gè)物品2.由此可得到一個(gè)解為x=[1,0.2,1,1],其相應(yīng)的價(jià)值為22.盡管這不是一個(gè)可行解，但可以證明其價(jià)值是最有大的上界。因此，對(duì)于這個(gè)實(shí)例，最優(yōu)值不超過(guò)22.問(wèn)題舉例最優(yōu)值上界對(duì)于0-1背包問(wèn)題回溯法的一個(gè)實(shí)例，n=4問(wèn)題舉例最優(yōu)值上界對(duì)于0-1背包問(wèn)題回溯法的一個(gè)實(shí)例，n=4回溯法解決01背包問(wèn)題0—1背包問(wèn)題是一個(gè)子集選取問(wèn)題，適合于用子集樹表示0—1背包問(wèn)題的解空間。在搜索解空間樹是，只要其左兒子節(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹，在右子樹中有可能包含最優(yōu)解是才進(jìn)入右子樹搜索。否則將右子樹剪去。回溯法解決01背包問(wèn)題0—1背包問(wèn)題是一個(gè)子集選取問(wèn)題，適合回溯法解決01背包問(wèn)題0—1背包問(wèn)題是一個(gè)子集選取問(wèn)題，適合問(wèn)題分析：首先是將可供選擇的物品的個(gè)數(shù)輸入程序，將物品排成一列，計(jì)算總物品的體積s，然后輸入背包的實(shí)際體積V，如果背包的體積小于0或者大于物品的總體積s，則判斷輸入的背包體積錯(cuò)誤，否則開始順序選取物品裝入背包，假設(shè)已選取了前i件物品之后背包還沒(méi)有裝滿，則繼續(xù)選取第i+1件物品，若該件物品"太大"不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說(shuō)明"剛剛"裝入背包的那件物品"不合適"，應(yīng)將它取出"棄之一邊"，繼續(xù)再?gòu)?它之后"的物品中選取，如此重復(fù)，直至求得滿足條件的解。因?yàn)榛厮萸蠼獾囊?guī)則是"后進(jìn)先出"，所以要用到棧來(lái)存儲(chǔ)符合條件的解，在存儲(chǔ)過(guò)程中，利用數(shù)組來(lái)存儲(chǔ)各個(gè)物品的體積，然后用深度優(yōu)先的搜索方式求解，將符合條件的數(shù)組元素的下標(biāo)存入棧里，最后得到符合條件的解并且實(shí)現(xiàn)輸出。

問(wèn)題分析：首先是將可供選擇的物品的個(gè)數(shù)輸入程序，將物品排成一問(wèn)題分析：首先是將可供選擇的物品的個(gè)數(shù)輸入程序，將物品排成一限界函數(shù)設(shè)r是當(dāng)前剩余物品價(jià)值總和；cp是當(dāng)前結(jié)點(diǎn)X的價(jià)值；bp是當(dāng)前X結(jié)點(diǎn)上界函數(shù)值。L始終為已搜索到的答案節(jié)點(diǎn)中受益的最大值，當(dāng)cp+r=bp<L時(shí)可剪去以X為根的子樹。計(jì)算右子樹中解的上界的更好方法是將剩余物品依其單位重量?jī)r(jià)值排序，然后依次裝入物品，直至裝不下時(shí)，再裝入該物品的一部分而裝滿背包。由此得到的價(jià)值是右子樹中解的上界。限界函數(shù)設(shè)r是當(dāng)前剩余物品價(jià)值總和；cp是當(dāng)前結(jié)點(diǎn)X的價(jià)值；限界函數(shù)設(shè)r是當(dāng)前剩余物品價(jià)值總和；cp是當(dāng)前結(jié)點(diǎn)X的價(jià)值；THANKYOUSUCCESS2023/7/3112可編輯THANKYOUSUCCESS2023/1/912THANKYOUSUCCESS2023/7/271L始終為已搜索到的答案節(jié)點(diǎn)中受益的最大值，最優(yōu)解必定大于等于L，對(duì)于任意結(jié)點(diǎn)X，若其上界函數(shù)值bp<L，則可以斷定X子樹上不含最優(yōu)答案結(jié)點(diǎn)，可以剪去以X為根的子樹ZYXTbp=cp+rrpcw，cpL始終為已搜索到的答案節(jié)點(diǎn)中受益的最大值，最優(yōu)解必定大于等于L始終為已搜索到的答案節(jié)點(diǎn)中受益的最大值，最優(yōu)解必定大于等于考察如下背包問(wèn)題：n=3，w=[11，8，6]，p=[18，25，20]且M=20.三個(gè)對(duì)象的背包問(wèn)題的解空間

10101000101010ABGIFHELDCL=43L=43L=38L=25L=20L=0L=45L=18考察如下背包問(wèn)題：n=3，w=[11，8，6]，p=[18，考察如下背包問(wèn)題：n=3，w=[11，8，6]，p=[18，回溯法解決0/1背包問(wèn)題#include<stdio.h>

intc;//背包容量

intn;//物品數(shù)

intweight[100];//存放n個(gè)物品重量的數(shù)組

intprice[100];//存放n個(gè)物品價(jià)值的數(shù)組

intcurrentWeight=0;//當(dāng)前重量

intcurrentPrice=0;//當(dāng)前價(jià)值

intbestPrice=0;//當(dāng)前最優(yōu)值

intbestAnswer[100];//當(dāng)前最優(yōu)解

intbp=0;intbA[100];//當(dāng)前最優(yōu)解

inttimes=0;

回溯法解決0/1背包問(wèn)題#include<stdio.h>

回溯法解決0/1背包問(wèn)題#include<stdio.h>

回溯法解決01背包問(wèn)題

voidPrint();voidBacktracking(inti){times+=1; if(i>n) { Print(); if(bestPrice>bp) { bp=bestPrice; for(intj=1;j<=n;j++)bA[j]=bestAnswer[j]; } return;}

回溯法解決01背包問(wèn)題

voidPrint();回溯法解決01背包問(wèn)題

voidPrint();回溯法解回溯法解決01背包問(wèn)題if(currentWeight+weight[i]<=c) {//將物品i放入背包，搜索左子樹

bestAnswer[i]=1; currentWeight+=weight[i]; bestPrice+=price[i]; Backtracking(i+1);//完成上面的遞歸，返回到上一結(jié)點(diǎn)，物品i不放入背包，準(zhǔn)備遞歸右子樹

currentWeight-=weight[i]; bestPrice-=price[i]; }bestAnswer[i]=0; Backtracking(i+1);}回溯法解決01背包問(wèn)題if(currentWeight+we回溯法解決01背包問(wèn)題if(currentWeight+we回溯法解決01背包問(wèn)題voidPrint(){ inti; printf("\n路徑為{"); for(i=1;i<n;++i) printf("%d,",bestAnswer[i]); printf("%d}\t價(jià)值為%d\n",bestAnswer[i],bestPrice);}voidmain(){ inti; /*輸入部分*/printf("請(qǐng)輸入物品的數(shù)量:\n");scanf("%d",&n);printf("請(qǐng)輸入背包的容量(能承受的重量):\n");scanf("%d",&c);printf("請(qǐng)依次輸入%d個(gè)物品的重量:\n",n);回溯法解決01背包問(wèn)題voidPrint()回溯法解決01背包問(wèn)題voidPrint()回溯法解決0回溯法解決01背包問(wèn)題for(i=1;i<=n;i++)scanf("%d",&weight[i]);printf("請(qǐng)依次輸入%d個(gè)物品的價(jià)值:\n",n);for(i=1;i<=n;i++)scanf("%d",&price[i]); printf("各符合條件的路徑為：\n"); Backtracking(1); printf("*******************************************************\n"); printf("\nthebestansweris{"); for(i=1;i<n;++i) printf("%d,",bA[i]); printf("%d}\tthepriceis%d\n",bA[i],bp); printf("\n\n總共搜索結(jié)點(diǎn)數(shù)%d\n",times);}回溯法解決01背包問(wèn)題for(i=1;i<=n;i++)回溯法解決01背包問(wèn)題for(i=1;i<=n;i++)回溯回溯法解決01背包問(wèn)題回溯法解決01背包問(wèn)題回溯法解決01背包問(wèn)題回溯法解決01背包問(wèn)題回溯法解決01背包問(wèn)題

物品情況搜索結(jié)點(diǎn)數(shù)遞歸法n=3w=20,15,10;c=25v=20,30,25;11遞歸法n=4w=10,20,30,40;c=30v=4,3,2,1;17遞歸法n=4w=30,25,10,35c=40v=7,9,3,619遞歸法n=4w=7,3,4,5c=10v=42,12,40,2522回溯法解決01背包問(wèn)題

物品情況回溯法解決01背包問(wèn)題

物品情況回溯法解決01背包問(wèn)題THANKYOU!回溯法解決01背包問(wèn)題THANKYOU!回溯法解決01背包問(wèn)題THANKYOU!回溯法解決01背THANKYOUSUCCESS2023/7/3123可編輯THANKYOUSUCCESS2023/1/923THANKYOUSUCCESS2023/7/272回溯法解決01背包問(wèn)題回溯法解決01背包問(wèn)題回溯法解決01背包問(wèn)題回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題1、算法思想2、問(wèn)題描述3、設(shè)計(jì)實(shí)現(xiàn)

回溯法解決01背包問(wèn)題1、算法思想

回溯法解決01背包問(wèn)題1、算法思想

回溯法解決01背包問(wèn)題回溯法解決01背包問(wèn)題

回溯法：是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問(wèn)題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其原先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。課堂上老師已經(jīng)講解過(guò)用回溯法解決n-皇后問(wèn)題，m-圖著色問(wèn)題以及哈密頓環(huán)問(wèn)題，他們有相同的特征即問(wèn)題的求解目標(biāo)都是求滿足約束條件的全部可行解。而0/1背包是最優(yōu)化問(wèn)題，還需要使用限界函數(shù)剪去已能確認(rèn)不含最優(yōu)答案結(jié)點(diǎn)的子樹。回溯法解決01背包問(wèn)題回溯法：是一個(gè)回溯法解決01背包問(wèn)題回溯法：是一個(gè)回溯法解決0/1背包問(wèn)題運(yùn)用回溯法解題通常包含以下三個(gè)步驟：

a.針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；

b.確定易于搜索的解空間結(jié)構(gòu)；

c.以深度優(yōu)先的方式搜索解空間，并且在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索；回溯法解決0/1背包問(wèn)題運(yùn)用回溯法解題通常包含以下三個(gè)步驟：回溯法解決0/1背包問(wèn)題運(yùn)用回溯法解題通常包含以下三個(gè)步驟：0/1背包問(wèn)題概述

在0/1背包問(wèn)題中，需對(duì)容量為c的背包進(jìn)行裝載。從n個(gè)物品中選取裝入背包的物品，每件物品

i的重量為wi,價(jià)值為pi。對(duì)于可行的背包裝載，背包中的物品的總重量不能超過(guò)背包的容量，最佳裝載是指所裝入的物品價(jià)值最高，即取得最大值。約束條件為c和。在這個(gè)表達(dá)式中，需求出xi的值。xi=1表示物品i裝入背包中，xi=0表示物品i不裝入背包。0/1背包問(wèn)題概述在0/1背包問(wèn)題中，需對(duì)容0/1背包問(wèn)題概述在0/1背包問(wèn)題中，需對(duì)容回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

回溯法解決01背包問(wèn)題

問(wèn)題舉例最優(yōu)值上界對(duì)于0-1背包問(wèn)題回溯法的一個(gè)實(shí)例，n=4，M=7，p=[9,10,7,4],w=[3,5,2,1].這4個(gè)物品的單位重量?jī)r(jià)值分別為[3,2,3,5,4].以物品為單位價(jià)值的遞減序裝入物品。先裝入物品4，然后裝入物品3和1.裝入這3個(gè)物品后，剩余的背包容量為1，只能裝入0.2個(gè)物品2.由此可得到一個(gè)解為x=[1,0.2,1,1],其相應(yīng)的價(jià)值為22.盡管這不是一個(gè)可行解，但可以證明其價(jià)值是最有大的上界。因此，對(duì)于這個(gè)實(shí)例，最優(yōu)值不超過(guò)22.問(wèn)題舉例最優(yōu)值上界對(duì)于0-1背包問(wèn)題回溯法的一個(gè)實(shí)例，n=4問(wèn)題舉例最優(yōu)值上界對(duì)于0-1背包問(wèn)題回溯法的一個(gè)實(shí)例，n=4回溯法解決01背包問(wèn)題0—1背包問(wèn)題是一個(gè)子集選取問(wèn)題，適合于用子集樹表示0—1背包問(wèn)題的解空間。在搜索解空間樹是，只要其左兒子節(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹，在右子樹中有可能包含最優(yōu)解是才進(jìn)入右子樹搜索。否則將右子樹剪去。回溯法解決01背包問(wèn)題0—1背包問(wèn)題是一個(gè)子集選取問(wèn)題，適合回溯法解決01背包問(wèn)題0—1背包問(wèn)題是一個(gè)子集選取問(wèn)題，適合問(wèn)題分析：首先是將可供選擇的物品的個(gè)數(shù)輸入程序，將物品排成一列，計(jì)算總物品的體積s，然后輸入背包的實(shí)際體積V，如果背包的體積小于0或者大于物品的總體積s，則判斷輸入的背包體積錯(cuò)誤，否則開始順序選取物品裝入背包，假設(shè)已選取了前i件物品之后背包還沒(méi)有裝滿，則繼續(xù)選取第i+1件物品，若該件物品"太大"不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說(shuō)明"剛剛"裝入背包的那件物品"不合適"，應(yīng)將它取出"棄之一邊"，繼續(xù)再?gòu)?它之后"的物品中選取，如此重復(fù)，直至求得滿足條件的解。因?yàn)榛厮萸蠼獾囊?guī)則是"后進(jìn)先出"，所以要用到棧來(lái)存儲(chǔ)符合條件的解，在存儲(chǔ)過(guò)程中，利用數(shù)組來(lái)存儲(chǔ)各個(gè)物品的體積，然后用深度優(yōu)先的搜索方式求解，將符合條件的數(shù)組元素的下標(biāo)存入棧里，最后得到符合條件的解并且實(shí)現(xiàn)輸出。

問(wèn)題分析：首先是將可供選擇的物品的個(gè)數(shù)輸入程序，將物品排成一問(wèn)題分析：首先是將可供選擇的物品的個(gè)數(shù)輸入程序，將物品排成一限界函數(shù)設(shè)r是當(dāng)前剩余物品價(jià)值總和；cp是當(dāng)前結(jié)點(diǎn)X的價(jià)值；bp是當(dāng)前X結(jié)點(diǎn)上界函數(shù)值。L始終為已搜索到的答案節(jié)點(diǎn)中受益的最大值，當(dāng)cp+r=bp<L時(shí)可剪去以X為根的子樹。計(jì)算右子樹中解的上界的更好方法是將剩余物品依其單位重量?jī)r(jià)值排序，然后依次裝入物品，直至裝不下時(shí)，再裝入該物品的一部分而裝滿背包。由此得到的價(jià)值是右子樹中解的上界。限界函數(shù)設(shè)r是當(dāng)前剩余物品價(jià)值總和；cp是當(dāng)前結(jié)點(diǎn)X的價(jià)值；限界函數(shù)設(shè)r是當(dāng)前剩余物品價(jià)值總和；cp是當(dāng)前結(jié)點(diǎn)X的價(jià)值；THANKYOUSUCCESS2023/7/3135可編輯THANKYOUSUCCESS2023/1/912THANKYOUSUCCESS2023/7/273L始終為已搜索到的答案節(jié)點(diǎn)中受益的最大值，最優(yōu)解必定大于等于L，對(duì)于任意結(jié)點(diǎn)X，若其上界函數(shù)值bp<L，則可以斷定X子樹上不含最優(yōu)答案結(jié)點(diǎn)，可以剪去以X為根的子樹ZYXTbp=cp+rrpcw，cpL始終為已搜索到的答案節(jié)點(diǎn)中受益的最大值，最優(yōu)解必定大于等于L始終為已搜索到的答案節(jié)點(diǎn)中受益的最大值，最優(yōu)解必定大于等于考察如下背包問(wèn)題：n=3，w=[11，8，6]，p=[18，25，20]且M=20.三個(gè)對(duì)象的背包問(wèn)題的解空間

10101000101010ABGIFHELDCL=43L=43L=38L=25L=20L=0L=45L=18考察如下背包問(wèn)題：n=3，w=[11，8，6]，p=[18，考察如下背包問(wèn)題：n=3，w=[11，8，6]，p=[18，回溯法解決0/1背包問(wèn)題#include<stdio.h>

intc;//背包容量

intn;//物品數(shù)

intweight[100];//存放n個(gè)物品重量的數(shù)組

intprice[100];//存放n個(gè)物品價(jià)值的數(shù)組

intcurrentWeight=0;//當(dāng)前重量

intcurrentPrice=0;//當(dāng)前價(jià)值

intbestPrice=0;//當(dāng)前最優(yōu)值

intbestAnswer[100];//當(dāng)前最優(yōu)解

intbp=0;intbA[100];//當(dāng)前最優(yōu)解

inttimes=0;

回溯法解決0/1背包問(wèn)題#include<stdio.h>

回溯法解決0/1背包問(wèn)題#include<stdio.h>

回溯法解決01背包問(wèn)題

voidPrint();voidBacktracking(inti){times+=1; if(i>n) { Print(); if(bestPrice>bp) { bp=bestPrice; for(intj=1;j<=n;j++)bA[j]=bestAnswer[j]; } return;}

回溯法解決01背包問(wèn)題

voidPrint();回溯法解決01背包問(wèn)題

voidPrint();回溯法解回溯法解決01背包問(wèn)題if(currentWeight+weight[i]<=c) {//將物品i放入背包，搜索左子樹

bestAnswer[i]=1; currentWeight+=weight[i]; bestPrice+=price[i]; Backtracking(i+1);//完成上面的遞歸，返回到上一結(jié)點(diǎn)，物品i不放入背包，準(zhǔn)備遞歸右子樹

currentWeight-=weight[i]; bestPrice-=price[i]; }bestAnswer[i]=0; Backtracking(i+1);}回溯法解決01背包問(wèn)題if(currentWeight+we回溯法解決01背包問(wèn)題if(currentWeight+we回溯法解決01背包問(wèn)題voidPrint(){ inti; printf("\n路徑為{"); for(i=1;i<n;++i) printf("%d,",bestAnswer[i]); printf("%d}\t價(jià)值為%d\n",bestAnswer[i],bestPrice);}voidmain(){ inti; /*輸入部分*/printf("請(qǐng)輸入物品的數(shù)量:\n");scanf("%d",&n);printf("請(qǐng)輸入背包的容量(能承受的重量):\n");scanf("%d",&c);print