0-1背包問題

問題：有n個物品，第i個物品價值為vi，重量為wi，其中vi和wi均為非負數，背包的容量為W，W為非負數。現需要考慮如何選擇裝入背包的物品，使裝入背包的物品總價值最大。

針對這個經典的動態規劃問題，先建立一個實例，如下表格：

物體編號i12345

價值v	4	5	10	11	13
重量w	3	4	7	8	9

假設約束條件背包的最大承重\(W = 17\)，且每個物體只能裝一次，請問背包應該怎么裝最好。

這一類問題依舊是兩個關鍵：1.初始條件或者最小子問題最優解；2.遞歸定義式或狀態轉移方程。

這里最小子問題最優解應該就是，背包只選一個物品且在限定承重 W' 時所指向的最佳物體。這里 W' 可以為大于等于1的任意值。

那么狀態轉移方程應該就是，在當前給定限定承重條件下，從不同的承重組合選出一個最優解（每一個都是它在限定承重條件下得到的最優解）。用數學定義式可以如下：

\[ dp[i][j] = max(dp[i-1][j], dp[i-1][j-w(k)]+v[k]) \]

其中dp[i][j]表示i件物品放入一個容量為j的背包可以獲得的最大價值。這個式子不是很好理解，舉個例子就很清楚了，如下。

比如當前背包容量是10，那我們可以有多種分配組合，比如9+1，以及7+3。其中dp[i-1][j]可以對應分配的9，dp[i-1][j-w(k)]可以對應分配的7；左邊9所對應的1是再找不出適合裝的東西了，右邊7對應的3可以再裝一個編號1。這個式子的意義就是，比較這兩種組合其中的更佳者。

需要注意的是，不一定永遠是右邊的更佳，有時候空間不全部利用反而能得到更加解。這就是動態規劃的關鍵。

要是直接將動態規劃的代碼寫出來，有時候可能很困難。可以先考慮用遞歸做，再將自頂向下的遞歸轉化為自底向上的動態規劃就好了。這里就不管這些，直接給出動態規劃的代碼了。

class ZeroByOnePack:def __init__(self, list_v, list_w):self.list_v = list_vself.list_w = list_wdef dpPack(n, max_w):V = self.list_vW = self.list_wdp = [0] * (max_w + 1) # 為了形式上好理解，只好浪費一部分空間for i in range(n);for j in range(W[i], max_w + 1):dp[j] = max(dp[j], dp[j-W[i]]+V[i])return dp[max_w]

這里只用一維數組，節省內存空間。

leetcode 132

代碼實現

作業限制了用動態規劃，但其實這道題不用動態規劃也可以做。

class Solution(object):def minCut(self, s):""":type s: str:rtype: int"""cut = [x for x in range(-1,len(s))]for i in range(0,len(s)):for j in range(i,len(s)):if s[i:j] == s[j:i:-1]:cut[j+1] = min(cut[j+1],cut[i]+1)return cut[-1]

當然，這個性能是很差的，時間復雜度應該達到了O(n^3)？如果用動態規劃的話，時間復雜度只要O(n^2)。

class Solution:def minCut(self, s):""":type s: str:rtype: intThis can be solved by:cut[end] is the minimum of cut[st-1] + 1 (st <= end) if [st, end] is palindromea b a | c cst endst-1 | [st, end] is palindromecut(st-1) + 1"""n = len(s)cut = [0] * npal = [[False] * n for row in range(n)]for end in range(n):min_cut = endfor st in range(end + 1):if s[st] == s[end] and (end - st <= 2 or pal[st+1][end-1]):pal[st][end] = Truemin_cut = 0 if st == 0 else min(min_cut, cut[st-1] + 1)cut[end] = min_cutreturn cut[n-1]

代碼不是自己寫的。我只能根據簡單的思路寫出遞歸的算法，但是這道題卡了遞歸的邊界。也許將遞歸算法改進成備忘錄方法會更好點，這個留待以后驗證了。

轉載于:https://www.cnblogs.com/ChanWunsam/p/10246615.html

總結

以上是生活随笔為你收集整理的Datawhale编程——动态规划DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。