对于下图的例子，一种常见的贪心思想是：在背包可以装得下的情况下，尽可能选择价值更高的物品。那么当背包容量是W=11时，先选择item5，再选择item2，最后只能放下item1，总价值为28+6+1=35。实际上最优解是选择item3和item4，价值18+22=40。这说明了贪心算法对于背包问题的求解可能不是zuiyou的。下面考虑使用动态规划算法求解，首先要推导递归关系式。
类似于Weighted Interval Scheduling问题，定义opt(i, w)表示在有i个item，且背包剩余容量为w时所能得到的最大价值和。
考虑第i个item，有选和不选两种情况：
case 1: 如果选择第i个item，则
case 2: 如果不选择第i个item，则
边界条件: 当i=0时，显然opt(i,w)=0。
后一步的结果取前一步所有可能情况的最大值，因此综上所述，能得到动态规划的递归关系为：
算法迭代过程如下表：
值得注意的是，该算法相对于输入尺寸来说，不是一个多项式算法，虽然O(nW)看起来很像一个多项式解，背包问题实际上是一个NP完全问题。
为了便于理解，可以写成这种形式：
W在计算机中只是一个数字，以长度logW的空间存储，非常小。但是在实际运算中，随着W的改变，需要计算nW次，这是非常大的（相对于logW来说）。例如，当W为5kg的时候，以kg为基准单位，需要计算O(5n)次，当W为5t时，仍然以kg为单位，需要计算O(5000n)次，而在计算机中W的变化量相对很小。
Sequence Alignment Define edit distance给定两个序列x1,x2...xi和y1,y2,...,yj。要匹配这两个序列，使相似度足够大。首先需要定义一个表示代价的量-Edit distance，只有优化使这个量最小，就相当于最大化匹配了这两个序列。
Edit distance的定义如下所示。
其中，匹配到空，设距离为delta，否则字母p和q匹配的距离记为alpha(p,q)，如果p=q，则alpha=0；
那么两个序列匹配的总代价为：
设opt(i,j)是序列x1,x2...xi和y1,y2,...,yj之间匹配所花费的最小代价。当i，j不全为0时，则分别有三种情况，分别是xi-gap，yj-gap，xi-yj，分别计算不同匹配情况所花费的代价，再加上前一步的结果，就可以建立递推关系式，如下所示。