動態規劃 3 ——一維狀態 背包問題

首先申明下面要寫的總結主要摘自在網上找到的一篇動態規劃總結教程（沒找到作者），內容基本相同。寫這些東西純屬自己動態規劃復慣用。知乎上大神很多，其中有不妥的不對的地方歡迎指出，大家共同進步！！！

背包問題分析

首先說說背包問題的基本模型：

現有N個物品，每個物品的價值為V，重量為W。求用一個載重量為S的背包裝這寫物品，使得所裝物品的總價值最高。背包問題用貪心和搜索解，當然效果不佳。顯然標準的解法是動態規化，我在解決這個問題時習慣設計一維狀態，還可以設計二維的，二維狀態在下面會講，現在只討論用一維狀態實現背包問題。

背包問題的分類：

(1)小數背包:物品的重量是實數，如油，水等可以取1.67升……

(2)整數背包：<1>0/1背包：每個物品只能選一次，或不選。不能只選一部分

<2>部分背包：所選物品可以是一部分。

(3)多重背包：背包不只一個。

整數背包：

0/1背包：這個問題是最經常出現的問題，應該熟練掌握。

我們先看一下0/1背包的簡化版：

現有N個物品，每個物品重量為W，這些物品能否使在載重量為S的背包裝滿（即重量和正好為S）？如過不能那能使物品重量和最重達到多少？

針對這一問題我們以物品的個數分階段，設計一個狀態opt[i]表示載重量為i的背包可否裝滿，顯然opt[i]的基類型是boolean。

決策是什麼呢？

當要裝第i個物品時，如果前i-1個物品可以使載重為 k的背包裝滿，那麼載重為k+w[i]的背包就可以裝滿。於是對於一個opt[j]來說，只要opt[j-w[i]]是true（表示可裝滿）那opt[j]就可以裝滿，但要注意：針對每一個物品枚舉背包的載重量時如果這樣正向的推導會使同一個物品用好幾次，因為k+w[i]可裝滿那k+w[i]+w[i]就可裝滿，但實際上是裝不滿的因為物品只有一個。解決這個問題很簡單，只要逆向推導就OK了。

這樣劃分階段，設計狀態，滿足無後效性和么？

顯然對於每一個階段都是獨立的，物品的順序並不影響求解，因為裝物品的次序不限。而對於opt[j]只考慮opt[j-w[i]]而不考慮後面的，所以滿足無後效性。

有了上面的分析不難寫出狀態轉移方程：

opt[j] =opt[j-w[1]] {opt[j-w[i]]=true}

時間複雜度：

例題

1 裝箱問題

【問題描述】

有一個箱子容量為V（正整數，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30＝，每個物品有一個體積（正整數）。

要求n個物品中，任取若干個裝入箱內，使箱子的剩餘空間為最小。

【輸入文件】

第一 行一個正整數V表示箱子的容量，第二行一個正整數N表示物品個數，接下來N行列出這N個物品各自的體積。

【輸出文件】

單獨一行，表示箱子最小的剩餘空間。

【輸入樣例】

24

6

8

3

12

7

9

7

【輸出樣例】

0

【問題分析】

本題是經典的0/1背包問題，並且是0/1背包的簡化版，把箱子看做背包，容量看做載重量，體積看做重量，剩餘空間最小也就是盡量裝滿背包。於是這個問題便成了：

有一個栽重量為V的背包，有N個物品，盡量多裝物品，使背包盡量的重。

設計一個狀態opt[i]表示重量i可否構成。

狀態轉移方程：opt[j]:=opt[j-w[1]] {opt[j-w[i]]=true}

最終的解就是v-x（x<=n 且opt[x]=true 且 opt[x+1..n]=false）。

#include<iostream>using namespace std;class Solution{ private: int V; int* w; int N; public: void readData(){ cout<<"please input capacity:"; cin >> V; cout<<"please input the number of goods:"; cin >> N; w = new int[N]; for(int i = 0; i < N; i++){ cin >> w[i]; } }; int solve(){ bool* opt = new bool[V + 1]{false}; opt[0] = true; for(int i = 0 ; i < N; i++){ for(int j = V; j >= w[i]; j--){ if(opt[j-w[i]]) { opt[j] = true; } } } for(int i = V; i >= 0; i--){ if(opt[i]){ delete[] opt; return V - i; } } }; Solution(){this->w = NULL;}; ~Solution(){ if(w != NULL) delete[] w; this->w = NULL; };};

2 砝碼稱重

【問題描述】

設有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重<=1000），用他們能稱出的重量的種類數。

【輸入文件】

a1 a2 a3 a4 a5 a6

（表示1g砝碼有a1個，2g砝碼有a2個，…，20g砝碼有a6個，中間有空格）。

【輸出文件】

Total=N

（N表示用這些砝碼能稱出的不同重量的個數，但不包括一個砝碼也不用的情況）。

【輸入樣例】

1 1 0 0 0 0

【輸出樣例】

TOTAL=3

【問題分析】

把問題稍做一個改動，已知a1+a2+a3+a4+a5+a6個砝碼的重量w[i],w[i]∈{ 1,2,3,5,10,20} 其中砝碼重量可以相等，求用這些砝碼可稱出的不同重量的個數。

這樣一改就是經典的0/1背包問題的簡化版了，求解方法完全和上面說的一樣，這裡就不多說了，只是要注意這個題目不是求最大載重量，是統計所有的可稱出的重量的個數。

class Solution{ private: int N; int* a; int* num; int maxWeight; public: void readData(){ cin >> N; a = new int[N]; num = new int[N]; maxWeight = 0; for(int i = 0; i < N; i++){ cin >> a[i] >> num[i]; maxWeight += a[i] * num[i]; } } Solution(){ a = NULL; num == NULL; }; int solve(){ bool* opt = new bool[maxWeight + 1]{false}; opt[0] = true; for(int i = 0; i < N; i++){ for(int j = 0; j < num[i]; j++){ for(int k = maxWeight; k >= a[i]; k--){ if(opt[k - a[i]]) opt[k] = true; } } } int count = 0; for(int i = 1; i <= maxWeight; i++){ if(opt[i]) count++; } delete[] opt; return count; }; ~Solution(){ if(a != NULL) delete[] a; if(num != NULL) delete[] num; }};

3 積木城堡

【問題描述】

XC的兒子小XC最喜歡玩的遊戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木。小XC是一個比他爸爸XC還聰明的孩子，他發現壘城堡的時候，如果下面的積木比上面的積木大，那麼城堡便不容易倒。所以他在壘城堡的時候總是遵循這樣的規則。

小XC想把自己壘的城堡送給幼兒園裡漂亮的女孩子們，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們為了獲得更漂亮的城堡而引起爭執。可是他發現自己在壘城堡的時候並沒有預先考慮到這一點。所以他現在要改造城堡。由於他沒有多餘的積木了，他靈機一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應該使最後的城堡都儘可能的高。

任務：

請你幫助小XC編一個程序，根據他壘的所有城堡的信息，決定應該移去哪些積木才能獲得最佳的效果。

【輸入文件】

第一行是一個整數N(N<=100)，表示一共有幾座城堡。以下N行每行是一系列非負整數，用一個空格分隔，按從下往上的順序依次給出一座城堡中所有積木的棱長。用-1結束。一座城堡中的積木不超過100塊，每塊積木的棱長不超過100。

【輸出文件】

一個整數，表示最後城堡的最大可能的高度。如果找不到合適的方案，則輸出0。

【輸入樣例】

2

2 1 –1

3 2 1 -1

【輸出樣例】

3

【問題分析】

首先要說明一點，可以挪走任意一個積木，不見得是最上面的。

初看題目有點茫然，但抽象一下就。。。。。。。。。。

其實塔好積木在拿走就相當於當初搭的時候沒選拿走的積木。這樣一轉化思維問題就清楚了。把積木可搭建的最大高度看做背包的載重，每塊積木的高度就是物品的重量。也就是用給定的物品裝指定的包，使每個包裝的物品一樣多，且在符合條件的前提下盡量多。

這樣就變成經典的背包問題了。

對於每一個城堡求一次，最終找到每一個城堡都可達到的最大高度即可。

#include<iostream>#include<vector>using namespace std;class Solution {private: vector<vector<int>*> data; int minH; // 最後的結果肯定不高於最矮城堡的高度 int N;public: void readData() { this->destroy(); cout << "please input the number of the building block:"; cin >> N; minH = INT_MAX; for (int i = 1; i <= N; ++i) { cout << "please input the "<< i<<"th building block ,-1 means end:" << endl; vector<int>* d = new vector<int>(); int height = 0; int t; cin >> t; while (t != -1) { d->push_back(t); height += t; cin >> t; } if (height < minH) minH = height; this->data->push_back(d); } }; int solve() { this->readData(); vector<vector<bool>> opt(N, vector<bool>(minH + 1, false)); for (int i = 0; i < N; ++i) { vector<int>* d = (*data)[i]; opt[i][0] = true; for (auto it = d->begin(); it != d->end(); it++) { for (int k = minH ; k >= *it ; --k) { if (opt[i][k - *it]) opt[k] = true; } } } int i = minH; for (; i > 0; --i) { bool flag = true; for (int j = 0; j < N; j++) { flag &= opt[i][j]; } if (flag) break; } cout << "result: " << i << endl; return i; }; Solution() {}; void destroy() { for (auto it = data->begin(); it != data->end(); ++it) { if (*it != NULL) delete *it; } data.clear(); }; ~Solution() { this->destroy(); };};

背包問題階段總結

回顧上面的內容充分說明動態規劃的本質就是遞推。其實按照我的理解（動規涉及最優決策，遞推是單純的總結）背包問題的簡化版更準確點算是遞推而非動態規劃，至於動歸和遞推之間的界線本來就很模糊（至少我這麼認為）把它看做什麼都可以，沒必要咬文嚼字。

回到0/1背包的原問題上（如果你忘了就去上面看看）。

如果在不知道這個模型的情況下我們怎麼做這個題呢？

這就要用到第一節提到的方法二：三要素法。

題目中明確說明對於一個物品要不就拿走要不就放下，其實題目赤裸裸的告訴我們決策就是不拿（用0表示）或拿（用1表示）。這樣想都不用想就知道了決策，這也是本題的突破口。知道了決策寫個搜索的程序應該是很輕鬆的了。

那麼階段是什麼呢？

顯然，給你一堆東西讓你往包里塞，你當然是一個一個的那來，塞進去。那麼階段很明顯就是物品的個數。

狀態又是什麼呢？

有的人在裝東西是有個習慣（比如說我）就是先把東西分類，然後把同類的東西打個小包，最後在把小包放進去，我們可以按這個思想給物品打一些小包，也就是按照單位為1的遞增的順序準備好多小包，比如載重是6的包，可以為它準備載重是1，2，3，4，5的小包。這樣狀態就可以想出來了：

設計狀態opt[i，j]表示裝第i個物品時載重為j的包可以裝到的最大價值。

opt[i-1,j] (j-w[i]<0，i>0)

狀態轉移方程：opt[i,j]=

max{opt[i-1,j],opt[i-1,j-w[i]]+v[i]}(j-w[i]>=0,i>0)

(w[i]:第i個物品的重量，v[i]第i個物品的價值)

解釋：要載重為j的背包空出w[i]（j-w[i]）的空間且裝上第i個物品，比不裝獲得的價值大就裝上它。

邊界條件：opt[0,i]=0; (i∈{1..S})

註：

這種二維的狀態表示應該在下節講，但是為了方便理解先在這裡說了。

上面的方法動態規劃三要素都很明顯，實現也很簡單。但是在我初學背包時卻用另外一種一維的狀態表示法。

用第一節說的思考方法五（放寬約束和增加約束）在重新思考一下這個問題：

怎麼放寬約束呢？

把題目中的價值去掉，不考慮價值即最優就變成背包問題的簡化版了。那簡化版的求解對我們有何啟示呢？

再一次增加約束：背包只能裝滿。

顯然對於N個裝滿背包的方案中只要找到一個價值最大的就是問題的解。那麼裝不滿怎麼辦呢？其實裝不滿背包，它總要達到一定的重量（X）。我們可以把這種情況看作是裝滿一個載重為X的小包。

總結一下上面的思維過程：

放寬約束讓我們找到問題的突破口——和背包問題簡化版一樣，我們可以卻定載重為S的背包是否可以裝滿。

增加約束讓我們找到問題的求解方法——在裝滿背包的方案中選擇最優的一個方案。

這樣問題就解決了。

設計一個狀態opt[j]表示裝滿載重為j的背包可獲得的最大價值。對於第i個物品，只要opt[j-w[i]]可以裝滿且opt[j-w[i]]+v[i]比opt[j]大就裝上這個物品（更新opt[j]）。

怎麼使opt[j]既有是否構成又有最優的概念呢？

opt[j]只表示最優，只不過使初始條件+1，判斷opt[j]是否為0，如果opt[j]=0說明j裝不滿。

邊界條件：opt[0]=1;

狀態轉移方程：opt[j]=max{opt[j-w[i]]}(0<i<n,w[i]<=j<=S)

問題解：ans=max{opt[i]}-1 (0<i<=s)

時間複雜度：階段數O(S)*狀態數（O(N)）*轉移代價（O(1)）=O（SN）

再看幾個例題：

4 採藥

【問題描述】

辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞裡對他說：「孩子，這個山洞裡有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間裡，你可以採到一些草藥。如果你是一個聰明的孩子，你應該可以讓採到的草藥的總價值最大。」

如果你是辰辰，你能完成這個任務嗎？

【輸入文件】

輸入文件http://medic.in的第一行有兩個整數T（1 <= T <= 1000）和M（1<= M <= 100），用一個空格隔開，T代表總共能夠用來採藥的時間，M代表山洞裡的草藥的數目。接下來的M行每行包括兩個在1到100之間（包括1和100）的整數，分別表示採摘某株草藥的時間和這株草藥的價值。

【輸出文件】

輸出文件medic.out包括一行，這一行只包含一個整數，表示在規定的時間內，可以採到的草藥的最大總價值。

【輸入樣例】

70 3

71 100

69 1

1 2

【輸出樣例】

3

【數據規模】

對於30%的數據，M<= 10；

對於全部的數據，M <= 100。

【問題分析】

這是一道典型的0/1背包問題，把時間看做標準模型中的重量，把規定的時間看做載重為T的背包，這樣問題和基本模型就一樣了，具體實現這裡不多說了。

#include<iostream>#include<vector>using namespace std;class Solution {private: int totalTime; int N; int* times; int* values;public: void readData() { this->destroy(); cout << "please input the total time: "; cin >> this->totalTime; cout << "please input the number of the medic: "; cin >> this->N; this->times = new int[this->N]; this->values = new int[this->N]; cout << "please input the medic format(time value):" << endl; for (int i = 0; i < this->N; i++) { cout << "please input the " << (i + 1) << "th medic: " << endl; cin >> this->times[i] >> this->values[i]; } }; int solve() { this->readData(); int* opt = new int[this->totalTime + 1]{0}; for (int i = 0; i < N; i++) { int t = this->times[i]; int v = this->values[i]; for (int j = totalTime; j >= t; j--) { if (opt[j] < opt[j - t] + v) opt[j] = opt[j - t] + v; } } int result = opt[this->totalTime]; cout << "result: " << result <<endl; delete[] opt; return result; }; Solution() {this->times = NULL; this->values = NULL;}; void destroy() { if (this->times != NULL) delete[] this->times; this->times = NULL; if (this->values != NULL) delete[] this->values; this->values = NULL; }; ~Solution() { this->destroy(); };};

5 開心的金明

【問題描述】

金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：「你的房間需要購買哪些物品，怎麼布置，你說了算，只要不超過N 元錢就行」。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的N 元。於是，他把每件物品規定了一個重要度，分為5 等：用整數1~5 表示，第5 等最重要。他還從網際網路上查到了每件物品的價格（都是整數元）。他希望在不超過N 元（可以等於N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設第j 件物品的價格為v[j]，重要度為w[j]，共選中了k 件物品，編號依次為j1...jk，則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]請你幫助金明設計一個滿足要求的購物單.

【輸入文件】

輸入的第1 行，為兩個正整數，用一個空格隔開： N m

（其中N（<30000）表示總錢數，m(<25)為希望購買物品的個數。）

從第2 行到第m+1 行，第j 行給出了編號為j-1的物品的基本數據，每行有2 個非負整數 v p

（其中v 表示該物品的價格（v≤10000），p 表示該物品的重要度（1~5））

【輸出文件】

輸出只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（<100000000）

【輸入樣例】

1000 5

800 2

400 5

300 5

400 3

200 2

【輸出樣例】

3900

【問題分析】

這仍然是一到典型的0/1背包，只不過注意這個問題中的價值對應背包模型中的重量，這個問題中的價值和重要度的成績是背包模型中的價值。（很饒口啊）。

具體實現同背包模型一樣，這裡不多說了。

#include<iostream>using namespace std;class Solution {private: int N; int totalMoney; int* price; int* importance;public: void readData() { this->destroy(); cout << "please input the total money: "; cin >> this->totalMoney; cout << "please input the number of the things: "; cin >> this->N; cout << "please input the things(format: price importance)" << endl; this->price = new int[this->N]; this->importance = new int[this->N]; for (int i = 0; i < N; i++) { cout << "please input the " << i << "th thing:" << endl; cin >> this->price[i] >> this->importance[i]; } }; int solve() { this->readData(); int* opt = new int[this->totalMoney + 1]{0}; opt[0] = 1; for (int i = 0; i < this->N; i++) { int value = this->price[i] * this->importance[i]; for (int j = this->totalMoney; j >= this->price[i]; j--) { if (opt[j - this->price[i]] > 0 && opt[j - this->price[i]] + value > opt[j]) { opt[j] = opt[j - this->price[i]] + value; } } } int result = 0; int minMoney = this->totalMoney; for (int i = totalMoney; i > 0; i--) { if (opt[i] >= result) { result = opt[i]; minMoney = i; } } result = result - 1; cout << "result: " << result <<", money: "<<minMoney<< endl; delete[] opt; return result; }; Solution() {this->price = NULL; this->importance = NULL}; void destroy() { if (this->price != NULL) { delete[] this->price; } this->price = NULL; if (this->importance != NULL) { delete[] this->importance; } this->importance = NULL; }; ~Solution() { this->destroy(); };};

6 金明的預算方案

【問題描述】

金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：「你的房間需要購買哪些物品，怎麼布置，你說了算，只要不超過N元錢就行」。今天一早，金明就開始做預算了，他把想買的物品分為兩類：主件與附件，附件是從屬於某個主件的，下表就是一些主件與附件的例子：

主件 附件

電腦 印表機，掃描儀

書櫃 圖書

書桌 檯燈，文具

工作椅 無

如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有0個、1個或2個附件。附件不再有從屬於自己的附件。金明想買的東西很多，肯定會超過媽媽限定的N元。於是，他把每件物品規定了一個重要度，分為5等：用整數1~5表示，第5等最重要。他還從網際網路上查到了每件物品的價格（都是10元的整數倍）。他希望在不超過N元（可以等於N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。

設第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1，j2，……，jk，則所求的總和為：

v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*為乘號）

請你幫助金明設計一個滿足要求的購物單。

【輸入文件】

輸入文件http://budget.in 的第1行，為兩個正整數，用一個空格隔開：

N m （其中N（<32000）表示總錢數，m（<60）為希望購買物品的個數。）

從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數據，每行有3個非負整數： v p q

（其中v表示該物品的價格（v<10000），p表示該物品的重要度（1~5），q表示該物品是主件還是附件。如果q=0，表示該物品為主件，如果q>0，表示該物品為附件，q是所屬主件的編號）

【輸出文件】

輸出文件budget.out只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（<200000）。

【輸入樣例】

1000 5

800 2 0

400 5 1

300 5 1

400 3 0

500 2 0

【輸出樣例】

2200

【問題分析】

這道題是一道典型的背包問題，比較麻煩的就是它還存在附件和主件之分。但這並不影響解題，由於附件最多兩個，那麼我們做一個對主，附件做個捆綁就行了。

（1） 標準演算法

因為這道題是典型的背包問題，顯然標準演算法就是動態規劃。由於我們要對主，附件做捆綁。由於題目沒有直接給出每個主件對應的附件，所以還需要做一個預處理：另開兩個數組q1，q2來分別記錄對應的第i個主件的附件。那麼對與附件不需要處理。而主件的花費就有4種情況了。( 下面用W表示花費)

W1=v[i] （只買主件）

W2=v[i]+v[q1[i]] （買主件和第一個附件）

W3=v[i]+v[q2[i]] （買主件和第二個附件）

W4=v[i]+v[q1[i]]+v[q2[i]] （買主件和那兩個附件）

設計一個狀態opt[i]表示花i元錢可買到的物品的價格個重要度最大值。邊界條件是opt[0]=0但是為了區分花i元錢是否可買到物品我們把初始條件opt[0]:=1;這樣opt[i]>0說明花i元可以買到物品。這樣就不難設計出這個狀態的轉移方程來：

opt[i]=max{opt[i],opt[i-wj]} ((i-wj>0) and (opt[i-wj]>0)) (0<j<=4)

#include<iostream>#include<map>#include<vector>#include<algorithm>using namespace std;class Solution {private: int totalMoney; int N; int* importance; int* price; map<int, vector<int>*> master; void destroy() { if (this->importance != NULL) delete[] this->importance; this->importance = NULL; if (this->price != NULL) delete[] this->price; this->price = NULL; for (map<int, vector<int>*>::iterator it = this->master.begin(); it != this->master.end(); it++) { if (it->second != NULL) delete it->second; } master.clear(); };public: Solution() {this->importance = NULL; this->price = NULL;}; ~Solution() { this->destroy(); }; void readData() { this->destroy(); cout << "please input the total money: "; cin >> this->totalMoney; cout << "please input the count of the goods: "; cin >> this->N; this->importance = new int[N]; this->price = new int[N]; int index; cout << "please input the goods, format( price importance master): " << endl; for (int i = 0; i < this->N; i++) { cout << "please input the " << i + 1 << "th goods: " << endl; cin >> this->price[i] >> this->importance[i]; this->importance[i] *= this->price[i]; // here importance = importance * price , cin >> index; vector<int>* v = NULL; if (index > 0) { v = this->master[index - 1]; if (v == NULL) v = new vector<int>(); v->push_back(i); this->master[index - 1] = v; } else { v = this->master[i]; if (v == NULL) this->master[i] = new vector<int>(); } } } int solve() { this->readData(); int* opt = new int[this->totalMoney + 1]{0}; opt[0] = 1; for (map<int, vector<int>*>::iterator it = this->master.begin(); it != this->master.end(); it++) { for (int i = this->totalMoney; i >= this->price[it->first]; i--) { int index = it->first; if (opt[i - this->price[index]] > 0) opt[i] = max(opt[i], opt[i - this->price[index]] + this->importance[index] ); for (vector<int>::iterator vt = it->second->begin(); vt != it->second->end(); vt++) { int index_1 = *vt; int t_money = i - this->price[index] - this->price[index_1]; if (t_money >= 0 && opt[t_money] > 0) opt[i] = max(opt[i], opt[t_money] + this->importance[index] + this->importance[index_1]); } if (it->second->size() >= 2) { int index_1 = (*it->second)[0]; int index_2 = (*it->second)[1]; int t_money = i - this->price[index] - this->price[index_1] - this->price[index_2]; if (t_money >= 0 && opt[t_money] > 0) opt[i] = max(opt[i], opt[t_money] + this->importance[index] + this->importance[index_1] + this->importance[index_2]); } } } int result = 0; for (int i = this->totalMoney; i > 0; i--) { if (opt[i] >= result) result = opt[i]; else break; } delete[] opt; result -= 1; // note: initialize opt[0] = 1 cout << result << endl; return result; }};

7 Money System

【問題描述】

母牛們不但創建了他們自己的政府而且選擇了建立了自己的貨幣系統。[In their own rebelliousway],，他們對貨幣的數值感到好奇。

傳統地，一個貨幣系統是由1,5,10,20 或 25,50, 和 100的單位面值組成的。

母牛想知道有多少種不同的方法來用貨幣系統中的貨幣來構造一個確定的數值。

舉例來說, 使用一個貨幣系統 {1,2,5,10,...}產生 18單位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1,3x5+2+1,等等其它。寫一個程序來計算有多少種方法用給定的貨幣系統來構造一定數量的面值。保證總數將會適合long long (C/C++) 和 Int64 (Free Pascal)。

【輸入文件】

貨幣系統中貨幣的種類數目是 V (1<= V<=25)。要構造的數量錢是 N (1<= N<=10,000)。

第 1 行: 二整數， V 和 N

第 2 行： 可用的貨幣 V 個整數。

【輸出文件】

單獨的一行包含那個可能的構造的方案數。

【輸入樣例】

3 10

1 2 5

【輸出樣例】

10

【問題分析】

把錢面值，把要構造的前看做載重為N的背包，這個問題便是0/1背包的簡化版了，但這個問題和傳統模型有所差異，不是判斷N是否可構成，而是求構成N的方案，而且這裡的面值是可以重複利用的（你可以看做是物品有無限多）。

對與第一個問題，只要把原來bool型的狀態改為int，在遞推過程中累加方案數即可。

對於第二個問題，基本模型中為了避免重複在內重循環枚舉背包載重時採用倒循環，現在只要正向循環就OK了。

複雜度與原模型相同。

#include<iostream>#include<algorithm>using namespace std;class Solution {private: int N; int V; int* currency; void destroy() { if (this->currency != NULL) delete[] currency; this->currency = NULL; return; }public: Solution() {currency = NULL;}; ~Solution() { this->destroy(); }; void readData() { this->destroy(); cout << "please input the category number of currency: "; cin >> this->V; cout << "please input the money: "; cin >> this->N; this->currency = new int[this->V]; cout << "please input the currency in a line:" << endl; for (int i = 0; i < this->V; i++) { cin >> this->currency[i]; } }; int solve() { this->readData(); int* opt = new int[this->N + 1]{0}; opt[0] = 1; sort(this->currency, this->currency + this->V); for (int i = 0; i < this->V; i++) { for (int j = this->currency[i]; j <= this->N; j++) { opt[j] += opt[j - this->currency[i]]; } } int result = opt[this->N]; delete[] opt; cout << result << endl; return result; }};

8 新年趣事之打牌

【問題描述】

過年的時候，大人們最喜歡的活動，就是打牌了。xiaomengxian不會打牌，只好坐在一邊看著。

這天，正當一群人打牌打得起勁的時候，突然有人喊道：「這副牌少了幾張！」眾人一數，果然是少了。於是這副牌的主人得意地說：「這是一幅特製的牌，我知道整副牌每一張的重量。只要我們稱一下剩下的牌的總重量，就能知道少了哪些牌了。」大家都覺得這個辦法不錯，於是稱出剩下的牌的總重量，開始計算少了哪些牌。由於數據量比較大，過了不久，大家都算得頭暈了。

這時，xiaomengxian大聲說：「你們看我的吧！」於是他拿出筆記本電腦，編出了一個程序，很快就把缺少的牌找了出來。

如果是你遇到了這樣的情況呢？你能辦到同樣的事情嗎？

【輸入文件】

第一行一個整數TotalW，表示剩下的牌的總重量。

第二行一個整數N（1<N<=100），表示這副牌有多少張。

接下來N行，每行一個整數Wi（1<=Wi<=1000），表示每一張牌的重量。

【輸出文件】

如果無解，則輸出「0」；如果有多解，則輸出「-1」；否則，按照升序輸出丟失的牌的編號，相鄰兩個數之間用一個空格隔開。

【輸入樣例】

270

4

100

110

170

200

【輸出樣例】

2 4

【問題分析】

如果你認真的做了前面的題，把這個題目抽象成背包問題對你來說應該易如反掌了，我就不多說了。

因為這個問題要求多方案時輸出-1，也就是說要輸出的方案是唯一的，這時你就不需要擔心一維狀態的正確性了，可以放心的用一維求解，但要注意只有當前狀態沒有方案是才記錄當前的方案，否則會把正確方案替換了。

#include<iostream>#include<vector>using namespace std;class Solution {private: int leftTotalW; int N; int* weight; void destroy() { if (this->weight != NULL) delete[] this->weight; this->weight = NULL; };public: Solution() {this->weight = NULL;}; ~Solution() { this->destroy(); }; void readData() { cout << "please input the total weight of the left cards: "; cin >> this->leftTotalW; cout << "please input the number of all the cards: "; cin >> this->N; this->weight = new int[this->N]; cout << "please input the weights of all the cards:" << endl; for (int i = 0; i < this->N; i++) { cout << "please input the weight of the " << i + 1 << "th card: "; cin >> this->weight[i]; } }; vector<int> solve() { this->readData(); int* opt = new int[this->leftTotalW + 1]{0}; opt[0] = 1; int* path = new int[this->leftTotalW + 1]; for (int i = 0; i < this->N; i++) { for (int j = this->leftTotalW; j >= this->weight[i]; j--) { if (opt[j - this->weight[i]] > 0) { if (opt[j] == 0) { path[j] = i ; } opt[j] += opt[j - this->weight[i]]; } } } vector<int> result; if (opt[this->leftTotalW] == 0) { result.push_back(0); } else if (opt[this->leftTotalW] == 1) { bool* flag = new bool[this->N]{ false }; int count = this->leftTotalW; while (count > 0) { flag[path[count]] = true; count -= this->weight[path[count]]; } for (int i = 0; i < this->N; i++) { if (!flag[i]) { result.push_back(i + 1); cout << i + 1 << " "; } } delete[] flag; cout << endl; } else { result.push_back(-1); } delete[] opt; delete[] path; return result; };};

推薦閱讀：