算法設(shè)計與分析 習(xí)題答案 田小霞

國家級實驗教學(xué)示范中心計算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計與分析習(xí)題答案田小霞楊圣云陳炫銳邱維陽編著清華大學(xué)出版社北京

目錄第一章算法基礎(chǔ) 第一章算法基礎(chǔ)1.漸進(jìn)式(1)50n(2)2n2(3)5n2.上界和下界(1)n2(2)4n3(3)n23.T(n)=n(n+1)(2n+1)/6，O(n3)。提示：自然數(shù)平方和4.略?？刹贾梅纸M任務(wù)。5.略。第二章遞歸與分治1.B2.C3.C4.A5.C6.一般分為3個子問題，比較第1個和第2個子問題的硬幣是否相等，如果兩個子問題相等，假幣在第3個子問題中；否則假幣在較輕的子問題中；繼續(xù)分割子問題，直到找到假幣。時間復(fù)雜度為。（此題也可以分解為兩個子問題來求解，復(fù)雜度）7.略。8.參考代碼如下：#include<iostream>#include<algorithm>usingnamespacestd;intres=1;voiddfs(intcnt,intn,intf[],boolst[],intans[]){ if(cnt==n+1) { cout<<"這是第"<<res<<"個排列："; for(intk=1;k<=n;k++) { cout<<ans[k]; if(k!=n)cout<<","; elsecout<<'\n'; } res++; return; } for(inti=1;i<=n;i++) { if(!st[i]) { st[i]=true; ans[cnt]=f[i]; dfs(cnt+1,n,f,st,ans); st[i]=false; } }}intmain(){ cout<<"請輸入序列的數(shù)量："; intn; cin>>n; intf[n+10],ans[n+10]; boolst[n+10]; cout<<"請輸入"<<n<<"個不重復(fù)的數(shù)（使用空格或回車隔開）：\n"; for(inti=1;i<=n;i++) cin>>f[i]; for(inti=1;i<=n;i++)st[i]=false; dfs(1,n,f,st,ans); return0;}9.此題與例題2.3.2相似。時間復(fù)雜度為O(n+m)。參考代碼如下：#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintN=1010,M=N*2;intn,m,k;intf[N][N];boolcheck(){ intl=n,r=1; while(l>=1&&r<=m) { if(f[l][r]==k)returntrue; if(f[l][r]>k)l--; elser++; } returnfalse;}intmain(){ cout<<"請輸入矩陣大小和目標(biāo)值k:";cin>>n>>m>>k;cout<<"\n請輸入符合題目要求的矩陣：\n";for(inti=1;i<=n;i++) for(intj=1;j<=m;j++) cin>>f[i][j];if(check())cout<<"Yes\n";elsecout<<"No\n"; return0;}10.代碼：f1=1f2=1for(i=3;i<n;i++)sum=f1+f2f1=f2f2=sum時間復(fù)雜度O(n)。11.此題與例題2.3.7相似。12.參考代碼如下：//矩陣快速冪#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;typedeflonglongLL;intn,mod=10000;voidqmi(inta[],intb[][2]){inttemp[2]={0,0};for(inti=0;i<2;i++)for(intj=0;j<2;j++)temp[i]=(temp[i]+(LL)a[j]*b[j][i])%mod;memcpy(a,temp,sizeoftemp);}voidqmi(inta[][2],intb[][2]){inttemp[2][2]={0};for(inti=0;i<2;i++)for(intj=0;j<2;j++)for(intk=0;k<2;k++)temp[i][j]=(temp[i][j]+(LL)a[i][k]*b[k][j])%mod;memcpy(a,temp,sizeoftemp);}intmain(){cin>>n;intf1[2]={1,1};inta[2][2]={{1,1},{1,0}};n--;while(n){if(n&1)qmi(f1,a);qmi(a,a);n>>=1;}cout<<f1[1]<<'\n';return0;}13.按分治策略，將所有的選手分為兩半，n個選手的比賽日程表就可以通過為n/2個選手設(shè)計的比賽日程表來決定。遞歸地用對選手進(jìn)行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單。這時只要讓這2個選手進(jìn)行比賽就可以了。123456782143658734127856432187655678123465872143785634128765432114.參考代碼如下：#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;typedeflonglongLL;intqmi(inta,intn,intp){ intres=1; while(n) { if(n&1)res=(LL)res*a%p; a=(LL)a*a%p; n>>=1; } returnres;}intmain(){inta,n,p;cin>>a>>n>>p;cout<<qmi(a,n,p)<<'\n';return0;}15.參考代碼如下：#include<bits/stdc++.h>usingnamespacestd;intn,k;vector<int>to[200005];vector<int>len[200005];longlongdeep[200005];intdiep[200005];intsize[200005];intson[200005];intnid[200005];intid[200005];intcnt;map<longlong,int>dep;intans=1e9;voiddfs1(intnow,intlast){size[now]=1;id[now]=++cnt;nid[cnt]=now;intmx=0;for(inti=0;i<to[now].size();i++){intnext=to[now][i];if(next==last)continue;deep[next]=deep[now]+len[now][i];diep[next]=diep[now]+1;dfs1(next,now);size[now]+=size[next];if(size[next]>mx){mx=size[next];son[now]=next;}}}voidupdata(intx,intk){intdx=deep[x];if(k==-1){dep[dx]=0;}else{inttmp=dep[dx];if(tmp==0)tmp=1e9;dep[dx]=min(tmp,diep[x]);}}voiddfs2(intnow,intlast,boolkeep){for(autonext:to[now]){if(next==son[now]ornext==last)continue;dfs2(next,now,0);}if(son[now])dfs2(son[now],now,1);for(autonext:to[now]){if(next==son[now]ornext==last)continue;for(inti=0;i<size[next];i++){intnxt=nid[id[next]+i];intreq=k+2*deep[now]-deep[nxt];if(dep[req]){ans=min(ans,dep[req]+diep[nxt]-2*diep[now]);}}for(inti=0;i<size[next];i++){updata(nid[id[next]+i],1);}}updata(now,1);if(dep[deep[now]+k])ans=min(ans,dep[deep[now]+k]-diep[now]);if(keep==0){for(inti=0;i<size[now];i++){updata(nid[id[now]+i],-1);}}}intmain(){cin>>n>>k;for(inti=1;i<n;i++){intu,v,w;scanf("%d%d%d",&u,&v,&w);to[u].push_back(v);to[v].push_back(u);len[u].push_back(w);len[v].push_back(w);}diep[0]=1;dfs1(0,0);dfs2(0,0,0);if(ans==1e9)ans=-1;cout<<ans;return0;}16.參考代碼如下：#include<stdio.h>#include<iostream>#include<algorithm>#include<string.h>#definemaxn20010#definelowbit(x)x&(-x)#definemem(a,b)memset(a,b,sizeof(a))#definelllonglong#defineINF0x3f3f3f3fusingnamespacestd;intn;structnode{intto,next,w;}edge[maxn*2];inthead[maxn],tot;intvis[maxn];intf[maxn],son[maxn],core,sum;intd[maxn],t[5];intans;voidinit(){mem(head,-1);tot=ans=0;mem(vis,0);}voidadd(inta,intb,intc){edge[tot].to=b,edge[tot].next=head[a],edge[tot].w=c;head[a]=tot++;}voidgetcore(intu,intfa){son[u]=1,f[u]=0;for(inti=head[u];i!=-1;i=edge[i].next){intv=edge[i].to;if(vis[v]||v==fa)continue;getcore(v,u);son[u]+=son[v];f[u]=max(f[u],son[v]);}f[u]=max(f[u],sum-son[u]);if(f[u]<f[core])core=u;//f[u]算出后取最小的一個}voidgetdeep(intu,intfa){//計算u所在子樹每個點相對u的深度+u自身的深度t[d[u]]++;for(inti=head[u];i!=-1;i=edge[i].next){intv=edge[i].to,w=edge[i].w;if(vis[v]||v==fa)continue;d[v]=(d[u]+w)%3;getdeep(v,u);}}intcal(intu,intw){d[u]=w%3;t[0]=t[1]=t[2]=0;//初始化！getdeep(u,0);//printf("%d%d%d%d\n",u,t[0],t[1],t[2]);returnt[1]*t[2]*2+t[0]*t[0];}voidwork(intu){//點分治主過程ans+=cal(u,0);//求經(jīng)過重心u的合法路徑數(shù)vis[u]=1;for(inti=head[u];i!=-1;i=edge[i].next){intv=edge[i].to,w=edge[i].w;if(vis[v])continue;ans-=cal(v,w);//減去僅屬于一個分支的合法路徑數(shù)（不符合路徑定義）sum=son[v],core=0;getcore(v,0);work(core);}}intgcd(inta,intb){returnb==0?a:gcd(b,a%b);}intmain(){scanf("%d",&n);init();for(inti=0;i<n-1;i++){inta,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c%3),add(b,a,c%3);}core=0,sum=n,f[0]=INF;getcore(1,0);work(core);inttmp=gcd(ans,n*n);printf("%d/%d\n",ans/tmp,n*n/tmp);return0;}第三章貪心算法ABBACBBCAB解：算法步驟如下輸入：鱷魚的坐標(biāo)列表和007的最大跳躍距離。初始化：將島的邊緣坐標(biāo)計算出來，即所有距離(0,0)小于等于7.5米的點。計算跳躍路徑：從池子的邊緣開始（例如可以從東北角(50,50)開始），嘗試向島的中心(0,0)跳躍。對于每個可能的跳躍點，檢查該點是否在鱷魚的位置上，如果在，則標(biāo)記為不可達(dá)；如果不在，則檢查從當(dāng)前點到該點的距離是否小于等于007的最大跳躍距離。如果存在至少一條路徑，使得007可以從池子的邊緣跳到島上而不碰到任何鱷魚，則返回“可以逃脫”。輸出：如果找到至少一條安全路徑，輸出“可以逃脫”，否則輸出“無法逃脫”。代碼參考如下：importmathdefcan_escape(crocodile_positions,max_jump_distance):#鱷魚池的尺寸pond_size=100#島的半徑island_radius=7.5#檢查一個點是否在鱷魚的位置上defis_crocodile(x,y):forcx,cyincrocodile_positions:ifmath.isclose(x,cx)andmath.isclose(y,cy):returnTruereturnFalse#檢查從當(dāng)前點(x,y)跳躍到(nx,ny)是否可行defcan_jump(x,y,nx,ny):distance=math.sqrt((nx-x)**2+(ny-y)**2)returndistance<=max_jump_distanceandnotis_crocodile(nx,ny)#檢查從池子的邊緣是否存在一條路徑到達(dá)島上defcheck_path_exists():#只需要從池子的邊緣檢查一個點即可，因為問題是對稱的start_x,start_y=pond_size,0#可以選擇任意邊緣點，這里選擇右下角#使用廣度優(yōu)先搜索(BFS)來查找路徑queue=[(start_x,start_y)]visited=set(queue)whilequeue:x,y=queue.pop(0)#如果當(dāng)前點在島上ifmath.sqrt(x**2+y**2)<=island_radius:returnTrue#嘗試所有可能的跳躍方向directions=[(-1,0),(1,0),(0,-1),(0,1)]#上下左右fordx,dyindirections:nx,ny=x+dx,y+dy#檢查新點是否在池子內(nèi)且未被訪問過if0<=nx<=pond_sizeand0<=ny<=pond_sizeand(nx,ny)notinvisited:#如果可以跳躍到新點ifcan_jump(x,y,nx,ny):visited.add((nx,ny))queue.append((nx,ny))#如果沒有找到路徑returnFalse#調(diào)用函數(shù)檢查路徑是否存在returncheck_path_exists()#示例用法crocodile_positions=[(30,30),(40,40),(50,50)]#鱷魚的位置max_jump_distance=10#007的最大跳躍距離print(can_escape(crocodile_positions,max_jump_distance))#輸出：False或True解：首先，我們需要對孩子們的胃口值g和餅干尺寸s進(jìn)行排序。然后，我們從最小的胃口和最小的餅干開始匹配，如果當(dāng)前餅干可以滿足當(dāng)前孩子的胃口，我們就分配這塊餅干給孩子，并繼續(xù)匹配下一個孩子和下一塊餅干。如果不能滿足，我們就嘗試下一塊更大的餅干。具體代碼參考如下：deffindContentChildren(g,s):#對孩子們的胃口和餅干尺寸進(jìn)行排序g.sort()s.sort()child=0#當(dāng)前匹配到的孩子索引cookie=0#當(dāng)前匹配到的餅干索引satisfied=0#滿足的孩子數(shù)量#當(dāng)孩子和餅干都還有剩余時，進(jìn)行匹配whilechild<len(g)andcookie<len(s):ifs[cookie]>=g[child]:#如果當(dāng)前餅干可以滿足當(dāng)前孩子的胃口satisfied+=1child+=1#匹配下一個孩子cookie+=1#嘗試下一塊餅干returnsatisfied#示例g=[1,2,3]s=[1,1]print(findContentChildren(g,s))#輸出:1解：要使最遠(yuǎn)的兩個洞穴之間的距離盡可能小，并且仍然可以從其他洞穴到達(dá)每個洞穴，可以構(gòu)建一個這樣的隧道系統(tǒng)：將洞穴視為圖的節(jié)點，隧道視為圖的邊，構(gòu)建一個連通圖，其中任意兩點間的最長路徑盡可能短。一個有效的方法是使用最小生成樹，具體的代碼參考如下：importheapqdefprim_algorithm(n):#初始化tunnels=[]visited=[False]*nedges=[(0,i,1)foriinrange(1,n)]#從洞穴0開始，到所有其他洞穴的邊，權(quán)值都為1heapq.heapify(edges)#將邊放入最小堆中#Prim算法主循環(huán)whileedges:cost,u,v=heapq.heappop(edges)ifnotvisited[v]:visited[v]=Truetunnels.append((u,v,cost))foriinrange(n):ifnotvisited[i]andi!=u:heapq.heappush(edges,(1,v,i))#添加從v到所有未訪問洞穴的邊，權(quán)值都為1returntunnels#示例n=5tunnels=prim_algorithm(n)print(tunnels)#輸出可能類似于：[(0,1,1),(1,2,1),(2,3,1),(3,4,1)]，表示連接洞穴的隧道及其權(quán)值解：這個問題是一個經(jīng)典的“雙指針”問題，可以通過移動兩個指針來找到最大水量的容器。雙指針法本質(zhì)上是一種貪心算法，因為我們每次移動指針都是為了尋找可能的更大容器。具體的參考代碼如下：defmax_area(height):left=0#左指針right=len(height)-1#右指針max_water=0#最大水量whileleft<right:#當(dāng)前容器的寬度width=right-left#當(dāng)前容器能容納的水量current_water=min(height[left],height[right])*width#更新最大水量max_water=max(max_water,current_water)#貪心策略：移動較短的那根線以嘗試找到更大的容積ifheight[left]<height[right]:left+=1else:right-=1returnmax_water#測試height=[1,8,6,2,5,4,8,3,7]print("最大可以容納的水量:",max_area(height))解：defmax_activities(n,activities):#按照結(jié)束時間排序activities.sort(key=lambdax:x[1])#初始化計數(shù)器和前一個活動的結(jié)束時間count=0last_end_time=0foractivityinactivities:start,end=activity#如果當(dāng)前活動的開始時間不早于上一個活動的結(jié)束時間ifstart>=last_end_time:#安排這個活動count+=1last_end_time=endreturncount#輸入n=int(input())activities=[tuple(map(int,input().split()))for_inrange(n)]#計算并輸出最多能安排的活動數(shù)量print("最多能夠安排的活動數(shù)量:",max_activities(n,activities))第四章回溯法一、選擇題1．在解決問題時，回溯法的主要特點是（）。A.避免了系統(tǒng)地搜索所有的可能解B.能夠快速找到最優(yōu)解C.一旦發(fā)現(xiàn)當(dāng)前選擇不會產(chǎn)生期望的結(jié)果，它會立即放棄這條路徑D.總是保證找到全局最優(yōu)解解答：C.一旦發(fā)現(xiàn)當(dāng)前選擇不會產(chǎn)生期望的結(jié)果，它會立即放棄這條路徑講解：避免系統(tǒng)地搜索所有的可能解（A）：這并不是回溯法的主要特點。事實上，回溯法是一種系統(tǒng)的搜索算法，但它通過剪枝（即提前終止一些不可能產(chǎn)生有效解的搜索路徑）來提高效率。能夠快速找到最優(yōu)解（B）：回溯法并不保證能夠快速找到最優(yōu)解。它只是通過系統(tǒng)地搜索解空間來找到所有可能的解，并通過剪枝來減少不必要的計算量。一旦發(fā)現(xiàn)當(dāng)前選擇不會產(chǎn)生期望的結(jié)果，它會立即放棄這條路徑（C）：這正是回溯法的核心特點。回溯法通過在搜索過程中不斷評估當(dāng)前路徑是否有可能達(dá)到目標(biāo)，如果發(fā)現(xiàn)不可能達(dá)到目標(biāo)，就會立即放棄當(dāng)前路徑，回溯到上一步進(jìn)行其他選擇?？偸潜ＷC找到全局最優(yōu)解（D）：回溯法不一定能保證找到全局最優(yōu)解。它可以找到所有可能的解，但是否最優(yōu)取決于具體問題和實現(xiàn)方法。例如，對于某些優(yōu)化問題，可能需要結(jié)合其他方法（如動態(tài)規(guī)劃或啟發(fā)式算法）來找到最優(yōu)解。2．在使用回溯法進(jìn)行搜索時，通常采用（）策略。A.廣度優(yōu)先搜索B.深度優(yōu)先搜索C.貪心算法D.動態(tài)規(guī)劃解答：B.深度優(yōu)先搜索講解：廣度優(yōu)先搜索（A）：廣度優(yōu)先搜索是一種逐層擴(kuò)展節(jié)點的搜索策略，通常用于尋找最短路徑等問題，而不是回溯法的主要策略?；厮莘ǜm合逐步深入到問題的各個分支，廣度優(yōu)先搜索會在同一層的所有節(jié)點都被擴(kuò)展后，才會進(jìn)入下一層，這與回溯法逐步深入的特點不符。深度優(yōu)先搜索（B）：回溯法的核心是逐步深入探索每一條可能的路徑，直到發(fā)現(xiàn)問題或達(dá)到目標(biāo)，然后回溯到上一步進(jìn)行其他選擇。這種逐步深入的方式正是深度優(yōu)先搜索的特點，因此，回溯法通常采用深度優(yōu)先搜索策略。貪心算法（C）：貪心算法在每一步選擇中都選擇當(dāng)前最優(yōu)解，不考慮全局最優(yōu)解是否能通過當(dāng)前選擇達(dá)到。而回溯法是通過全面搜索來找到所有可能解，不局限于當(dāng)前最優(yōu)解，因此，貪心算法不是回溯法的策略。動態(tài)規(guī)劃（D）：動態(tài)規(guī)劃通過將問題分解為子問題，并保存子問題的解來避免重復(fù)計算，從而優(yōu)化計算過程。雖然動態(tài)規(guī)劃和回溯法都用于解決復(fù)雜問題，但它們的策略不同，動態(tài)規(guī)劃不是回溯法的搜索策略。3．回溯法通常用于解決（）類型的問題。A.優(yōu)化問題B.搜索問題C.數(shù)值計算問題D.數(shù)據(jù)排序問題解答：B.搜索問題講解：優(yōu)化問題（A）：雖然回溯法可以用于某些優(yōu)化問題，但它主要用于全面搜索所有可能解的情況，并不專門針對優(yōu)化問題。針對優(yōu)化問題，通常會使用動態(tài)規(guī)劃、貪心算法等更高效的方法。搜索問題（B）：回溯法是一種系統(tǒng)的搜索算法，用于遍歷所有可能的解空間，尋找滿足特定條件的解。因此，它廣泛應(yīng)用于各種搜索問題，如組合問題、排列問題、子集問題和路徑問題等。數(shù)值計算問題（C）：數(shù)值計算問題通常涉及數(shù)值分析和科學(xué)計算，回溯法并不適合解決這類問題。這類問題通常使用數(shù)值算法、線性代數(shù)方法等更合適的方法。數(shù)據(jù)排序問題（D）：數(shù)據(jù)排序問題有專門的排序算法，如快速排序、歸并排序、堆排序等?；厮莘ú皇墙鉀Q數(shù)據(jù)排序問題的主要方法。4．回溯法在遇到不滿足條件的路徑時會怎么做？（）A.繼續(xù)向前搜索B.轉(zhuǎn)而搜索其他路徑C.返回上一步，嘗試其他可能性D.停止整個搜索過程解答：C.返回上一步，嘗試其他可能性講解：繼續(xù)向前搜索（A）：如果當(dāng)前路徑已經(jīng)被確定為不滿足條件，繼續(xù)向前搜索是沒有意義的，會浪費計算資源。因此，回溯法不會選擇這種策略。轉(zhuǎn)而搜索其他路徑（B）：回溯法確實會搜索其他路徑，但具體的操作是先回到上一步，然后嘗試其他可能性，而不是直接轉(zhuǎn)到其他路徑。返回上一步，嘗試其他可能性（C）：這是回溯法的核心特點。當(dāng)發(fā)現(xiàn)當(dāng)前路徑不滿足條件時，它會回溯到上一步（即上一個決策點），并嘗試其他可能的選擇，直到找到一個滿足條件的解或者所有路徑都嘗試過。停止整個搜索過程（D）：除非所有可能的路徑都被嘗試過，回溯法不會停止搜索。如果僅僅因為一條路徑不滿足條件就停止整個搜索過程，問題將無法得到完整解決。5．以下哪項不是回溯法的典型應(yīng)用場景？（）A.解決N-皇后問題B.找出圖中的最短路徑C.計算數(shù)組的所有子集D.排列組合問題解答：B.找出圖中的最短路徑講解：解決N-皇后問題（A）：N-皇后問題是回溯法的經(jīng)典應(yīng)用之一。回溯法通過逐步嘗試將皇后放置在棋盤的每一列中，避免沖突，直到找到所有可能的解決方案。找出圖中的最短路徑（B）：尋找圖中的最短路徑通常使用的是廣度優(yōu)先搜索（BFS）或Dijkstra算法等?；厮莘ㄓ糜谶@種問題效率較低，因為它不具備優(yōu)先探索最短路徑的機(jī)制。計算數(shù)組的所有子集（C）：回溯法適用于生成所有可能的子集。它通過遞歸地選擇或不選擇每個元素，來構(gòu)建所有子集。排列組合問題（D）：回溯法非常適合解決排列組合問題。它通過遞歸地選擇和排列元素，生成所有可能的排列和組合。6．關(guān)于回溯法和遞歸的關(guān)系，以下哪項描述是正確的？（）A.回溯法和遞歸沒有任何關(guān)聯(lián)B.回溯法通常采用迭代而非遞歸C.回溯法總是使用遞歸來實現(xiàn)D.回溯法可以使用遞歸，也可以不使用解答：D.回溯法可以使用遞歸，也可以不使用講解：回溯法和遞歸沒有任何關(guān)聯(lián)（A）：這是不正確的?；厮莘ㄍǔＥc遞歸有很強(qiáng)的關(guān)聯(lián)，因為遞歸是實現(xiàn)回溯法的一種常見方法。回溯法通常采用迭代而非遞歸（B）：這也是不準(zhǔn)確的。雖然回溯法可以使用迭代來實現(xiàn)，但更常見的是使用遞歸來實現(xiàn)?；厮莘偸鞘褂眠f歸來實現(xiàn)（C）：這并不完全正確?；厮莘梢酝ㄟ^遞歸來實現(xiàn)，但并不總是使用遞歸。它也可以通過顯式的棧來實現(xiàn)迭代的方式。回溯法可以使用遞歸，也可以不使用（D）：這是正確的?；厮莘ǖ膶崿F(xiàn)可以使用遞歸，也可以使用迭代。遞歸實現(xiàn)是回溯法的常見方式，但有時為了優(yōu)化性能或減少遞歸深度，也會使用顯式棧的迭代方式來實現(xiàn)。7．關(guān)于回溯法以下敘述中不正確的是()。A.回溯法有“通用解題法”之稱，它可以系統(tǒng)地搜索一個問題的所有解或任意解B.回溯法需要借助隊列這種結(jié)構(gòu)來保存從根結(jié)點到當(dāng)前擴(kuò)展結(jié)點的路徑C.回溯法是一種既帶系統(tǒng)性又帶跳躍性的搜索算法D.回溯法在生成解空間的任一結(jié)點時先判斷該結(jié)點是否可能包含問題的解，如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向祖先結(jié)點回溯解答：B.回溯法需要借助隊列這種結(jié)構(gòu)來保存從根結(jié)點到當(dāng)前擴(kuò)展結(jié)點的路徑講解：回溯法有“通用解題法”之稱，它可以系統(tǒng)地搜索一個問題的所有解或任意解（A）：這句話是正確的?；厮莘ù_實被稱為“通用解題法”，因為它可以系統(tǒng)地搜索問題的所有可能解或任意一個解?；厮莘ㄐ枰柚犃羞@種結(jié)構(gòu)來保存從根結(jié)點到當(dāng)前擴(kuò)展結(jié)點的路徑（B）：這句話是不正確的?；厮莘ㄍǔＪ褂眠f歸?；蝻@式的棧結(jié)構(gòu)來保存路徑，而不是隊列。隊列通常用于廣度優(yōu)先搜索（BFS），而不是回溯法的深度優(yōu)先搜索（DFS）?；厮莘ㄊ且环N既帶系統(tǒng)性又帶跳躍性的搜索算法（C）：這句話是正確的?；厮莘ㄍㄟ^系統(tǒng)地探索每一條路徑，同時在遇到不符合條件的路徑時跳過它們，回溯到上一個決策點?；厮莘ㄔ谏山饪臻g的任一結(jié)點時先判斷該結(jié)點是否可能包含問題的解，如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向祖先結(jié)點回溯（D）：這句話是正確的?；厮莘ㄍㄟ^在每個節(jié)點處進(jìn)行剪枝，避免了無效路徑的進(jìn)一步搜索，提高了算法的效率。8．下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略？（）A.遞歸函數(shù)B.剪枝函數(shù)C.隨機(jī)數(shù)函數(shù)D.搜索函數(shù)解答：B.剪枝函數(shù)講解：遞歸函數(shù)（A）：遞歸函數(shù)是實現(xiàn)回溯法的一種常見方法，用于遍歷解空間，但它本身并不是專門用于避免無效搜索的策略。剪枝函數(shù)（B）：剪枝函數(shù)是回溯法中的一種關(guān)鍵策略，用于避免無效搜索。當(dāng)算法確定當(dāng)前路徑不可能產(chǎn)生有效解時，剪枝函數(shù)會停止進(jìn)一步的搜索，回溯到上一步。這有效地減少了不必要的計算，提高了效率。隨機(jī)數(shù)函數(shù)（C）：隨機(jī)數(shù)函數(shù)通常用于生成隨機(jī)數(shù)，在某些隨機(jī)算法或概率算法中使用，但與回溯法的核心策略無關(guān)。搜索函數(shù)（D）：搜索函數(shù)泛指用于執(zhí)行搜索操作的函數(shù)，雖然回溯法中確實包含搜索功能，但“搜索函數(shù)”并不是特指回溯法中避免無效搜索的策略。9．以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為（）。A.分支界限算法B.概率算法C.貪心算法D.回溯法解答：D.回溯法講解：分支界限算法（A）：分支界限算法（BranchandBound）是一種用于解決優(yōu)化問題的算法，它通過分支來生成解的候選，并使用界限來排除不可能的解，但它不一定采用深度優(yōu)先的方式。概率算法（B）：概率算法（ProbabilisticAlgorithm）是一類算法，其行為是隨機(jī)的，通常用于在確定性算法難以處理的情況下提供近似解。它們不采用系統(tǒng)的深度優(yōu)先搜索。貪心算法（C）：貪心算法（GreedyAlgorithm）在每一步選擇中都做出當(dāng)前最優(yōu)的選擇，希望通過局部最優(yōu)解達(dá)到全局最優(yōu)解。它不采用深度優(yōu)先搜索策略?；厮莘ǎ―）：回溯法是一種系統(tǒng)地搜索解空間的算法，采用深度優(yōu)先搜索（DFS）策略，通過逐步深入到每一個可能的分支路徑，在需要時回溯到上一步，以尋找所有可能的解或滿足條件的解。二、編程題10．組合總和:給定一個數(shù)組candidates和一個目標(biāo)數(shù)target，找出candidates中所有可以使數(shù)字和為target的組合。數(shù)組中的數(shù)字可以無限次使用。解答：要解決組合總和問題，可以使用回溯法。下面是用Python編寫的代碼，找出所有可能的組合，使得這些組合中的數(shù)字和為目標(biāo)值target。defcombination_sum(candidates,target):defbacktrack(start,target,path):iftarget==0:result.append(path)returniftarget<0:returnforiinrange(start,len(candidates)):#選擇當(dāng)前數(shù)字并繼續(xù)搜索backtrack(i,target-candidates[i],path+[candidates[i]])result=[]candidates.sort()#排序可以加速一些剪枝操作backtrack(0,target,[])returnresult#示例candidates=[2,3,6,7]target=7print(combination_sum(candidates,target))講解：這個代碼的核心部分是backtrack函數(shù)，它通過遞歸的方式來構(gòu)建所有可能的組合：1. remain是剩余需要達(dá)到的目標(biāo)數(shù)。2. path是當(dāng)前構(gòu)建的組合。3. start是當(dāng)前選擇的候選數(shù)組的起始位置，以避免重復(fù)選擇。在每一次遞歸中：? 如果remain為0，表示當(dāng)前組合滿足要求，將其加入結(jié)果列表。? 如果remain小于0，表示當(dāng)前組合超出目標(biāo)數(shù)，停止遞歸。? 否則，繼續(xù)嘗試選擇當(dāng)前及之后的候選數(shù)，繼續(xù)構(gòu)建組合。11.分割回文串:給定一個字符串s，將s分割成一些子串，使每個子串都是回文串。返回s所有可能的分割方案。解答：defpartition(s):result=[]defis_palindrome(sub):returnsub==sub[::-1]defbacktrack(start,path):ifstart==len(s):result.append(list(path))returnforendinrange(start+1,len(s)+1):substring=s[start:end]ifis_palindrome(substring):path.append(substring)backtrack(end,path)path.pop()backtrack(0,[])returnresult#示例s="aab"print(partition(s))講解：partition函數(shù)：這是主函數(shù)，它接受一個字符串s，并返回所有可能的分割方案。is_palindrome函數(shù)：這是一個輔助函數(shù)，用來檢查一個字符串是否是回文。一個字符串如果等于其反轉(zhuǎn)字符串，那么它就是回文。backtrack函數(shù)：這是回溯函數(shù)，它通過遞歸的方式來構(gòu)建所有可能的分割方案。start表示當(dāng)前子串的起始位置。path是當(dāng)前構(gòu)建的分割方案。在每一次遞歸中：如果start達(dá)到字符串的長度，表示當(dāng)前分割方案已經(jīng)構(gòu)建完成，將其加入結(jié)果列表。否則，嘗試從start開始到字符串結(jié)尾的每一個位置，將當(dāng)前子串加入路徑，并繼續(xù)遞歸處理剩余部分。主函數(shù)調(diào)用backtrack，從字符串的起始位置開始構(gòu)建分割方案。12．小括號生成：給定一個數(shù)字n，生成所有可能的并且有效的括號組合。例如，給定n=3，一個可能的解集是["((()))","(()())","(())()","()(())","()()()"]。解答：這個問題可以通過回溯算法來解決。我們需要生成所有可能的括號組合并檢查其有效性?；厮菟惴梢杂行У貥?gòu)建所有可能的組合，并通過遞歸的方式確保生成的括號組合是有效的。以下是用Python實現(xiàn)求解這個問題的代碼：defgenerate_parenthesis(n):result=[]defbacktrack(current,open_count,close_count):iflen(current)==2*n:result.append(current)returnifopen_count<n:backtrack(current+'(',open_count+1,close_count)ifclose_count<open_count:backtrack(current+')',open_count,close_count+1)backtrack('',0,0)returnresult#示例n=3print(generate_parenthesis(n))講解：generate_parenthesis函數(shù)：這是主函數(shù)，它接受一個整數(shù)n，返回所有可能的并且有效的括號組合。backtrack函數(shù)：這是回溯函數(shù)，通過遞歸構(gòu)建所有可能的括號組合。current表示當(dāng)前構(gòu)建的括號組合字符串。open_count表示當(dāng)前使用的左括號數(shù)量。close_count表示當(dāng)前使用的右括號數(shù)量。在每一次遞歸中：如果current的長度達(dá)到2*n，表示當(dāng)前組合完成，將其加入結(jié)果列表。如果open_count小于n，可以繼續(xù)添加左括號。如果close_count小于open_count，可以繼續(xù)添加右括號。讓我們運行這個代碼，并輸出結(jié)果。代碼運行結(jié)果如下：對于n=3，所有可能的并且有效的括號組合是：['((()))','(()())','(())()','()(())','()()()']13.最近憨憨喜歡上了散步。憨憨住在南二區(qū)，他發(fā)現(xiàn)南二區(qū)有n個景點（從1到n進(jìn)行編號）很值得觀賞。憨憨不想錯過每個景點，但又不想在一次散步過程中經(jīng)過任意一個景點超過一次。憨憨的散步方案要求是從住所（設(shè)編號為0）出發(fā)，經(jīng)過每個景點有且僅有一次，最后回到住所。當(dāng)給定n個點的無權(quán)無向相連信息，滿足要求的方案總數(shù)是多少嗎？解答：這個問題實際上是一個經(jīng)典的旅行商問題的變種，具體來說是一個哈密頓回路問題。哈密頓回路問題是一個NP完全問題，通常在大規(guī)模情況下，計算會非常復(fù)雜。我們可以使用回溯算法來解決這個問題，通過遞歸構(gòu)建所有可能的路徑并檢查是否每個景點恰好經(jīng)過一次并回到起點。defcount_hamiltonian_cycles(n,edges):fromcollectionsimportdefaultdict#創(chuàng)建鄰接表graph=defaultdict(list)foru,vinedges:graph[u].append(v)graph[v].append(u)defbacktrack(current,visited,count):#如果訪問的節(jié)點數(shù)等于總節(jié)點數(shù)，并且當(dāng)前節(jié)點有一條邊指向起點iflen(visited)==n+1and0ingraph[current]:returncount+1forneighboringraph[current]:ifneighbornotinvisited:visited.add(neighbor)count=backtrack(neighbor,visited,count)visited.remove(neighbor)returncount#初始從0號點出發(fā)visited=set([0])count=0returnbacktrack(0,visited,count)#示例n=3edges=[(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)]result=count_hamiltonian_cycles(n,edges)result講解：鄰接表：使用defaultdict創(chuàng)建鄰接表以存儲無向圖的邊?；厮莺瘮?shù)backtrack：current表示當(dāng)前節(jié)點。visited是一個集合，保存已經(jīng)訪問的節(jié)點。count記錄滿足條件的回路數(shù)量。如果訪問的節(jié)點數(shù)等于總節(jié)點數(shù)n+1（包括起點），并且當(dāng)前節(jié)點有一條邊指向起點（0），則找到一個有效回路，count加1。否則，繼續(xù)嘗試訪問當(dāng)前節(jié)點的未訪問鄰居節(jié)點，遞歸地進(jìn)行回溯搜索。第五章分支限界法1.分支限界法通常用于解決哪類問題？（）A.只有一個解的問題B.需要找到所有可能解的問題C.尋找最優(yōu)解的問題D.解決遞歸問題解答：C.尋找最優(yōu)解的問題講解：只有一個解的問題（A）：分支限界法不是專門用來解決只有一個解的問題。它的目標(biāo)是找到最優(yōu)解，而不是單純地找到一個可行解。需要找到所有可能解的問題（B）：分支限界法不是用來尋找所有可能解的，而是用來在所有可能解中找到最優(yōu)解。回溯法更適合用于找到所有可能解的問題。尋找最優(yōu)解的問題（C）：這是正確的。分支限界法是一種用于解決優(yōu)化問題的算法，通過分支來生成解的候選，并使用界限來排除不可能的解，從而有效地找到最優(yōu)解。解決遞歸問題（D）：雖然分支限界法可以通過遞歸來實現(xiàn)，但它的主要目的是尋找最優(yōu)解，而不是專門用于解決遞歸問題。2.關(guān)于回溯法和分支限界法的區(qū)別，下面哪項描述是正確的？（）A.回溯法適用于解決組合問題，而分支限界法適用于解決優(yōu)化問題B.回溯法使用廣度優(yōu)先搜索，分支限界法使用深度優(yōu)先搜索C.兩者沒有本質(zhì)區(qū)別，只是應(yīng)用場景不同D.分支限界法通常不考慮約束條件，而回溯法則會解答：A.回溯法適用于解決組合問題，而分支限界法適用于解決優(yōu)化問題講解：回溯法適用于解決組合問題，而分支限界法適用于解決優(yōu)化問題（A）：這是正確的?；厮莘ㄍǔＳ糜趯ふ宜锌赡艿慕?，特別是在組合問題和排列問題中。而分支限界法主要用于優(yōu)化問題，通過分支和界限來有效地找到最優(yōu)解?；厮莘ㄊ褂脧V度優(yōu)先搜索，分支限界法使用深度優(yōu)先搜索（B）：這是不正確的。回溯法通常使用深度優(yōu)先搜索（DFS），而分支限界法可以使用廣度優(yōu)先搜索（BFS）或深度優(yōu)先搜索（DFS），具體取決于問題和實現(xiàn)方式。兩者沒有本質(zhì)區(qū)別，只是應(yīng)用場景不同（C）：這是不正確的。兩者有本質(zhì)區(qū)別?；厮莘ㄊ峭ㄟ^全面搜索所有可能的解來解決問題，而分支限界法通過分支和界限來優(yōu)化搜索過程，尋找最優(yōu)解。分支限界法通常不考慮約束條件，而回溯法則會（D）：這是不正確的。分支限界法和回溯法都考慮約束條件。分支限界法通過界限來排除不滿足約束條件的解，回溯法通過在搜索過程中進(jìn)行剪枝來處理約束條件。3.分支限界法在求解問題時的主要特點是什么？（）A.總是遵循深度優(yōu)先搜索策略B.主要用于解決組合問題C.側(cè)重于減少搜索空間以找到最優(yōu)解。D.通常用于處理具有多個解的問題解答：C.側(cè)重于減少搜索空間以找到最優(yōu)解。講解：總是遵循深度優(yōu)先搜索策略（A）：分支限界法不一定總是使用深度優(yōu)先搜索策略，它可以使用深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜索（BFS），具體取決于問題的性質(zhì)和實現(xiàn)方式。主要用于解決組合問題（B）：分支限界法主要用于解決優(yōu)化問題，而不是簡單的組合問題?；厮莘ǜＳ糜诮鉀Q組合問題。側(cè)重于減少搜索空間以找到最優(yōu)解（C）：這是正確的。分支限界法的主要特點是通過分支和界限來有效地減少搜索空間，從而找到問題的最優(yōu)解。它通過排除不可能的解來優(yōu)化搜索過程。通常用于處理具有多個解的問題（D）：雖然分支限界法可以處理具有多個解的問題，但它的主要目標(biāo)是找到最優(yōu)解，而不是簡單地處理多個解。4.FIFO是（）的一種搜索方式。A.分支限界B.動態(tài)規(guī)劃C.貪心算法D.回溯法解答：A.分支限界講解：分支限界（A）：FIFO（First-In-First-Out）是一種搜索方式，常用于分支限界法中的廣度優(yōu)先搜索（BFS）。在這種方法中，節(jié)點按照進(jìn)入的順序進(jìn)行處理，以確保搜索是逐層進(jìn)行的。這種方式有助于有效地剪枝和找到最優(yōu)解。動態(tài)規(guī)劃（B）：動態(tài)規(guī)劃主要通過將問題分解為子問題并保存子問題的解來避免重復(fù)計算，并不涉及FIFO這種搜索策略。貪心算法（C）：貪心算法在每一步選擇中都做出當(dāng)前最優(yōu)的選擇，它通常不使用FIFO這種策略，而是基于當(dāng)前局部信息做出選擇。回溯法（D）：回溯法通常使用深度優(yōu)先搜索（DFS）策略，通過遞歸或棧來實現(xiàn)，而不是使用FIFO策略。5.在分支限界法中，通常采用哪種搜索策略來找到最優(yōu)解？（）A.僅深度優(yōu)先搜索。B.僅廣度優(yōu)先搜索。C.根據(jù)問題特性選擇深度優(yōu)先或廣度優(yōu)先搜索。D.隨機(jī)搜索。解答：C.根據(jù)問題特性選擇深度優(yōu)先或廣度優(yōu)先搜索。講解：僅深度優(yōu)先搜索（A）：雖然深度優(yōu)先搜索（DFS）在某些情況下可能是有效的，但它并不是分支限界法唯一使用的搜索策略。僅廣度優(yōu)先搜索（B）：廣度優(yōu)先搜索（BFS）在某些情況下也可能是有效的，但同樣，它并不是分支限界法唯一使用的搜索策略。根據(jù)問題特性選擇深度優(yōu)先或廣度優(yōu)先搜索（C）：這是正確的。分支限界法可以根據(jù)具體問題的特性選擇適合的搜索策略，既可以使用深度優(yōu)先搜索，也可以使用廣度優(yōu)先搜索，甚至可以結(jié)合兩者。選擇哪種搜索策略取決于問題的性質(zhì)和如何能夠更高效地找到最優(yōu)解。隨機(jī)搜索（D）：隨機(jī)搜索不是分支限界法的策略。分支限界法是一個系統(tǒng)性的搜索算法，旨在通過有效的分支和剪枝來找到最優(yōu)解，而不是隨機(jī)搜索。6.優(yōu)先級隊列式分支限界法選取擴(kuò)展結(jié)點的原則是（）。A.先進(jìn)先出B.后進(jìn)先出C.隨機(jī)D.結(jié)點優(yōu)先級解答：D.結(jié)點優(yōu)先級講解：先進(jìn)先出（A）：這是廣度優(yōu)先搜索（BFS）使用的原則，不適用于優(yōu)先級隊列式分支限界法。后進(jìn)先出（B）：這是深度優(yōu)先搜索（DFS）使用的原則，不適用于優(yōu)先級隊列式分支限界法。隨機(jī)（C）：隨機(jī)選擇結(jié)點不符合優(yōu)先級隊列式分支限界法的原則。結(jié)點優(yōu)先級（D）：這是正確的。優(yōu)先級隊列式分支限界法使用結(jié)點的優(yōu)先級來決定擴(kuò)展哪個結(jié)點。優(yōu)先級通?；诮Y(jié)點的估值函數(shù)或界限函數(shù)，以確保優(yōu)先擴(kuò)展可能最優(yōu)解的結(jié)點。7.作業(yè)調(diào)度問題：給定一組作業(yè)，其中每個作業(yè)都有一個截止日期和利潤。只有一個工作人員，工作人員只能在任何給定的時間工作一個作業(yè)。如果工作完成，會得到利潤，否則不會得到任何利潤。目標(biāo)是最大化利潤。解答：分支限界法是一種用于解決組合優(yōu)化問題的算法，通過系統(tǒng)地搜索和剪枝來減少不必要的計算。對于作業(yè)調(diào)度問題，可以使用分支限界法來找到最大化利潤的作業(yè)安排。以下是使用分支限界法解決作業(yè)調(diào)度問題的Python實現(xiàn)代碼：fromheapqimportheappop,heappushclassJob:def__init__(self,job_id,deadline,profit):self.job_id=job_idself.deadline=deadlinefit=profitclassNode:def__init__(self,level,profit,bound,deadline_slot):self.level=levelfit=profitself.bound=boundself.deadline_slot=deadline_slotdef__lt__(self,other):returnself.bound>other.bound#Max-Heapbasedonbounddefcalculate_bound(node,n,jobs):ifnode.level>=n:return0profit_bound=fitj=node.level+1total_deadline=len(node.deadline_slot)whilej<nandnode.deadline_slot[jobs[j].deadline-1]isNone:profit_bound+=jobs[j].profitj+=1returnprofit_bounddefjob_scheduling_branch_bound(jobs):jobs.sort(key=lambdax:fit,reverse=True)n=len(jobs)max_deadline=max(job.deadlineforjobinjobs)priority_queue=[]root=Node(-1,0,0,[None]*max_deadline)root.bound=calculate_bound(root,n,jobs)heappush(priority_queue,root)max_profit=0best_schedule=[]whilepriority_queue:node=heappop(priority_queue)ifnode.bound>max_profit:next_level=node.level+1ifnext_level<n:#Includethenextjobnew_schedule=node.deadline_slot[:]profit_with_job=fitforslotinrange(min(jobs[next_level].deadline,max_deadline)-1,-1,-1):ifnew_schedule[slot]isNone:new_schedule[slot]=jobs[next_level]profit_with_job+=jobs[next_level].profitbreakifprofit_with_job>max_profit:max_profit=profit_with_jobbest_schedule=new_scheduleinclude_job_node=Node(next_level,profit_with_job,0,new_schedule)include_job_node.bound=calculate_bound(include_job_node,n,jobs)ifinclude_job_node.bound>max_profit:heappush(priority_queue,include_job_node)#Excludethenextjobexclude_job_node=Node(next_level,fit,0,node.deadline_slot)exclude_job_node.bound=calculate_bound(exclude_job_node,n,jobs)ifexclude_job_node.bound>max_profit:heappush(priority_queue,exclude_job_node)returnmax_profit,[job.job_idifjobelseNoneforjobinbest_schedule]#示例jobs=[Job(1,4,20),Job(2,1,10),Job(3,2,40),Job(4,1,30)]max_profit,scheduled_jobs_ids=job_scheduling_branch_bound(jobs)max_profit,scheduled_jobs_ids結(jié)果：最大利潤為：90安排的作業(yè)為[4,3,None,1]，表示：第一個時間槽安排了Job4（利潤30）。第二個時間槽安排了Job3（利潤40）。第三個時間槽為空。第四個時間槽安排了Job1（利潤20）。講解：Job類：用于表示每個作業(yè)，包括作業(yè)ID、截止日期和利潤。Node類：用于表示分支限界法中的節(jié)點，包括層次、當(dāng)前利潤、上界和截止日期槽。__lt__方法用于在優(yōu)先隊列中比較節(jié)點，基于上界（bound）進(jìn)行最大堆排序。calculate_bound函數(shù)：計算節(jié)點的上界（bound），用于評估節(jié)點的潛在利潤。計算當(dāng)前節(jié)點的潛在利潤上界，通過累加可以在剩余時間槽中安排的作業(yè)利潤。job_scheduling_branch_bound函數(shù)：實現(xiàn)分支限界法解決作業(yè)調(diào)度問題。按利潤降序排序作業(yè)。初始化優(yōu)先隊列并將根節(jié)點（初始狀態(tài)）加入隊列。使用優(yōu)先隊列進(jìn)行廣度優(yōu)先搜索，依次處理每個節(jié)點。對于每個節(jié)點，嘗試包括或排除下一個作業(yè)，并計算新的節(jié)點狀態(tài)和上界。如果新的節(jié)點上界大于當(dāng)前最大利潤，將其加入優(yōu)先隊列。更新最大利潤和最佳安排。第六章動態(tài)規(guī)劃1.B2.D3.A4.最優(yōu)子結(jié)構(gòu)；無后效性；重疊子問題。5. 略6. 多加入一重for循環(huán)，遍歷所有可能的轉(zhuǎn)移位置（i-1至i-R）。代碼如下：#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=2e5+10;lldp[N],d[N];lln,k;intmain(){ cin>>n>>k;//n個臺階，一次最高k步 for(inti=1;i<=n;i++)cin>>d[i]; dp[0]=0; for(inti=2;i<=n;i++){ dp[i]=1e18;//初始默認(rèn)無窮大 for(intj=1;j<=k&&j<=i;j++){ dp[i]=min(dp[i],dp[i-j]+abs(d[i]-d[i-j])); //第i個臺階的前k個臺階到第i個臺階的消耗是不是更少，取開銷小的 } } cout<<dp[n]; return0;}7.可以。8.修改為相等的時候也可以進(jìn)行轉(zhuǎn)移。借助二分查找可以實現(xiàn)。9.用dp[i]記錄物品總價值為i的最小重量即可。參考代碼如下：#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=2e5+10;typedefpair<int,int>pii;intn,sum;llw[N],v[N];lldp[N];/*這個你觀察就發(fā)現(xiàn)其實最大的價值沒超過1e5那么你可以改變你的dp方程來求解設(shè)dp[i]表示獲得價值i的最小物品體積即可洛谷Knapsack2*/intmain(){scanf("%d%d",&n,&sum);for(inti=1;i<=n;i++){scanf("%d%d",&w[i],&v[i]);}memset(dp,0x3f,sizeof(dp));dp[0]=0;for(inti=1;i<=n;i++){for(intj=1e5;j>=v[i];j--){dp[j]=min(dp[j],dp[j-v[i]]+w[i]);}}for(inti=1e5;i>=0;i--){if(dp[i]<=sum){printf("%d\n",i);break;}}return0;}10. （1）遍歷添加的數(shù)字時，不超過P即可。（2）先求出n以內(nèi)所有的質(zhì)數(shù)，轉(zhuǎn)移時，只用這些質(zhì)數(shù)進(jìn)行轉(zhuǎn)移。11. 可以。復(fù)雜度不變。12. 復(fù)雜度不變。參考代碼如下:#include<iostream>#include<cstring>#include<algorithm>#inclu