蠻力法等求解背包問(wèn)題

1、算法綜合實(shí)驗(yàn)報(bào)告學(xué) 號(hào)： 姓 名： 一、實(shí)驗(yàn)內(nèi)容：分別用蠻力、動(dòng)態(tài)規(guī)劃、貪心及分支限界法實(shí)現(xiàn)對(duì)TSP問(wèn)題或者0-1背包問(wèn)題的求解，并至少用兩個(gè)測(cè)試用例對(duì)所完成的代碼進(jìn)行正確性及效率關(guān)系上的驗(yàn)證。二、程序設(shè)計(jì)的基本思想、原理和算法描述：1、 蠻力法(1) 數(shù)據(jù)結(jié)構(gòu):使用一維數(shù)組存儲(chǔ)物品的價(jià)值和重量還有下標(biāo)。 (2) 函數(shù)組成除主函數(shù)外還有一個(gè)subset（）函數(shù)，在此函數(shù)中列出所有的子集列出子集的同時(shí)求解最大價(jià)值，并且物品總重量要小于背包總?cè)萘俊?3) 輸入/輸出設(shè)計(jì)首先通過(guò)鍵盤輸入物品的總重量，再輸入背包總?cè)萘?，依次輸入每個(gè)物品的重量，對(duì)應(yīng)輸入相應(yīng)重量的價(jià)值，循環(huán)直至輸入所有物品的重量和價(jià)值。

2、最后輸出物品的最大價(jià)值。本程序通過(guò)鍵盤進(jìn)行輸入、屏幕進(jìn)行輸出。（根據(jù)實(shí)際程序情況，還可以選擇隨機(jī)產(chǎn)生輸入數(shù)據(jù)、將輸出數(shù)據(jù)輸出到文件等其它方式）(4) 符號(hào)名說(shuō)明w1001為物品重量的集合，v1001為物品價(jià)值的集合，n為物品數(shù)量，m為背包總?cè)萘?x1001用來(lái)存儲(chǔ)物品是否裝入背包，0為不裝入，1為裝入。用a1001來(lái)存儲(chǔ)下標(biāo)，用下標(biāo)找出所有子集。(5) 算法描述采用增量構(gòu)造的方法來(lái)構(gòu)造出物品的所有子集，對(duì)物品的下標(biāo)應(yīng)用此方法進(jìn)行構(gòu)造，下標(biāo)與物品相對(duì)應(yīng)，選出子集時(shí)物品的重量加之前重量小于背包總重量時(shí)將價(jià)值加上去，最后選出能裝入背包的物品的最大值。2、 動(dòng)態(tài)規(guī)劃法(1)數(shù)據(jù)結(jié)構(gòu)：使用一維數(shù)組存儲(chǔ)各

3、個(gè)物品價(jià)值，重量，使用一個(gè)二維數(shù)組存儲(chǔ)動(dòng)態(tài)規(guī)劃的整體求解的表，并以背包容量為最大列號(hào)，物品個(gè)數(shù)為最大行號(hào)。(2)函數(shù)組成：除主函數(shù)外由兩個(gè)函數(shù)組成，一個(gè)是求解兩個(gè)數(shù)中的大的一個(gè)的函數(shù)，另一個(gè)則是進(jìn)行動(dòng)態(tài)規(guī)劃求解的函數(shù)，在使用動(dòng)態(tài)規(guī)劃方法具體求解時(shí)調(diào)用求最大值函數(shù)，在主程序之中調(diào)用動(dòng)態(tài)規(guī)劃函數(shù)。(3)輸入/輸出設(shè)計(jì)： 首先通過(guò)鍵盤輸入物品的總重量，再輸入背包總?cè)萘浚来屋斎朊總€(gè)物品的重量，對(duì)應(yīng)輸入相應(yīng)重量的價(jià)值，循環(huán)直至輸入所有物品的重量和價(jià)值。輸出物品的最大價(jià)值。本程序通過(guò)鍵盤進(jìn)行輸入、屏幕進(jìn)行輸出。（根據(jù)實(shí)際程序情況，還可以選擇隨機(jī)產(chǎn)生輸入數(shù)據(jù)、將輸出數(shù)據(jù)輸出到文件等其它方式）(4)符號(hào)名說(shuō)

4、明： w1001為物品重量的集合，v1001為物品價(jià)值的集合，n為物品數(shù)量，m為背包總?cè)萘?x1001用來(lái)存儲(chǔ)物品是否裝入背包，0為不裝入，1為裝入。V10011001用來(lái)存儲(chǔ)動(dòng)態(tài)規(guī)劃具體求解過(guò)程,Vnm為最終結(jié)果最大價(jià)值。(5)算法描述： 1.背包容量不足以裝入物品i，則裝入前i個(gè)物品得到的最大價(jià)值和裝入前i-1個(gè)物品得到的最大價(jià)值是相同的，則xi=0，背包不增加價(jià)值。 2.背包容量可以裝入物品i，如果把第i個(gè)物品裝入背包，則背包中物品的價(jià)值等于前i-1個(gè)物品裝入容量為j-wi的背包中的價(jià)值加上第i個(gè)物品的價(jià)值；如果第i個(gè)物品沒(méi)有裝入背包，則背包中物品的價(jià)值等于把前i-1個(gè)物品裝入容量為j的

5、背包中所取得的價(jià)值。取二者中價(jià)值較大者作為把前i個(gè)物品裝入容量為j的背包中的最優(yōu)解。表示在前個(gè)物品中能夠裝入容量為的背包中的物品的最大值，則可以得到如下動(dòng)態(tài)函數(shù)：3、 貪心法(1) 數(shù)據(jù)結(jié)構(gòu)：定義多個(gè)一維數(shù)組存儲(chǔ)數(shù)據(jù)進(jìn)行貪心選擇。(2)函數(shù)組成 ：編寫了一個(gè)選擇排序函數(shù)，一個(gè)判斷是否能裝入包中的函數(shù)，一個(gè)主函數(shù)，在主函數(shù)中調(diào)用判斷函數(shù)，在判斷函數(shù)初始調(diào)用排序函數(shù)將單位價(jià)值重量從大到小進(jìn)行排序。(3)輸入/輸出設(shè)計(jì)：首先通過(guò)鍵盤輸入物品的總重量，再輸入背包總?cè)萘?，依次輸入每個(gè)物品的重量，對(duì)應(yīng)輸入相應(yīng)重量的價(jià)值，循環(huán)直至輸入所有物品的重量和價(jià)值。先輸出放入背包中的物品序號(hào)，在輸出總價(jià)值，最后輸出背

6、包總?cè)萘?。本程序通過(guò)鍵盤進(jìn)行輸入、屏幕進(jìn)行輸出。（根據(jù)實(shí)際程序情況，還可以選擇隨機(jī)產(chǎn)生輸入數(shù)據(jù)、將輸出數(shù)據(jù)輸出到文件等其它方式）(4)符號(hào)名說(shuō)明: w1001為物品重量的集合，v1001為物品價(jià)值的集合，a1001為單位物品價(jià)值集合,n為物品數(shù)量，m為背包總?cè)萘?x1001用來(lái)存儲(chǔ)物品是否裝入背包，0為不裝入，1為裝入。(5)算法描述：制定貪心策略，求出單位物品價(jià)值并從大到小進(jìn)行排序，依照排序結(jié)果從大到小放入，知道物品重量大于背包剩余容量為止，但是求出的并不是最優(yōu)解，貪心法無(wú)法求出0/1背包的最優(yōu)解，只能求出背包問(wèn)題的最優(yōu)解。4、 分支限界法(1) 數(shù)據(jù)結(jié)構(gòu)定義一個(gè)優(yōu)先隊(duì)列存儲(chǔ)分支限界所使用的

7、樹的節(jié)點(diǎn)，使用一維數(shù)組存儲(chǔ)物品的重量和價(jià)值。(2) 函數(shù)組成一個(gè)構(gòu)造函數(shù)，申請(qǐng)動(dòng)態(tài)數(shù)組構(gòu)造樹，一個(gè)析構(gòu)函數(shù)，刪掉動(dòng)態(tài)申請(qǐng)的數(shù)組，一個(gè)計(jì)算上界的函數(shù)，一個(gè)生成新節(jié)點(diǎn)的函數(shù)，一個(gè)將節(jié)點(diǎn)加入優(yōu)先隊(duì)列的函數(shù)，一個(gè)取上界最大節(jié)點(diǎn)的函數(shù)，一個(gè)背包問(wèn)題求解的函數(shù)，一個(gè)顯示函數(shù)，在主函數(shù)中調(diào)用函數(shù)求解。本程序還使用了類和結(jié)構(gòu)體。(3) 輸入/輸出設(shè)計(jì)通過(guò)鍵盤先輸入背包總?cè)萘?，再輸入物品總?shù)，依次輸入每個(gè)物品的重量，依次輸入每個(gè)物品的價(jià)值。輸出最大價(jià)值以及每個(gè)物品是否裝入背包中本程序通過(guò)鍵盤進(jìn)行輸入、屏幕進(jìn)行輸出。（根據(jù)實(shí)際程序情況，還可以選擇隨機(jī)產(chǎn)生輸入數(shù)據(jù)、將輸出數(shù)據(jù)輸出到文件等其它方式）(4) 符號(hào)名說(shuō)明

8、Cw為當(dāng)前背包裝載量，cv為當(dāng)前背包價(jià)值，ub節(jié)點(diǎn)的上界值，c為背包的容量，n為物品數(shù)量，x記錄物品是否放入背包，0為不放入，1為放入，w為存放物品重量的數(shù)組，v為存放物品價(jià)值的數(shù)組。(5)算法描述 給定n 種物品和一個(gè)容量為C 的背包, 物品i 的重量是Wi, 其價(jià)值為Vi , 0/ 1 背包問(wèn)題是如何選擇裝入背包的物品(物品不可分割) , 使得裝入背包中物品的總價(jià)值最大，一般情況下, 解空間樹中第i 層的每個(gè)結(jié)點(diǎn), 都代表了對(duì)物品1 i 做出的某種特定選擇, 這個(gè)特定選擇由從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑唯一確定: 左分支表示裝入物品, 右分支表示不裝入物品。對(duì)于第i 層的某個(gè)結(jié)點(diǎn), 假設(shè)背包中已裝

9、入物品的重量是w, 獲得的價(jià)值是v, 計(jì)算該結(jié)點(diǎn)的目標(biāo)函數(shù)上界的一個(gè)簡(jiǎn)單方法是把已經(jīng)裝入背包中的物品取得的價(jià)值v, 加上背包剩余容量W - w 與剩下物品的最大單位重量?jī)r(jià)值vi + 1/ wi + 1的積,于是,得到限界函數(shù):u b = v + ( W - w) × ( vi + 1/ wi + 1 )根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界 down , up，然后, 按照廣度優(yōu)先策略遍歷問(wèn)題的空間樹。三、源程序及注釋：1、蠻力法#include<cstdio>#include<iostream>using namespace std;int x1001=0;int w

10、1001,v1001;int maxValue=0;int subset(int n,int m,int* A,int cur)/n是數(shù)組長(zhǎng)度,A為待求子集數(shù)組，cur用于遞歸記錄int weight=0;int value=0; for(int i=0; i<cur; i+) /這個(gè)用于輸出子集 /printf("%d ",Ai);if(weight+wAi<m)xAi=1;weight=weight+wAi;value=value+vAi; if(maxValue<value)maxValue=value; /printf("n")

11、; int s = cur? Acur-1+1 : 0; /判斷cur是否是0，避免越界,是0的話就取s=0，非零的話s=Acur-1 for( i=s; i<n; i+) /遞歸構(gòu)造子集 Acur = i; subset(n,m,A,cur+1); return maxValue;int main()int n,m;int a1000;cout<<"請(qǐng)輸入物品總數(shù)量:"<<endl;cin>>n;/輸入物品總數(shù)量cout<<"請(qǐng)輸入背包總?cè)萘?"<<endl;cin>>m;/

12、輸入背包總?cè)萘縞out<<"請(qǐng)依次輸入物品的重量和價(jià)值"<<endl;for(int i=0;i<n;i+)cin>>wi;cin>>vi;ai=i; /記錄下標(biāo) cout<<"總價(jià)值為:"<<subset(n,m,a,0)<<endl;return 0;2、動(dòng)態(tài)規(guī)劃法#include<iostream>#include<cmath>using namespace std;int V10021002;int w1001,v1001;int m

13、ax(int xx,int yy) /判斷兩個(gè)數(shù)誰(shuí)大，返回大的那個(gè)值if(xx>=yy)return xx;else return yy;int KnapSack(int *w,int *v,int n,int m)int x1001=0;int i,j;for(i=0;i<=n;i+) /初始化第0列為0Vi0=0;for(j=0;j<=m;j+) /初始化第0行為0V0j=0;for(i=1;i<=n;i+) /在背包能放下的情況下，如果放入后比i-1個(gè)物品裝入后價(jià)值還小則不放入for(j=1;j<=m;j+) /計(jì)算第i行，進(jìn)行第i次迭代if(j<wi

14、)Vij=Vi-1j;elseVij=max(Vi-1j,(Vi-1j-wi+vi);for(j=m,i=n;i>0;i-) /求裝入背包的物品if(Vij>Vi-1j)xi=1;j=j-wi;elsexi=0;return Vnm; /返回背包取得的最大價(jià)值int main()int n,m;/n為物品數(shù)量，m為背包容量int i;int maxValue;cout<<"請(qǐng)輸入物品數(shù)量"<<endl;cin>>n;cout<<"請(qǐng)輸入背包容量"<<endl;cin>>m

15、;cout<<"請(qǐng)依次輸入每個(gè)物品的重量和價(jià)值(注：重量在前，價(jià)值在后)"<<endl;for(i=1;i<=n;i+)cin>>wi;cin>>vi;maxValue=KnapSack(w,v,n,m);cout<<"最大價(jià)值是："<<maxValue<<endl;return 0;3、貪心法：#include<iostream>#include<iomanip>using namespace std;int n,m;int w1001,v

16、1001;double a1001;int maxValue=0;int b1001;/存儲(chǔ)物品序號(hào)int x1001=0; /0為不放入背包，1為放入背包void Sort(int n,double *a,int *w,int *v,int *b)/排序函數(shù)for(int e=0;e<n;e+) /將單位重量?jī)r(jià)值從大到小排序for(int t=n-1;t>e;t-)if(ae<at)int temp=ae;int q=we;int s=ve;int p=be;ae=at;at=temp;we=wt;wt=q;ve=vt;vt=s;be=bt;bt=p;int KnapSac

17、k(int n,int m,int *w,int *v,int *x)/ 判斷是否能裝入背包Sort(n,a,w,v,b);for(int j=0;wj<m;j+) xj=1;maxValue=maxValue+vj;m=m-wj; return maxValue;int main()cin>>n; /輸入物品總個(gè)數(shù)cin>>m; /輸入背包總?cè)萘縤nt weight=0;for(int i=0;i<n;i+)cin>>wi; /輸入物品重量cin>>vi; /輸入物品價(jià)值ai=vi/wi; /求得單位重量?jī)r(jià)值bi=i+1; /記錄物

18、品序號(hào) maxValue=KnapSack(n,m,w,v,x);for(int j=0;j<n;j+)if(xj=1)cout<<"第"<<bj<<"個(gè)物品裝入"<<" "weight=weight+wj;cout<<endl;cout<<maxValue<<endl; /輸出能裝入的總價(jià)值cout<<"總重量為："<<weight<<endl;return 0;5、 分支限界法#incl

19、ude<iostream>#include<cstdio>using namespace std;int *x;struct node /結(jié)點(diǎn)表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu) node *parent, /父結(jié)點(diǎn)指針 *next; /后繼結(jié)點(diǎn)指針 int level, /結(jié)點(diǎn)的層 bag, /節(jié)點(diǎn)的解 cw, /當(dāng)前背包裝載量 cv; /當(dāng)前背包價(jià)值 float ub; /結(jié)點(diǎn)的上界值;class Knapprivate:struct node *front, /隊(duì)列隊(duì)首 *bestp,*first; /解結(jié)點(diǎn)、根結(jié)點(diǎn)int *v,*w,n,c,*M;/背包價(jià)值、重量、物品數(shù)、背包容量、

20、記錄大小順序關(guān)系long lbestp;/背包容量最優(yōu)解 public:void Sort();Knap(int *pp,int *ww,int cc,int nn);Knap();float Bound(int i,int cw,int cv); /計(jì)算上界node *nnoder(node *pa,int ba,float uub);/生成一個(gè)結(jié)點(diǎn) ba=1生成左節(jié)點(diǎn) ba=0生成右節(jié)點(diǎn)void addnode(node *nod); /將結(jié)點(diǎn)添加到隊(duì)列中void deletenode(node *nod); /將結(jié)點(diǎn)隊(duì)列中刪除struct node *nextnode(); /取下一個(gè)節(jié)

21、點(diǎn)void display(); /輸出結(jié)果void solvebag(); /背包問(wèn)題求解;Knap:Knap(int *pp,int *ww,int cc,int nn) /構(gòu)造函數(shù)int i;n=nn;c=cc;v=new intn; /動(dòng)態(tài)申請(qǐng)數(shù)組w=new intn;M=new intn;for(i=0;i<n;i+)vi=ppi;wi=wwi;Mi=i;front=new node1;front->next=NULL;lbestp=0;bestp=new node1;bestp=NULL;Sort();Knap:Knap() /析構(gòu)函數(shù) delete first;del

22、ete front;delete bestp;delete v;delete w;float Knap:Bound(int i,int cw,int cv) / 計(jì)算上界int left=c-cw; float b=(float)cv; while (i<n&&wi<=left)left-=wi;b+=vi;i+;if (i<n) b+=1.0*vi/wi*left;return b;node * Knap:nnoder(struct node *pa,int ba,float uub) /生成一個(gè)新結(jié)點(diǎn)node * nodell=new(node);node

23、ll->parent=pa;nodell->next=NULL;nodell->level=(pa->level)+1;nodell->bag=ba;nodell->ub=uub;if(ba=1)nodell->cw=pa->cw+wpa->level;nodell->cv=pa->cv+vpa->level ;else nodell->cw=pa->cw;nodell->cv=pa->cv;return(nodell);void Knap:addnode(node *no) /將結(jié)點(diǎn)加入優(yōu)先隊(duì)列n

24、ode *p=front->next,*next1=front;float ub=no->ub;while(p!=NULL)if(p->ub<ub)no->next=p;next1->next=no;break;next1=p;p=p->next;if(p=NULL)next1->next=no;node *Knap:nextnode() /取上限最大結(jié)點(diǎn) node *p=front->next;front->next=p->next;return(p);void Knap:Sort()int i,j,k,kkl;float m

25、inl; for(i=1;i<n;i+) minl=1.0*vi/wi;k=0;for(j=1;j<=n-i;j+) if(minl<1.0*vj/wj)minl=1.0*vj/wj;swap(vk,vj);swap(wk,wj);swap(Mk,Mj); k=j; void Knap:display() /顯示函數(shù)int i;cout<<"最大價(jià)值是:"<<lbestp<<endl;for(i=n;i>=1;i-) xMi-1=bestp->bag;bestp=bestp->parent;cout&l

26、t;<"物品狀態(tài)為(0為不裝入，1為裝入):"<<endl;for(i=1;i<=n;i+)cout<<"x("<<i<<")="<<xi-1<<endl;void Knap:solvebag() /背包問(wèn)題求解int i;float ubb;node *aa;first=new node1; /根結(jié)點(diǎn)first->parent=NULL;first->next=NULL;first->level=0;first->cw=0;f

27、irst->cv=0;first->bag=0;ubb=Bound(0,0,0);first->ub=ubb;front->next=first;while(front->next!=NULL)aa=nextnode();i=aa->level;if(i=n-1) if(aa->cw+wi<=c&&(long)(aa->cv+vi)>lbestp)lbestp=aa->cv+vi;bestp=nnoder(aa,1,(float)lbestp);if(long)(aa->cv)>lbestp) lbe

28、stp=aa->cv;bestp=nnoder(aa,0,(float)lbestp);if(i<n-1) if(aa->cw+wi<=c&&Bound(i+1,aa->cw+wi,aa->cv+vi)>(float)lbestp)ubb=Bound(i,aa->cw+wi,aa->cv+vi);addnode(nnoder(aa,1,ubb);ubb=ubb=Bound(i,aa->cw,aa->cv);if(ubb>lbestp) addnode(nnoder(aa,0,ubb);display();v

29、oid main()int c,n;int i=0;int *v;int *w;cout<<"請(qǐng)輸入背包容量:"<<endl;cin>>c;cout<<"請(qǐng)輸入物品數(shù):"<<endl;cin>>n; x=new intn;v=new intn;w=new intn;cout<<"請(qǐng)輸入"<<n<<"個(gè)物品的重量:"<<endl;for(i=0;i<n;i+)cin>>wi; co

30、ut<<"請(qǐng)輸入"<<n<<"個(gè)物品價(jià)值:"<<endl;for(i=0;i<n;i+)cin>>vi;x=new intn;Knap knbag(v,w,c,n);knbag.solvebag();return;四、運(yùn)行輸出結(jié)果：1、 蠻力法測(cè)試1：測(cè)試2：2、動(dòng)態(tài)規(guī)劃法測(cè)試1：測(cè)試2：3、貪心法：測(cè)試1：測(cè)試2：4、分支限界法測(cè)試1：測(cè)試2：五、調(diào)試和運(yùn)行程序過(guò)程中產(chǎn)生的問(wèn)題及采取的措施：1、在傳數(shù)組時(shí)一開始就是在報(bào)錯(cuò)，最后我使用了全局變量定義數(shù)組，使用了指針直接傳指針，eg:max（

31、a,b），a,b,是數(shù)組，定義函數(shù)時(shí)void Sort(int n,double *a,int *w,int *v,int *b)才可以進(jìn)行。錯(cuò)誤如下圖：2、寫動(dòng)態(tài)規(guī)劃法程序時(shí)，參照書上思想進(jìn)行編程結(jié)果總是錯(cuò)誤，因?yàn)槲叶xVn+1m+1，所以在main中傳入重量和價(jià)值時(shí)應(yīng)該從i=1開始到i=n為止才是正確的。3、在寫蠻力法求解0/1背包問(wèn)題的時(shí)候一開始不知道怎么列出所有子集，后來(lái)詢問(wèn)同學(xué)知道了增量構(gòu)造的方法才解出的。 4、蠻力法求解時(shí)解總是不對(duì)后來(lái)我發(fā)現(xiàn)我將weight和value設(shè)為全局變量后只賦了一次0，必須在蠻力法求解的函數(shù)之前清零，否則重量與價(jià)值都在不斷累加。 5、在寫分支限界法時(shí)一開

32、始覺(jué)得算法的思想很簡(jiǎn)單，就是以廣度優(yōu)先來(lái)遍歷一棵樹，通過(guò)限界函數(shù)不斷剪枝，并以值的大小用優(yōu)先隊(duì)列進(jìn)行存儲(chǔ)，但是實(shí)際實(shí)踐時(shí)就出現(xiàn)了很多問(wèn)題，最后是通過(guò)詢問(wèn)同學(xué)與同學(xué)一起討論加上上網(wǎng)搜集一些資料才解出的。六、對(duì)算法的程序的討論、分析，改進(jìn)設(shè)想，其它經(jīng)驗(yàn)教訓(xùn)：1、貪心法求解01背包問(wèn)題無(wú)法得到最優(yōu)解，蠻力法，動(dòng)態(tài)規(guī)劃法，分支限界法都能求解出最優(yōu)解。2、使用分支限界法的時(shí)候遇到了許多的問(wèn)題，此方法要用對(duì)或者優(yōu)先隊(duì)列來(lái)存儲(chǔ)節(jié)點(diǎn)，但是我本身對(duì)堆和隊(duì)列的掌握就不是特別的好，所以進(jìn)行了復(fù)習(xí)，重新看了隊(duì)列的使用最終使用優(yōu)先隊(duì)列實(shí)現(xiàn)了此代碼。3、蠻力法求解時(shí)時(shí)間復(fù)雜度為O(2n),動(dòng)態(tài)規(guī)劃法的時(shí)間復(fù)雜度為O(n*

33、c)，貪心法因?yàn)闊o(wú)法求解出最優(yōu)解時(shí)間復(fù)雜度無(wú)意義，分支限界法無(wú)法確定具體時(shí)間復(fù)雜度，只能知道最好和最壞的。4、貪心法求解背包問(wèn)題可以取得最優(yōu)解。5、對(duì)于分支限界法既可以用堆也可以用隊(duì)列，而我在本次實(shí)驗(yàn)中使用了隊(duì)列，下去后我會(huì)找機(jī)會(huì)使用堆來(lái)再編寫此程序。6、這是在使用動(dòng)態(tài)規(guī)劃時(shí)一開始輸入i=0,i<n時(shí)的結(jié)果，但是明明應(yīng)該是錯(cuò)的因?yàn)槲业臄?shù)組是Vn+1Wn+1可是結(jié)果卻是對(duì)的這一點(diǎn)令我感覺(jué)非常的奇怪，目前還不知道具體的原因，會(huì)進(jìn)一步去我尋找問(wèn)題的答案，去考慮為什么原本應(yīng)該是錯(cuò)誤的答案最后卻異常的正確了，會(huì)課下再進(jìn)行研究。7、我后來(lái)再改進(jìn)重新運(yùn)行貪心法求解01背包問(wèn)題時(shí)發(fā)現(xiàn)傳數(shù)組可以不用*w或*v可以直接使用void Sort(int n,double a1001,int w1001,int v1001,int b1001)，這樣也可以