@Author：Runsen

@Date：2020/9/15

動態規劃需要搞定三個系列：三個背包，零錢問題和股票問題。今天就開始干掉三個背包問題。

三個背包問題：01背包，多重背包，完全背包。上次搞定了01背包，那么繼續學習完全背包。

我們有$N$種物品，物品$i$的重量為$w[i]$，價格為$p[i]$。我們假定所有物品的重量和價格都是非負的，背包所能承受的最大重量W，每種物品都有無限件可用，則該問題成為完全背包問題 。

題目來源：https://www.acwing.com/problem/content/description/3/

先上代碼，和01背包問題的解法有略微的改動，區別在于遍歷體積$j$時從逆序改為順序，就只有這一個不同，在上一篇博客中有關于01背包問題的理解。

# 代碼基本一樣 n, v = map(int, input().split()) goods = [] for i in range(n):goods.append([int(i) for i in input().split()]) dp = [0 for i in range(v+1)] for i in range(n):for j in range(v+1): # 從前往后if j >= goods[i][0]:dp[j] = max(dp[j], dp[j-goods[i][0]]+goods[i][1]) print(dp[-1])# 測試代碼 5 10 1 2 2 3 3 4 4 5 5 6 20

下面是有關完全背包的題目

Leetcode 279. 完全平方數

給定正整數 n，找到若干個完全平方數（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數的個數最少。示例 1:輸入: n = 12 輸出: 3 解釋: 12 = 4 + 4 + 4. 示例 2:輸入: n = 13 輸出: 2 解釋: 13 = 4 + 9

首先，明確dp，然后找dp的轉移方程。

這里，dp[i]：表示完全平方數和為i的 最小個數。這個是沒有任何問題的，關鍵是dp的轉移方程。

對于Runsen這個菜鳥來說，也很快指的這是轉移方程，就是i減去k 加上1。本質上就是斐波那契數列的一個變形。

$$dp[i]=min(dp(i),dp[i?k]+1)，k指的是平方和的數$$

問題就轉為了求n的最大平方和的序列。

i = 1 nums = [] while i*i <= n:nums.append(i*i)i = i + 1

然后就是完全背包的反例的問題了。那么這個動態規劃的問題基本解決了。

n = int(input()) i = 1 nums = [] while i*i <= n:nums.append(i*i)i = i + 1 print(nums) # dp = [0] * (n+1) 是求最大值，[float('inf')] * (n+1)求最小值 # 如果寫成 dp = [0] * (n+1) ，那么永遠0最小 dp = [float('inf')] * (n+1) dp[0] = 0 for i in range(1,n+1):# j 是平方數for j in nums:if i<j:breakdp[i] = min(dp[i], dp[i - j] + 1) print(dp[-1])

下面代碼來源官方的動態規劃，和Runsen的基本一樣。

import math def numSquares(n):""":type n: int:rtype: int"""square_nums = [i ** 2 for i in range(0, int(math.sqrt(n)) + 1)]dp = [float('inf')] * (n + 1)# bottom casedp[0] = 0for i in range(1, n + 1):for square in square_nums:if i < square:breakdp[i] = min(dp[i], dp[i - square] + 1)return dp[-1]

順便補充一下：四平方定理： 任何一個正整數都可以表示成不超過四個整數的平方之和。 推論：滿足四數平方和定理的數n（四個整數的情況），必定滿足$n=4^a(8b+7)$

這個自己是不知道的，大家想深入：https://leetcode-cn.com/problems/perfect-squares/solution/wan-quan-ping-fang-shu-by-leetcode/

下面是四平方定理的代碼

def numSquares(self, n):""":type n: int:rtype: int"""while n % 4 == 0: n /= 4 if n % 8 == 7: return 4 a = 0 while a**2 <= n: b = int((n - a**2)**0.5) if a**2 + b**2 == n: return (not not a) + (not not b) a += 1 return 3

Leetcode 300 最長上升子序列

給定一個無序的整數數組，找到其中最長上升子序列的長度。

示例:

輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。
說明:

可能會有多種最長上升子序列的組合，你只需要輸出對應的長度即可。
你算法的時間復雜度應該為 O(n2) 。

對于Runsen這個菜鳥來說，關鍵還是怎么找出dp和轉移方程，dp[i]是第i個最長上升子序列。那么

$$dp[i]=max(dp[i],dp[k]+1)其中0<k<i?1$$

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:# 如果定義dp dp[i] 最長上升子序列 那么 dp[i] = max(dp[i], dp[k] + 1) 0<k<i-1m = len(nums)if m <= 1:return mdp = [ 1 for _ in range(m)]for i in range(1,m):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j]+ 1 ) return max(dp)

Leetcode 322 零錢兌換

給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1。

示例 1:

輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例 2:

輸入: coins = [2], amount = 3
輸出: -1

零錢兌換實際上就是完全背包的題目，也可以看作下樓梯的問題的變種

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:# 第一步：定義dp數組或變量，首先明確題目說每種硬幣的數量是無限的，但是會給定一個固定的 amount 金額，我們需要用最少的硬幣數湊出這個金額，如果是01背包問題就是[0]開始；# 因此這個是一個完全背包的題目，還是下樓梯的問題的變種。完全背包求最小，那么初始就要時最大dp = [float('inf')] * (amount + 1)# 計算的起點 0 塊錢當然是 0dp[0] = 0# 狀態轉移方程： f(11) = min(f(10),f(9),f(6)) + 1 for i in range(amount + 1):for j in coins:if i-j >=0 :dp[i] = min(dp[i],dp[i-j] + 1 )if dp[amount] > amount:# 如果dp[amount] 是amount + 1 ，說明了沒有匹配的方式return -1return dp[-1]

至此完全背包就到這里結束了，完全背包注意dp的定義，求最大還是最小，完全背包的關鍵詞就次數是無限的

總結

以上是生活随笔為你收集整理的八十九、动态规划系列背包问题之完全背包的全部內容，希望文章能夠幫你解決所遇到的問題。

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