利用動態(tài)規(guī)劃算法解0-1背包問題、動態(tài)規(guī)劃算法介紹岸」動態(tài)規(guī)劃算法(DynamicProgrammingAlgorithm,DPA)與是將待求解問題分解成若干個子問題，先求解子問題，然后從這營解。與分治法不同的是，適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分，相獨立的，若用分治法解這類問題，則分解得到的子問題數(shù)目太:需要耗費過多的時間。在用分治法求解時，有些子問題被重復(fù)計;保存已解決的子問題的答案，而在需要時再找出已求得的答案，i計算。為了達(dá)到此目的，可以用一個表來記錄所有已解決的子問】法的基本思想。岸」動態(tài)規(guī)劃算法使用于解最優(yōu)化問題。通?？砂匆韵?個步驟設(shè)計1、找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2、遞歸地定義最優(yōu)值；1=3、以自底向上的方式計算出最優(yōu)值；4、根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。1=1=1步驟1~3是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情需要求出問題的最優(yōu)解，則必須執(zhí)行步驟4。此時，在步驟3中i更多的信息，以便在步驟4中，根據(jù)所記錄的信息，快速構(gòu)造出二、0-1背包問題I三」【問題描述】：給定n種物品和一背包。物品i的重量是wi，1=1I三」問應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價值:品時，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不也不能只裝入部分的物品i。因此，該問題稱為0-1背包問題。【算法分析】：0-1背包問題的最優(yōu)子結(jié)構(gòu)，設(shè)(yi,y2,...,yn)是最優(yōu)解，則(y2,y3,...,yn)是經(jīng)過一次選擇后的0-1背包問題的；I歸關(guān)系，設(shè)當(dāng)前子問題的最優(yōu)值為m(ij)，即m(ij)使背包容量i,i+i,...,n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子m(ij)的遞歸式：當(dāng)i=n時，若j>=wn，則m(ij)=vn；若0<=j<wn，則m(i當(dāng)i<n時，若j>=wi，則m(ij)=max{m(i+1j),m(i+1j-wi：m(ij)=m(i+1j)?！舅惴▽崿F(xiàn)】Knapsack算法的C++實現(xiàn)如下：(其中背包信息從文件中讀取，點擊進入該文件下載界面)viewsourceprint?001#include"iostream"002usingnamespacestd;003004#definen50//物品的數(shù)量006〃物體重量、收益、背包容量007intweight[n],profit[n],contain,x[n],**m;008009〃從文件中讀取背包信息010intread_infor()011{012FILE*fp;013inti;014if((fp=fopen("knapsack.txt","r"))==NULL)015{016printf("Thefileisnotfound!");017return0;018}019〃讀取物體收益信息021022023024025026027028029030031032033}034fscanf(fp,"%d",&profit[i]);}〃讀取物體重量信息for(i=0;i<n;i++)fscanf(fp,"%d",&weight[i]);}i=j//讀取背包容量fscanf(fp,"%d",&contain);i=j//讀取背包容量fscanf(fp,"%d",&contain);fclose(fp);return1;035voidKnapsack()036{037038039040041042043044045046047048049050intjMax=min(weight[n-1]-1,contain);inti,j;fOr(j=0;j<=jMax;j++){m[n-1][j]=0;}fOr(j=weight[n-1];j<=contain;j++){m[n-1][j]=profit[n-1];}for(i=n-2;i>0;i--){jMax=min(weight[i]-1,contain);for(j=0;j<=jMax;j++)052m[i][j]=m[i+i][j]；TOC\o"1-5"\h\z053}054for(j=weight[i];j<=contain;j++)055{056m[i][j]=max(m[i+1][j],m[i+1][j-weight[057}058}059m[0][contain]=m[1][contain];060if(contain>=weight[0])061{062m[0][contain]=max(m[0][contain],m[1][coiprofit[0]);063}

066voidTraceback()intc=contain;fOr(inti=0;i<n-1;i++)(if(m[i][c]==m[i+1][c]){x[i]=0;}else{x[i]=1;067{068069070071072073074075076077078079c-=weight[i];081x[n-1]=(m[n-i][c])?1:0；082}083084voidmain()085{086inti,sumWeight=0;087if(read_infOr())088{089m=(int**)malloc(n*sizeof(int*));090for(i=0;i<n;i++)091{092m[i]=(int*)malloc(contain*sizeof(int));093}094Knapsack();095096097098099100101102103104105106107108109Traceback();}printf("Thechoiceis:\n");for(i=0;i<n;i++){sumWeight+=weight[i]*x[i];if(i!=0&&i%5==0){printf("");}printf("%1d",x[i]);}printf("\nThemaximumprofitis:%d?七m[1][coiprintf("\nTheknapsackweightis%d.\n",sumWscanf("%d",&i);for(i=0；i<n;i++)TOC\o"1-5"\h\z{free(m[i]);}free(m);}【算法復(fù)雜度分