動態規劃 01背包 問題描述 求解思路 代碼實現 放入哪些物品 代碼
我在上一篇博客裡已經講了一點動態規劃了，傳送門：算法學習 - 動態規劃(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背包是在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的時候，裝入物品是否會增加價值！
代碼其實行數很少，不好看那些寫了兩個屏幕的，可能並沒有更多的功能。
//
// main.cpp
// DP_01backpack
//
// Created by Alps on 15/4/28.
// Copyright (c) 2015年 chen. All rights reserved.
//
// 代碼中直接定義了石頭的數量和背包的空間，其實可以不用提前定義。
// 這裡為了方便，而且在C++ 11中可以動態規定數組大小。
#include
using namespace std;
#ifndef STONE_NUM
#define STONE_NUM 5 //定義石頭數量
#endif
#ifndef BACKPACK_SPACE
#define BACKPACK_SPACE 10
#endif
int main(int argc, const char * argv[]) {
int stoneSpace, stoneValue;//保存當前輸入的物品空間和價值
int value[BACKPACK_SPACE+1] = {0}; //初始化value數組
for (int i = 0; i < STONE_NUM; i++) {
scanf(%d %d, &stoneSpace, &stoneValue);//接收物品輸入
for (int j = BACKPACK_SPACE; j > 0; j--) {//當背包空間在不同的時候，** j 一定是從大到小**
if (j >= stoneSpace && value[j] < (value[j-stoneSpace] + stoneValue)) {//假如背包空間足夠，並且放入總價值增加
value[j] = value[j-stoneSpace] + stoneValue;//放入，並更新總價值
}
}
}
printf(%d
, 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的空間沒有放入物品，也就是空余了。
這樣找到第一個最大得數的下標，就是使用的空間了。
比較簡單，只不過多了一步查找那些物品放入了，就是當背包空間減去物品空間，總價值也剛好增加了物品的價值數量，那麼說明這個物品被放入了。
代碼如下：
//
// main.cpp
// DP_01backpack
//
// Created by Alps on 15/4/28.
// Copyright (c) 2015年 chen. All rights reserved.
//
// 代碼中直接定義了石頭的數量和背包的空間，其實可以不用提前定義。
// 這裡為了方便，而且在C++ 11中可以動態規定數組大小。
#include
using namespace std;
#ifndef STONE_NUM
#define STONE_NUM 5 //定義石頭數量
#endif
#ifndef BACKPACK_SPACE
#define BACKPACK_SPACE 10
#endif
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
, value[i]);
}//打印value數組，這裡面存放的是，所有物品在背包只有空間i的時候，達到的最大總價值。
int backPackSpace = BACKPACK_SPACE;// 得到背包空間
while (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;
}
整個代碼比較簡單。 有疑問的留言，可以相互交流。
