动态规划
我在上一篇博客里已经讲了一点动态规划了，传送门：算法学习 – 动态规划(DP问题)(C++)
这里说一下，遇到动态规划应该如何去想，才能找到解决办法。
最主要的其实是要找状态转移的方程，例如上一篇博客里面，找的就是当前两条生产线的第i个station的最短时间和上一时刻的时间关系。
minTime(station[1][i]) = minTime(station[1][i-1] + time[i], station[2][i-1] + time[i] + trans[i-1])
今天要讲的问题是01背包问题。
01背包问题描述
01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。
求解这个背包能装的最大价值。（物体不能分割）。
求解思路
这个其实比上一道题难在哪里了呢？ 难在上一题装配线始终是两个，不会多，不会少。我们变化的量只有装配站的多少。
这个题目变化的量一个是物品的数量，还有一个是背包的空间。就是说装配线不会随着station的多少而变化，但是背包的空间会随着物品的装入而变化。
所以我们需要做的是判断当背包剩余的空间为j的时候，能否装入第i个物品，并且总价值增加。 即：
d[j] = max ( d[j], d[j-v[i]] + w[i]); //v[i]表示第i个物品的体积，w[i]表示第i个物品的价值。
其实我最开始看到上面这个状态转移的方程的时候，觉得这不是肯定的在空间j的时候放入物品，价值大于不放入物品的。毕竟只要放入就证明增加了价值啊。
其实不是这个样子的，因为只有在最开始都没有装入的时候，所有的都是0. 装入就一定价值增加。但是假如我们的物品如下：
物品1： 空间 2 价值 5 物品2： 空间 4 价值 3
当我们放入第一件物品的时候，，假设背包空间是5，那么d[2…5]都是为 5. 因为d[0…1]空间不够所以为0。 当我们放入物品2的时候，d[5] = 5 > d[5 – 4] + 3 因为d[1] = 0;。
发现了没有！ 并不是放入就一定总价值增加！
所以我们遍历所有物品，从第一个物品开始，找当空间为j的时候，装入物品是否会增加价值！
代码实现
代码其实行数很少，不好看那些写了两个屏幕的，可能并没有更多的功能。
namespace std;int main(int argc, const char * argv[]) {[BACKPACK_SPACE+1] = {0}; //初始化value数组for (int i = 0; i < STONE_NUM; i++) {scanf((j >= stoneSpace && value[j] < (value[j-stoneSpace] + stoneValue)) {//假如背包空间足够，并且放入总价值增加value[j] = value[j-stoneSpace] + stoneValue;//放入，并更新总价值}}}printf(“%d\n”, value[BACKPACK_SPACE]);return 0;}
这里解释下，为何第二层for循环里，j 是从最大变化到最小的。因为我们比较的是当前物品放入，价值是否有变化，就是 value[j] 和 value[j – v] 比较。 假如更新了，那么 value[j + 1] 需要和 value[j + 1 – v] 比较的值，可能 value[j + 1 – v]已经被更新过了。就不行了！因为那个时候value[j + 1 -v]的总价值已经算上当前的物品了。再算就重复了。
放入哪些物品
上面的代码没有知道到底放入了哪些物品，其实是因为为了节省空间，没有保存每个 stoneSpace和 stoneValue. 所以我们把它们变成数组就好了。
然后我们首先要做的是：找到一共背包用了多少空间！
这个很重要，因为背包的最大价值不一定是装满了，所以我们要找到用了多少空间，才能知道到底放入了哪些物品。
怎么找呢？
假如我们的value数组如下：
0 0 4 6 9 10 13 15 15 19 19
很容易知道，这个背包剩余了一个空间? 为什么呢，因为最大的19有两个，j 多了1但是价值没有增加，说明这 1的空间没有放入物品，也就是空余了。
这样找到第一个最大得数的下标，就是使用的空间了。
代码
比较简单，只不过多了一步查找那些物品放入了，就是当背包空间减去物品空间，总价值也刚好增加了物品的价值数量，那么说明这个物品被放入了。
代码如下：
namespace std;int main(int argc, const char * argv[]) {int value[BACKPACK_SPACE+1] = {0};int stoneSpace[STONE_NUM],stoneValue[STONE_NUM];for (int i = 0; i < STONE_NUM; i++) {scanf(“%d %d”, &stoneSpace[i], &stoneValue[i]);for (int j = BACKPACK_SPACE; j > 0; j–) {if (j >= stoneSpace[i] && value[j] < value[j-stoneSpace[i]] + stoneValue[i]) {value[j] = value[j-stoneSpace[i]] + stoneValue[i];}}}//以上代码几乎无变化，只是存储是数组存储了。for (int i = 0; i <= BACKPACK_SPACE; i++) {printf(“%d\n”, value[i]);}(value[backPackSpace] == value[backPackSpace-1]) {backPackSpace–;//假如背包价值和背包空间-1的时候价值相同，空间 -1}//找到一共使用了多少空间for (int i = STONE_NUM-1; i >= 0; i–) {if (value[backPackSpace] == value[backPackSpace-stoneSpace[i]] + stoneValue[i]) { //假如减去当前物品的空间，总价值刚好和物品的价值相等，说明此物品被放入了。printf(“%d “, i+1);//打印这个物品。i+1是因为物品的下标是从0开始的。backPackSpace = backPackSpace – stoneSpace[i]; //背包放入了这个物品，自然空间减少了。}}return 0;}
整个代码比较简单。 有疑问的留言，可以相互交流。
我看了一篇其他博客，用二维矩阵入门，也觉得很棒。推荐：
痛苦留给的一切，请细加回味!苦难一经过去，苦难就变为甘美。
