晚上睡不着，翻同学发出来的笔记，看到背包问题，想了一下，趁热打铁把思路写下来。
如果阅读过程中有任何地方不理解，请先记住，耐下性子往下看。
0-1背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 w[i]，其价值为 v[i]。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
难点：由于给点的物品的顺序是随机的，所以有可能性价比最高的物品在后面，但按照顺序装物品，等要装性价比高的物品时，此时我们的背包已经填满了。
解决思路：假如每放一个物品下去，我都能列出所有组合的物品的价值最大值，最优解就出来了。
解决方法：
定义一个二维数组m[ i ][ j ]，i代表第i个物品，j代表此时背包的重量。而p[ i ][ j ] 代表总价值
对于第i件物品，每个j都有两种情况
1） j < w[ i ]
由于此时背包的容量小于物品i的重量，因此 m[ i ] [ j ]=p[ i-1 ][ j ] ·······①
2）j >= w[ i ]
此时背包的容量大于等于物品i的重量，那么这时候就要比较 当物品i的价值加上之前物品的价值 是否比 之前各种物品组合的价值 大，因此m[ i ] [ j ] = max(m[ i-1 ][ j ] ，m[ i-1 ][ j - m[ i ] ]+v[ i ])
ok，我们举个例子来说明一下会更加容易理解（这个代码是我同学的）
我们定义：
v[7]={0,8,10,6,3,7,2}; 价值
w[7]={0,4,6 ,2,2,5,1}; 重量
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=15;
int main(){
int v[N]={0,8,10,6,3,7,2};
int w[N]={0,4,6,2,2,5,1};
int m[N][N];
int n=6,c=12;
memset(m,0,sizeof(m));//数组初始化为0
for(int i=1;i<=n;i++){
for(int j=1;j<=c;j++){
if(j>=w[i]) m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
else m[i][j]=m[i-1][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=c;j++){
printf("%d ",m[ i ][ j ]);
}
printf("\n");
}
return 0;
}
当我列到m[ 3 ] [ 4 ]的时候，我就知道为什么①那个地方是m[ i ] [ j ]=p[ i-1 ][ j ]，他的目的就是要将之前物品组合的所有可能的价值再列出来，为下一个做准备。
与其说j是代表此时背包的重量，倒不如说，当背包的容量为j时，可以有多少种放物品的方式。
j的不同，代表着物品组合的方式也不一样，比如m[ 3 ][ 6 ]表示取物品1和物品3，m[ 3 ][ 8 ]表示取物品2和物品3，m[ 3 ][ 12 ]表示取物品1、2、3。
程序运行后，结果如下，为了更加方便理解，我调整了格式，最上面一排是j的值
这就符合每放一个物品下去，都能列出所有组合的物品的价值最大值的思路了
这种题目跟2048那几道题有异曲同工之处，也是递归问题。
