描述
給出 n 個物品, 以及一個陣列, nums[i]代表第i個物品的大小, 保證大小均為正數并且沒有重復, 正整數 target 表示背包的大小, 找到能填滿背包的方案數，
說明
每一個物品可以使用無數次
樣例
- 樣例1
輸入: nums = [2,3,6,7] 和 target = 7
輸出: 2
解釋:
方案有:
[7]
[2, 2, 3]
- 樣例2
輸入: nums = [2,3,4,5] 和 target = 7
輸出: 3
解釋:
方案有:
[2, 5]
[3, 4]
[2, 2, 3]
決議
class Solution:
def backPackIV(self, nums, target):
# write your code here
dp = [[0 for j in range(target+1)] for i in range(len(nums))]
for j in range(target+1):
if j%nums[0] == 0:
dp[0][j] = 1
for i in range(1, len(nums)):
for j in range(0, target+1):
if j >= nums[i]:
k = j - nums[i]
while (k >= 0):
dp[i][j] += dp[i - 1][k]
k = k - nums[i]
dp[i][j] += dp[i-1][j]
return dp[-1][-1]
運行結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/77158.html
標籤：其他
上一篇：關于微信公眾號開發遇到的問題
下一篇：運行代碼時出現Error while building/deploying project mapviewer (kit: Desktop Qt 5.7.1 M