文章目錄

• 1. 完全背包與0-1 背包對比
• 2. 完全背包的排列與組合
• 3. 與LeetCode上與完全背包相關的題目
• • 3.1 [518 零錢兌換②](https://leetcode.cn/problems/coin-change-2/)
  • 3.2[377 組合總和④](https://leetcode.cn/problems/combination-sum-iv/)
  • 3.3 [爬樓梯](https://leetcode.cn/problems/climbing-stairs/)

1. 完全背包與0-1 背包對比

上篇文章闡述了0-1背包問題
這裡做個對比：
0-1背包：物品種類n，每類物品可以選放與不放；
完全背包：物品種類n，每類物品有無限個，可以選放多少個。
完全背包實現的 Python 代碼：

def bagOneDe(bag, weights, values):
""" 和0-1背包不同，遍歷背包重量的時候要正序遍歷 """
nums = len(weights)
dp = [0] * (bag + 1)
for item in range(nums):
for b in range( weights[item],bag):
dp[b] = max(dp[b], dp[b - weights[item]] + values[item])
print(dp)
return dp[-1]

附上測試主函數

if __name__ == '__main__':
bag = 3
weights = [1, 4, 3]
values = [10, 30, 25]
ans = bagOneDe(bag, weights, values)
print(ans)

2. 完全背包的排列與組合

完全背包還可以分為兩種類型：

1. 與物品的順序有關（排列）
   [1,2,1] 和 [1,1,2] 視為兩種方案
2. 與物品的順序無關（組合）
   [1,2,1] 和 [1,1,2] 視為同一種方案

其在代碼上的區別為兩個循環的遍歷順序：

1. 排列問題：先遍歷背包，再遍歷物品
2. 組合問題：先遍歷物品，再遍歷背包

3. 與LeetCode上與完全背包相關的題目

3.1 518 零錢兌換②

分析題目，這裡求的是組合數，即：
[1,2,1] 和 [1,1,2] 視為同一種方案，
故采用先遍歷硬幣，後遍歷金額的方式。
注：初始值 dp[0]賦為1

class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp=[0]*(amount+1)
dp[0]=1
for coin in coins:
for b in range(amount+1):
if coin<=b:
dp[b] +=dp[b-coin]
return dp[-1]

3.2377 組合總和④

分析題目，這裡求的是排列數，即：
[1,2,1] 和 [1,1,2] 視為兩種方案，
故先遍歷總和，後遍歷數組。

class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for b in range(target + 1):
for num in nums:
if num <= b:
dp[b] += dp[b - num]
return dp[-1]

3.3 爬樓梯

走法有兩種：走一步和走兩步，目的是走到第n級台階上。換種表達方式，即用 1 和 2 的步數加和，湊到 n 這個數，記錄方法數。

class Solution:
def climbStairs(self, n: int) -> int:
dp=[0]*(n+1)
nums=[1,2]
dp[0]=1
for b in range(n+1):
for num in nums:
if num<=b:
dp[b]+=dp[b-num]
return dp[-1]