解决dp(动态规划)问题基本有四个主要步骤：
描述一个最优解的结构（最优子结构），借助“图”可利于分析问题；分析重叠子结构性质（计算某一种情况时，会重复出现之前的计算步骤），从而确定“自底向上”or“带备忘录的自顶向下”解题方法；关键：递归定义状态方程；构建路径（此步依题而定，如果只求最优解则可以省略）。
设: weight[i]:第i个物品的重量； value[i]：第i个物品的价值； f[i][j]重点内容:在只有i个物品，背包容量为j的情况下,问题的最大价值。 或者理解为：前i个物品装入容量为j的背包里获得的最大价值。 注意： f[i][0]:0容量时，所有物品都不取，最大价值为0； f[0][j]:没有物品可取，最大价值为0。
因此，容易得出本题的状态方程： (1) f(i,0)=f(0,j)=0 (2) f(i,j)=f(i-1,j) j<wi f(i,j)=max{f(i-1,j) ,f(i-1,j-wi)+vi) j>wi(2)式表明：如果第i个物品的重量大于背包的容量，则物品i不能装入背包。此时，装入前i个物品得到的最大价值（最优解）和装入前i-1个物品得到的最大价值是相同的；
反之，如果第i个物品的重量小于背包的容量，则会有两种情况： (a)如果把第i个物品装入背包，则背包物品的总价值等于第i-1个物品装入容量为j-weight[i] 的背包中的价值加上第i个物品的价值value[i]; (b)如果第i个物品没有装入背包，则背包中物品总价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。 显然，取二者中价值最大的作为 前i个物品装入容量为j的背包中的最优解。
注意!!!对于max函数的理解： 此时待选的物品仍有很多个，所以这是是一个比较最大值的过程，需要计算多次。不要单纯的把物品想象成只有一个，装进背包，价值一定增大。max比较的是：待装的物品中，将哪个装入，可使得总价值最大（最优解）。结合以下状态表格更容易理解。 横坐标为背包剩余容量（递增），纵坐标为选中物品的数量（递增）。 每一个单元格含义：在满足当前容量及物品个数要求时，所能创造的最大价值。
接下来，直接贴代码：
package dp0_1背包; public class Main { static final int M = 15;//背包容量 public static void main(String[] args) { int N = 4;//物品种类 int[] weight = {0, 3, 4, 5, 6};//为了题解方便，i对应第i个物品 int[] value = {0, 4, 5, 6, 7}; KnapSack(N, weight, value); } private static void KnapSack(int N, int[] weight, int[] value){ int[] x = new int[N+1]; int[][] f = new int[N+1][M+1]; for(int i=1; i<=N; i++) for(int j=1; j<=M; j++){ if(j < weight[i]) f[i][j] = f[i-1][j]; else f[i][j] = Math.max(f[i-1][j], f[i-1][j-weight[i]]+value[i]); //dp可以存储之前计算过的量，从而减少内存就体现在这里。如果收益比上一次大就记录下来，否则不记录，节省内存。 } //记录路径 //!!!在选择物品是否装入背包时，一定要逆序！！ //因为判断下一个是否要装入时，是在减掉前面装入的所有容量之和之后，才判断下一个能否装入 //而不是一项一项累加 判断和是否超出容量界限。 int j = M; for(int i=N; i>=1; i--) if(f[i][j]>f[i-1][j]){ x[i] = 1; //第i个物品要选 j = j - weight[i]; } System.out.println("选中的物品是:"); for(int i=1; i<=N; i++) System.out.print(x[i] + " "); System.out.println(); } }结果：
选中的物品是: 1 1 1 0 最后，可以看出：在计算f[i][j]时只使用了f[i-1][0……j]，没有使用其他子问题，因此在存储子问题的解时，只存储f[i-1]子问题的解即可。这样可以用两个一维数组解决（降维），一个存储子问题，一个存储正在解决的子问题。这里只写出状态方程，代码交给诸位博友自由发挥吧。f[j]=max(f[j],f[j-weight[i]]+value[i]);