网站广告费怎么做分录,做网站的销售怎么样,京山网站开发,dede新手做网站多久52. 携带研究材料#xff08;第七期模拟笔试#xff09; (kamacoder.com)
完全背包#xff0c;可重复放入物品#xff0c;需要用一维滚动数组从前往后遍历。
由于第0个物品和后面物品的转移方程没有区别#xff0c;可以不额外初始化dp数组#xff0c;直接用元素全0的d…52. 携带研究材料第七期模拟笔试 (kamacoder.com)
完全背包可重复放入物品需要用一维滚动数组从前往后遍历。
由于第0个物品和后面物品的转移方程没有区别可以不额外初始化dp数组直接用元素全0的dp从第0个物品开始遍历。
class solution:def maxval(self, capacity, luggages):dp [0 for _ in range(capacity 1)]for i in range(len(luggages)):w luggages[i][0]v luggages[i][1]for j in range(w, capacity1):dp[j] max(dp[j], v dp[j-w])return dp[-1]if __name__ __main__:N, capacity map(int, input().split())luggages []for i in range(N):cur list(map(int, input().split()))luggages.append(cur)res solution().maxval(capacity, luggages)print(res) 518. 零钱兑换 II - 力扣LeetCode
dp初始化为了避免dp元素始终为0令dp[0]1其余0。* amount 0时空集不算一种组合所以不能将dp所有元素初始化为1。当coins[i]不大于当前上限j进入第二层循环想象coins[0]j的情况dp[j] 01 1这个组合数是合理的。
由于物品可重复从前向后遍历滚动数组。求组合数累加。
class Solution:def change(self, amount: int, coins: List[int]) - int:dp [0 for _ in range(amount1)] #dp[j]:不超过j金额且尽和可能大的组合数dp[0] 1for i in range(len(coins)):for j in range(coins[i], amount1):dp[j] dp[j-coins[i]]return dp[-1]
先遍历物品再遍历背包上限组合数 先遍历背包上限再遍历物品排列数 377. 组合总和 Ⅳ - 力扣LeetCode
求排列数需要先遍历target再遍历物品。
class Solution:def combinationSum4(self, nums: List[int], target: int) - int:dp [0 for _ in range(target1)]dp[0] 1for j in range(target1):for num in nums:if j num:dp[j] dp[j-num]return dp[-1] 57. 爬楼梯第八期模拟笔试 (kamacoder.com)
class sol:def ways(self, n, m):dp [0 for _ in range(n1)]dp[0] 1 for j in range(n1):for i in range(1, m1):if j i:dp[j] dp[j-i]return dp[-1]if __name__ __main__:n, m map(int, input().split())res sol().ways(n, m)print(res)
