1、前言
背包问题是典型的动态规划问题，它有非常多的类型，本文讨论最常见的0-1背包问题
0-1背包问题描述：
有一个窃贼在偷窃一家商店时发现有n件物品，第i件物品价值为vi元，重量为wi，假设vi和wi都为整数。他希望带走的东西越值钱越好，但他的背包中之多只能装下W磅的东西，W为一整数。他应该带走哪几样东西？
2、问题分析
动态规划问题最重要的就是找出状态方程，方程找错了，一定做不出来。
根据背包问题描述，第一印象肯定不是钢条切割类型的，因为如果把背包分成两个背包，并一定两个背包都能装满，可能会千万浪费，那么背包问题是否可以采用 “数组最大连续子元素和”方式解题？
假定前n-1个物品，小偷已经选好放入背包，此时价值最大，到第n个物品时，如果背包已有重量加上wn仍然不超重的话，那么前n个物品中，加上vn，即为价值最大。
如果超重呢，那么不添加n即可，价值依然为之前背包物品价值。
设设有n个物品，背包的重量为w，C[i][w]为最优解为：
3、编码
已有状态方程，如何编码呢？
C[i][w]中i和w均为变量，那么至少需要使用两次循环，逐个求出所有的C[i][w]。
/**
* 0 1背包问题
* 此问题满足最优子问题结构。
* 如果加上第i项的重量，不会超重，那么总体最大价值为value[i] + select[i-1][j-weight[i]]
* 如果加上第i项的重量超重了，那么总体最大价值为select[i-1][j]
*/
public static int pack(int[] value, int[] weight, int w){
int[][] select = new int[value.length][w+1];
for (int i = 1; i <= w; i++) {
select[0][i] = 0;
}
for (int i = 1; i < value.length; i++) {
select[i][0] = 0;
for (int j = 0; j <= w; j++) {
if (weight[i] <= j) {
if (value[i] + select[i-1][j-weight[i]] > select[i-1][j]) {
select[i][j] = value[i] + select[i-1][j-weight[i]];
}else {
select[i][j] = select[i-1][j];
}
}else {
select[i][j] = select[i-1][j];
}
}
}
return select[value.length-1][w];
}
上述代码中，i代表物品，j代表背包重量。为了求解最后结果，需要把从0递增到w的所有C[i][w]都求解一次。
ps：代码已上传至github，欢迎探讨
