对于0/1背包问题，可以通过作出变量x1,x2,…,xi的一个决策序列来得到它的解。而对变量x的决策就是决定它是取0值还是取1值。假定决策这些x的次序为xn,xn-1,…,x1。在对xn作出决策之后，问题处于下列两种状态之一：
背包的剩余容量是M，则没有产生任何效益；
剩余容量是M-w，则效益值增长了P。
显然，对xn-l,xn-2,…,x1的决策相对于决策x所产生的问题状态应该是最优的，否则xn,xn-1,…,x1就不可能是最优决策序列。如果设fj(x)是Knap(1,j,X)最优解的值，那么fn(M)就可表示为：
fn(M) = max {fn-1(M), fn-1(M-wn)+pn}
对于任意的fi(X)，这里i＞0，则有：
fi(X) = max {fi-1(X), fi-1(X-wi)+pi}
为了能由前向后递推而最后求解出fn(M)，需从f0(X)开始。对所有的X≥0，有f0(X)=0，当X<0时，有f0(X)=-∞。根据(5.2)，可求解出0≤X<w1和X≥w1情况下f1(X)的值。接着又可由(5.2)不断递推求出f2,f3,…,fn在X相应取值范围内的值。
例如：非形式化的背包算法，代码如下：
line void DKP(p，w，n，M) { 1 S0={0，0}； 2 for(i=1；i<=n-1；++i) { 3 S1 i={(Pj,Wj)|(Pj-pi,Wj-wi) ∈Si-1 and Wj≤M}； 4 Si=Merge_Purge(Si-1，S1 i) ； 5 }； 6 (PX,WX)=Sn-1的最末序偶； 7 (PY,WY)=(Pj+pn,Wj+wn)其中，Wj是Sn-1中使得Wj+wn≤M的所有 序偶中取最大值的W； //沿Sn-1, …, S1回溯确定xn, xn－l, …, x1的取值 8 if(PX>PY) xn = 0； //PX是Sn的最末序偶 9 else xn = 1； //PY是Sn的最末序偶 10 回溯确定xn, xn－l, …, x1； 11 }//DKP
DKP的实现：
可以用两个一维数组P和W来存放所有的序偶(P1,W1)。P1的值放在P中，W1的值放在W中。序偶集S0,S1, …, Sn互相邻接地存放。各个集合可以用指针F(i)来指示，这里0≤i≤n。对于0≤i<n，F(i)指示S中第一个元素所在的位置。F(n)是Sn-1中最末元素的位置加1。
例如：0／1背包问题的算法，代码如下：
line void DKnap(p，w，n，M，m) { float p[n]，w[n]，P[m]，W[m]，pp，ww，M； int F[0:n]，t，h，u，i，j，p，next； 1 F[0]=1；P[1]=W[1]=0 //S0设定 2 t=h=1； //S0的首端与末端 3 F[1]=next=2； //P和W中第一个空位 4 for(i=1；i<=n-l；++i) { //生成Si 5 k = t； 6 u = 在1≤r≤h中使得W[r]+wi≤M的最大的r； 7 for(j=1；j<=u；++j) { //生成S1 i及归并 8 (pp,ww)=(P[j]+pi,W[j]+wi)； //S1 i中的下一个元素 9 while((k<=h) and (W[k]<ww)) { //从Si-1中取元素来归并 10 P[next]=P[k]；W[next]=W[k]； 11 next=next+1；k=k+1 12 }； 13 if((k<=h) and (W[k]=ww)) { pp=max(pp，P[k])； 14 k=k+l 15 }； 16 if(pp>P[next-1] (P[next],W[next])=(pp,ww) 17 next=next+1； 18 }； 19 while((k<=h) and P[k]<=P[next-1]) { //清除 20 k=k+1； 21 }； 22 } //将Si-1中剩余的元素并入Si 23 while(k<h) { 24 (P[next],W[next])=(P[k]，W[k])； 25 next=next+l；k=k+l； 26 } //对Si+1置初值 27 t=h+1；h=next-1；F[i+1]=next； 28 }； 29 Parts； 30 }//DKnap
过程DKnap的分析：
假设Si的序偶数是|Si|。在i＞0的情况下，每个Si由Si-1和S1i归并而成，并且以|S1i|≤|Si-1|，因此有|Si|≤2|Si-1|。在最坏情况下没有序偶会被清除，所以
Σ|Si| = Σ2i = 2n-1。
0≤i≤n-1 0≤i≤n-1 即，DKnap的空间复杂度为О(2n)。
由Si-1生成Si需要Θ(|Si-1|)的计算时间，因此，计算S0,S1, …, Sn-1总的时间是Θ(Σ|Si-1|)。由于|Si|≤2i，所以计算S0,S1, …, Sn-1的总时间是О(2n)。
以上分析表明当n取大值时，DKnap的有效性似乎令人失望。但这类问题在很多情况下都能在“适当的”时间内解出。这是因为在很多情况下p和w都是整数。而且M比2n小得多。另外，支配规则在清除不应并入Si的序偶上是很有效的。
使用探试方法(heuristic)可以加速DKnap的计算。设L是最优解的估计值，它使得fn(M)≥L，又设PLEFT(i)=Σpj|1<j≤n。如果序偶(P,W)∈Si，且使得
P+PLEFT(i)<L，那么(P,W)就可从Si中清除。这是因为(P,W)充其量只能对S1n产生(P+Σpj,W+Σwj)这样的序偶，而P+Σpj=P+PLEFT(i)<L，故序偶(P,W)不可
i<j≤n i<j≤n i<j≤n
能导致最优解fn(M)，故可从Si删去。找小于等于fn(M)的估计值L的一种简单方法是取Si的最末序偶(P,W)的P作为L。此时P≤fn(M)。更好的一种估计值是将某些剩余物品的p值与P值加在一起作为L。
小结
01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故仔细体会上面基本思路的得出方法，状态转移方程的意。
