01背包描述的是这样一个问题：
有一个容量为m的背包，有n个物品，第i个物品的重量为w[i], 价值为v[i]。现在要往背包中装这些物品，使得最后所获得的总价值最大。
状态定义：
dp[i][j]表示：解决了第0~i个物品的选取问题后，背包已消耗容量为j时，所获得的最大价值。
状态转移：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]).
核心代码：
1 memset(dp[0], 0, sizeof(dp[0])); 2 if(w[0]<=m) dp[0][w[0]] = v[0]; 3 for(int i=1; i<n; ++i) 4 { 5 for(int j=0; j<=m; ++j) 6 { 7 if(j>=w[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]); 8 else dp[i][j] = dp[i-1][j]; 9 } 10 ans = 0; 11 for(int i=0; i<=m; ++i) ans = max(ans, dp[n-1][i]); 12 }
优化空间复杂度后的代码（注意第二重for循环的遍历顺序）：
1 memset(dp, 0, sizeof(dp)); 2 for(int i=0; i<n; ++i) 3 for(int j=m; j>=w[i]; --j) 4 dp[j] = max(dp[j], dp[j-w[i]]+v[i]); 5 ans = 0; 6 for(int i=0; i<=m; ++i) ans = max(ans, dp[i]);
题目来源：http://hihocoder.com/problemset/problem/1038