這個問題也可以用動态規劃的分階段決策方法，來确定把哪一個物體裝入背包的最優決策，假定背包的載重量範圍是0-m，類似資源配置設定那樣，另optpi[j]表示在前i個物體中，能夠裝入重量為i的背包的物體的最大價值，j=1,2,3.......m.顯然，此時在前i個物體中，有些物體可以裝入背包，有些物體不能裝入背包。于是，可以得到下面的動态規劃函數：
6.6.1表面：把前i個物體裝入載重量為0的背包，或把0個物體裝入載重量為j的背包，得到的價值都是0.
6.6.2表面：
如果第i個物體的重量大于背包的載重量,則等于optp[i-1][j].
如果j>=wi.
optp[i-1](j-wi)+pi 表面：當第i個物體的重量小于背包載重量時，如果把第i個物體裝入載重量為j的背包，則背包中物體的價值==
等于把前面i-1個物體裝入載重量為j-wi的背包所得到的的價值+加上第i個物體的價值pi。
如果第i個物體沒有裝入背包，則背包中物體價值就等于把前面第i-1個物體裝入載重量為j的背包中所取得的價值。
顯然，這2種裝入方法，取的的價值不一定相同。是以，取最大值。
#include<iostream>
#include<climits>
#include<iomanip>
using namespace std;
typedef struct{
float p;
float w;
float v;
}Object;
Object object[7];//7個物品
float knapsack(int w[],float p[],int m,int n,bool x[ ])
{
float **optp=new float*[n+1];
for(int i=0;i<=n;i++)
optp[i]=new float[m+1];
for(int i=0;i<=n;i++)
{
optp[i][0]=0;
x[i]=false;
}
for(int i=0;i<=m;i++)
optp[0][i]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j<w[i])
{
optp[i][j]=optp[i-1][j];
}
else
{
int tmp1=optp[i-1][j];
int tmp2=optp[i-1][j-w[i]]+p[i];
if(tmp1>=tmp2)
{
optp[i][j]=tmp1;
}
else
{
optp[i][j]=tmp2;
}
}
}//end inner for
}
int j=m;//遞推裝入背包的物體
for(int i=n;i>0;i--)
{
if(optp[i][j]>optp[i-1][j])
{
x[i]=true;
j=j-w[i];
}
}
return optp[n][m];
}
int main()
{
int M=10;
float pArr[]={0,6,3,5,4,6};
int wArr[]={0,2,2,6,5,4};
bool x[6];
cout<<"各個物品價值為"<<endl;
for(int i=1;i<=5;i++)
cout<<left<<setw(2)<<pArr[i]<<ends;
cout<<endl<<"各個重量"<<endl;
for(int i=1;i<=5;i++)
cout<<left<<setw(2)<<wArr[i]<<ends;
cout<<endl;
cout<<"最大價值為"<<knapsack(wArr,pArr,M,5,x)<<endl;
cout<<"解為"<<endl;
for(int i=1;i<=5;i++)
cout<<x[i]<<ends;
cout<<endl;
} 注意我們的pArr[]和wArr[]第0個都應該不存，與上面的knapsack對應：
float pArr[]={0,6,3,5,4,6};
int wArr[]={0,2,2,6,5,4}; 這點要特别注意，否則很容易出錯。 for(int j=1;j<=m;j++)裡面的代碼： if(j<w[i])
{
optp[i][j]=optp[i-1][j];
}
else
{
int tmp1=optp[i-1][j];
int tmp2=optp[i-1][j-w[i]]+p[i];
if(tmp1>=tmp2)
{
optp[i][j]=tmp1;
}
else
{
optp[i][j]=tmp2;
}
} 可以簡化為:
optp[i][j]=optp[i-1][j];
if( (j>=w[i]) && optp[i-1,j-w[i]] + p[i] >optp[i-1][j];
optp[i][j]=optp[i-1][j-w[i]] + p[i]; 資料是鄭宗漢這本書上的。
float pArr[]={0,6,3,5,4,6};
int wArr[]={0,2,2,6,5,4}; 用1個(n+1)*(m+1)的表，來存放前面i個物體裝入載重量為j的背包時，所能取得的最大價值。
程式輸出結果： 結果正确。 算法導論上的僞代碼： 關于複雜度的一個問題？上面的代碼複雜度是O(nw)嗎？ 其實這裡忽略的問題是，在上面的程式中n才是輸入規模，而W并不是輸入規模，因為它是背包的容量，而背包的數量一直都是為1的，如果在物品數量為n的情況下，背包的容量為2^n，那麼這個算法的複雜度就是O(n*2^n), 是以這個問題是NP難的。
背包貌似不适用普通的線性規劃，應該視為整數規劃，可以認為是一個0-1規劃模型。
而整數規劃或0-1規劃似乎沒有多項式解法 背包問題的輸入input = logC（C的二進制字長），這樣DP複雜度對應于輸入是theta（n*
2^input）。是以是np的。是以稱背包問題的DP解法是僞多項式複雜度。 （容量可以很大）。 wikipedia定義： 在計算理論領域中，若一個數值算法的時間複雜度可以表示為輸入數值N的多項式，則稱其時間複雜度為僞多項式時間。由于N的值是N的位數的幂，故該算法的時間複雜度實際上應視為輸入數值N的位數的幂。
一個具有僞多項式時間複雜度的NP完全問題稱之為弱NP完全問題，而在P!=NP的情況下，若一個NP完全問題被證明沒有僞多項式時間複雜度的解，則稱之為強NP完全問題。
在素性測試中，使用較小的整數逐個對被測試數進行試除的算法被認為是一個僞多項式時間算法。對于給定的整數N，使用從最小的素數2開始，到為止的整數依次對N進行試除，如果均無法整除N，則N是素數，這個過程需要進行至多約次整數除法，即其時間複雜度為，為N的多項式。令D為N的二進制表示的位數，那麼N可以表示為以2為底D的幂，是以素性測試問題的時間複雜度用D表示應為。是以，上述算法是一個僞多項式時間算法。