八十九、動態(tài)規(guī)劃系列背包問題之完全背包
「@Author：Runsen」
動態(tài)規(guī)劃需要搞定三個系列：三個背包，零錢問題和股票問題。今天就開始干掉三個背包問題。
三個背包問題：01背包，多重背包，完全背包。上次搞定了01背包，那么繼續(xù)學習完全背包。
我們有種物品，物品的重量為，價格為。我們假定所有物品的重量和價格都是非負的，背包所能承受的最大重量W，每種物品都有無限件可用，則該問題成為完全背包問題 。
題目來源：https://www.acwing.com/problem/content/description/3/
先上代碼，和01背包問題的解法有略微的改動，區(qū)別在于「遍歷體積時從逆序改為順序」，就只有這一個不同，在上一篇博客中有關于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. 完全平方數(shù)
給定正整數(shù) n，找到若干個完全平方數(shù)（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個數(shù)最少。
示例 1:
輸入: n = 12
輸出: 3
解釋: 12 = 4 + 4 + 4.
示例 2:
輸入: n = 13
輸出: 2
解釋: 13 = 4 + 9
首先，明確dp，然后找dp的轉(zhuǎn)移方程。
這里，dp[i]：表示完全平方數(shù)和為i的 最小個數(shù)。這個是沒有任何問題的，關鍵是dp的轉(zhuǎn)移方程。
對于Runsen這個菜鳥來說，也很快指的這是轉(zhuǎn)移方程，就是i減去k 加上1。本質(zhì)上就是斐波那契數(shù)列的一個變形。
「問題就轉(zhuǎn)為了求n的最大平方和的序列。」
i = 1
nums = []
while i*i <= n:
nums.append(i*i)
i = i + 1
然后就是完全背包的反例的問題了。那么這個動態(tài)規(guī)劃的問題基本解決了。
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 是平方數(shù)
for j in nums:
if i<j:
break
dp[i] = min(dp[i], dp[i - j] + 1)
print(dp[-1])
下面代碼來源官方的動態(tài)規(guī)劃，和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 case
dp[0] = 0
for i in range(1, n + 1):
for square in square_nums:
if i < square:
break
dp[i] = min(dp[i], dp[i - square] + 1)
return dp[-1]
順便補充一下：「四平方定理」：任何一個正整數(shù)都可以表示成不超過四個整數(shù)的平方之和。推論：滿足四數(shù)平方和定理的數(shù)n（四個整數(shù)的情況），必定滿足
這個自己是不知道的，大家想深入：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 最長上升子序列
給定一個無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度。
示例:
輸入: [10,9,2,5,3,7,101,18] 輸出: 4 解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。說明:
可能會有多種最長上升子序列的組合，你只需要輸出對應的長度即可。你算法的時間復雜度應該為 O(n2) 。
對于Runsen這個菜鳥來說，關鍵還是怎么找出dp和轉(zhuǎn)移方程，dp[i]是第i個最長上升子序列。那么
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# 如果定義dp dp[i] 最長上升子序列 那么 dp[i] = max(dp[i], dp[k] + 1) 0<k<i-1
m = len(nums)
if m <= 1:
return m
dp = [ 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。編寫一個函數(shù)來計算可以湊成總金額所需的最少的硬幣個數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回 -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數(shù)組或變量，首先明確題目說每種硬幣的數(shù)量是無限的，但是會給定一個固定的 amount 金額，我們需要用最少的硬幣數(shù)湊出這個金額，如果是01背包問題就是[0]開始；
# 因此這個是一個完全背包的題目，還是下樓梯的問題的變種。完全背包求最小，那么初始就要時最大
dp = [float('inf')] * (amount + 1)
# 計算的起點 0 塊錢當然是 0
dp[0] = 0
# 狀態(tài)轉(zhuǎn)移方程：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 -1
return dp[-1]
「至此完全背包就到這里結(jié)束了，完全背包注意dp的定義，求最大還是最小，完全背包的關鍵詞就次數(shù)是無限的」
更多的文章
點擊下面小程序
- END -