一、问题描述：有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
二、总体思路：根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现；
三、动态规划的原理及过程：
eg：number＝4，capacity＝8
|
i |
1 |
2 |
3 |
4 |
|
w(体积) |
2 |
3 |
4 |
5 |
|
v(价值) |
3 |
4 |
5 |
6 |
1、原理
动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。
2、过程
a) 把背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选），Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积（重量）；
b) 建立模型，即求max(V1X1+V2X2+…+VnXn)；
c) 约束条件，W1X1+W2X2+…+WnXn<capacity；
d) 定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值；
e) 最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。判断该问题是否满足最优性原理，采用反证法证明：
假设(X1，X2，…，Xn)是01背包问题的最优解，则有(X2，X3，…，Xn)是其子问题的最优解，
假设(Y2，Y3，…，Yn)是上述问题的子问题最优解，则理应有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V2X2+V3X3+…+VnXn)+V1X1；
而(V2X2+V3X3+…+VnXn)+V1X1=(V1X1+V2X2+…+VnXn)，则有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V1X1+V2X2+…+VnXn)；
该式子说明(X1，Y2，Y3，…，Yn)才是该01背包问题的最优解，这与最开始的假设(X1，X2，…，Xn)是01背包问题的最优解相矛盾，故01背包问题满足最优性原理；
f) 寻找递推关系式，面对当前商品有两种可能性：
第一，包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝
其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；
由此可以得出递推关系式：
1) j<w(i) V(i,j)=V(i-1,j)
2) j>=w(i) V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝
g) 填表，首先初始化边界条件，V(0,j)=V(i,0)=0；
h) 然后一行一行的填表，
1) 如，i=1，j=1，w(1)=2，v(1)=3，有j<w(1)，故V(1,1)=V(1-1,1)=0；
2) 又如i=1，j=2，w(1)=2，v(1)=3，有j=w(1),故V(1,2)=max｛ V(1-1,2)，V(1-1,2-w(1))+v(1) ｝=max｛0，0+3｝=3；
3) 如此下去，填到最后一个，i=4，j=8，w(4)=5，v(4)=6，有j>w(4)，故V(4,8)=max｛ V(4-1,8)，V(4-1,8-w(4))+v(4) ｝=max｛9，4+6｝=10；所以填完表如下图：
java：
import java.util.Scanner;
public class Bag {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int w[] = new int[n+1];//存放重量
int v[] = new int[n+1];//存放价值
int c = sc.nextInt();//背包最大容量
int sum[][] = new int[n+1][c+1];
for (int i = 1; i <= n; i++) {
w[i] = sc.nextInt();
v[i] = sc.nextInt();
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= c; j++) {
if(w[i]<=j) {
sum[i][j] = Math.max(sum[i-1][j], sum[i-1][j-w[i]]+v[i]);
}else {
sum[i][j] = sum[i-1][j];
}
}
}
System.out.println(sum[n][c]);
}
}
另一个例子：
