動態(tài)規(guī)劃0或1背包問題

一、實驗內(nèi)容1、實驗題目0/1背包問題：給定n中物品和一個背包，物品i的重量是wi，價值是vi,背包的容量為co2、實驗?zāi)康纳羁汤斫獠⒄莆談討B(tài)規(guī)劃算法的設(shè)計思想；利用動態(tài)規(guī)劃方法設(shè)計背包問題算法，掌握動態(tài)規(guī)劃法的基本思想和算法設(shè)計的基本步驟。3、實驗要求設(shè)計0/1背包問題的動態(tài)規(guī)劃算法，要求輸出背包內(nèi)物品的最大價值以及選入背包的物品種類。利用C++語言實現(xiàn)算法，給出程序的正確運行結(jié)果。4、算法設(shè)計思想0/1背包為題可以看作是決策一個序列(x1，x2xn)，對任何一個變量xi的決策是決定xi=1還是xi=0.對xi-1決策后，已經(jīng)確定了(xl，xi-1)，在決策Xi時問題處于下列兩種狀態(tài)之一：背包容量不足以裝入物品i則xi=0，背包不增加價值；背包容量可以裝入物品i，則xi=1，背包的價值就增加了vi。這兩種情況下背包價值的最大者應(yīng)該是對xi決策后的背包價值。令V(i，j)表示在前i(1<=i<=n)個物品中能夠裝入容量為j(1<=j<=C)的背包中的物品的最大值則可以得到如下的動態(tài)規(guī)劃函數(shù):V(i,0)=V(0,j)=0j<Wi:V(i,j)=V(i-1,j)j>=Wi:V(i,j)=max{V(i-1,j),V(i-1,j-wi)+vi}二、代碼和運行結(jié)果截圖1、代碼#include<iostream.h>#include<stdlib.h>#definen5//5種物品的一個背包#defineC10〃背包容量structKnapSack{intw[C];//n個物品的重量存儲在數(shù)組w口中intv[n];//n個物品的價值存儲在數(shù)組v口中}knapsack;intmax(inta,intb)〃求最大值{if(a>=b)returna;elsereturnb;}voidmain(){intV[n+1][C+1];inti,j;intsi;intvi;intX;//X=0或X=1判斷物品是否裝入cout<<"輸入物品的重量、價值〃<<endl;for(i=1;i<=n;i++){cin>>knapsack.w[i];〃第i個物品的重量cin>>knapsack.v[i];〃第i個物品的價值}cout<<"輸入物品的信息如下表：〃<<endl;cout<<"物品|重量|價值〃<<endl;cout<<"11"<<endl;for(i=1;i<=n;i++)〃物品信息{cout<<i<<"|〃<<knapsack.w[i]<<〃〃<<knapsack.v[i]<<endl;cout<<""<<endl;for(i=0;i<=n;i++)〃初始化第0列{V[i][0]=0;}for(j=0;j<=C;j++)〃初始化第0行{V[0][j]=0;}for(i=1;i<=n;i++)//計算第i行，進行第i次迭代{V[i][0]=0;si=knapsack.w[i];vi=knapsack.v[i];for(j=1;j<=C;j++){V[i][j]=V[i-1][j];if(si<=j){V[i][j]=max(V[i][j],V[i-1][j-si]+vi);}}}cout<<"cout<<〃輸出結(jié)果V[n,C]=〃<<V[n][C]<<endl;//背包取得的最大價值cout<<〃〃<<endl;for(i=0;i<=n;i++){cout<<〃第〃<<i<<〃次結(jié)果〃<<endl;for(j=0;j<=C;j++)cout<<V[i][j]〈〈'';cout<<endl<<zz〃〈〈endl;for(i=0;i<5;i++){if(V[i][C]〈V[i+l][C])X=l;〃裝入elsex=o;〃不裝入cout〈〈〃選中的物品情況//?endl?//X=//?X?endl;2、運行結(jié)果截圖g*F:\Debug\背包問題-exe莉入物品的重量、價值Q623655446臆入物品的信息如下表：兩品；重量:價值航出結(jié)果Utn,C]=15便以次結(jié)果H0000000000律1次結(jié)果00666666666律2次結(jié)果00669999999律3次結(jié)果B0669999111114律4次結(jié)果h06699910111314律S次結(jié)果0066991212151515性中的物品情況：K=1怯中的物品情況二K=1陟中的物品情況二K=1QQ拼者售示陶中伊物品情況二■QQ拼者售示動態(tài)規(guī)劃算法是將待求解的問題分解成若干個子問題，但各子問題中往往是不相互獨立的。動態(tài)規(guī)劃算法將每個子問題只求解一次并將其