0/1背包問題回溯法求解
愛玩游戲的Tom
Tom很喜歡玩游戲，他在電腦上下了《GTA5》和《微軟飛行模擬》，對于后者他還喪心病狂的下載了所有地圖包，導致他可用空間只有mGB，但他還有幾個學校要求安裝的軟體沒有下載，他不能全部放下去，因此只能選擇性的安裝一部分，現在，我們知道每個學習軟體的大小以及該學習軟體的重要程度，現在Tom找到你，應該安裝哪一些軟體，使得這些軟體的重要程度之和最大，對于輸入第一行有n（0 < n <= 100）和m(0 < m <= 1000)兩個整陣列成，n代表接下來的輸入行數，m代表可用空間還剩mGB，接下來的n行，每行兩個整數，前一個整數為每個學習軟體的大小（GB），后一個整數代表重要程度，對于輸出，只有一行，即為最大重要程度之和，
樣例
Input：
3 23
15 9
20 5
7 7
Output：
16
下面我們來切掉這道裸題：首先我們定義一個函式，名字索性為dfs，
組成：int dfs(int i,int j)
解釋：引數i表示一共有多少件物品，體現在本題中便是多少個軟體，引數j則表示電腦還剩的空間（GB），
dfs(i,j)的回傳值所代表的意思便是，一共i個軟體，在電腦記憶體還剩jGB的情況下最大的重要程度，
經過上面的定義，我們顯然可以得到？
就上面的問題，我們留意前面dfs的定義，不難得出對于0個軟體，不管我們電腦還剩多少記憶體，它對于我們來說重要程度都為0，因為根本就沒有軟體，
這就是邊界（i==0），同時也是終止條件，
我們在回過頭看上面的程式，很遺憾，如果寫成這樣，當資料規模為最大，即當n=100的時候，程式無法在1秒內得出答案，最后超時，不予通過，指數級的時間復雜度太高了，需要降（一個狀態可能會被計算多次），
如何去降？
對于回溯，降低時間復雜度的有效方式是減枝，前面我們說過，一個狀態可能會被計算多次，那么我們便想方設法讓他只計算一次，
下面引出記憶式遞回
記憶式遞回：一個狀態已經被求解的情況下記住它，這也是人工智能中經常可以用到的（尤其是在機器學習中）
試思考：在本題中，我們如何讓程式去“記住”解的狀態？
顯然，讓我們寫的程式具備記憶功能似乎不可能，但是這實際是可行的，至少在本題中是如此，
具體如下：
我們開一個輔助陣列：spackSpace[i][j]
解釋是共i個軟體，裝進記憶體為j的電腦中最大的重要程度，初始化所有元素為0，如果當計算的時候其值為0，則代表程式沒有計算過該狀態，否則便是計算過，那么無需重復計算（剪枝+記憶），直接回傳spackSpace[i][j]便是，
具體實作如下（記得先思考）：
完整程式：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/234205.html
標籤：其他