leetcode-动态规划【背包问题】

这篇具有很好参考价值的文章主要介绍了leetcode-动态规划【背包问题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

背包问题篇:

基础背包:

416. 分割等和子集

1049. 最后一块石头的重量ii

494. 目标和

474. 一和零

完全背包:

518. 零钱兑换ii

377. 组合总和iv

70. 爬楼梯

322. 零钱兑换

279. 完全平方数

139. 单词拆分

多重背包:


0-1背包:(所有元素只能放入一次)

n件物品和最大承受重量为w的背包,其中第i件物品的重量是weight[i],得到的价值是value[i],每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。

1. 确定dp数组以及下标的含义

dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。i:物品编号,j:背包容量,dp[i][j]:价值总和

leetcode-动态规划【背包问题】

2. 确定递推公式

  • 不放物品i:由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时,物品i无法放进背包中,所以被背包内的价值依然和前面相同。)
  • 放物品i:由dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最大价值

递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. dp数组初始化

dp[i][0]:背包容量为0因此价值总和为0

dp[0][j]:存放物品0的时候背包价值总和,当j<weight[0]价值总和为0,其余情况价值总和为value[0]

4. 确定遍历顺序:先遍历物品/背包重量

5. 举例推导dp数组

416. 分割等和子集

leetcode-动态规划【背包问题】

leetcode-动态规划【背包问题】

leetcode-动态规划【背包问题】

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if sum(nums) % 2: return False
        # 要求找到元素和为sum/2的子集
        target = sum(nums) // 2
        # dp[i][j]代表可装物品为0-i,背包容量为j的情况下,背包内容量的最大价值(最大子集和)
        dp = [[0 for _ in range(target+1)] for _ in range(len(nums))]
        # 背包容量为0且只能放入nums[i]的情况下背包最大价值(最大子集和)
        for j in range(nums[0],target+1):
            dp[0][j] = nums[0]
        # 递推公式(每行从左到右遍历)
        for i in range(1, len(nums)):
            for j in range(1, target+1):
                # 当背包不能容纳nums[i]时
                if j < nums[i]:
                    dp[i][j] = dp[i-1][j]
                # 当背包可以容纳nums[i]时
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i])
        return dp[-1][-1] == target

使用滑动数组:

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums or sum(nums) % 2: return False
        target = sum(nums) // 2
        # 滑动数组(因为只需要保留上一行的值因此可以使用一维数组)
        dp = [0 for _ in range(target+1)]
        for i in range(len(nums)):
            for j in range(target, nums[i]-1, -1):
                dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])
        return dp[-1] == target

1049. 最后一块石头的重量ii

leetcode-动态规划【背包问题】

class Solution(object):
    def lastStoneWeightII(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        # 将stones分为重量差不多的两堆
        target = sum(stones) // 2
        # dp设为滑动数组,dp[j]存储最接近重量j其不超过的石头总重量
        dp = [0 for _ in range(target+1)]
        # 遍历stones
        for i in range(len(stones)):
            for j in range(target, stones[i]-1, -1):
                dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
        return sum(stones)-2*dp[-1]

494. 目标和

leetcode-动态规划【背包问题】

class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) == 1 and nums[0] != target and nums[0] != -1 * target:
            return 0
        sum_nums = sum(nums)
        if target > sum_nums or target < -1 * sum_nums: return 0
        # dp[][sum_nums]为中心点
        dp = [[0 for _ in range(2*sum_nums+1)] for _ in range(len(nums))]
        for j in range(2*sum_nums+1):
            if abs(j - sum_nums) == nums[0]:
                if nums[0] == 0: dp[0][j] = 2
                else: dp[0][j] = 1
        for i in range(len(nums)-1):
            for j in range(2*sum_nums+1):
                if dp[i][j] == 0: continue
                dp[i + 1][j - nums[i + 1]] += dp[i][j]
                dp[i + 1][j + nums[i + 1]] += dp[i][j]
        return dp[-1][target+sum_nums]

第二种方法:

假设nums = [3,1,2,5,4],此时选3和1前面的符号为加号,其余为减号,那么此时加法获得的和为3+1=4,减法获得的和为2+5+4=11,也可以通过sum(nums)-3-1=15-3-1=11获得。以此类推,设加法获得的和为x,则减法获得的和为(sum-x),问题转化满足x-(sum-x)=target / x=(sum+target)/2有几种方案。

class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        sum_nums = sum(nums)
        # 注意边界条件
        if abs(target) > sum_nums or (sum_nums + target) % 2 == 1: return 0
        bagSize = (sum_nums + target) // 2
        dp = [0] * (bagSize + 1)
        dp[0] = 1
        for i in range(len(nums)):
            for j in range(bagSize, nums[i] - 1, -1):
                dp[j] += dp[j - nums[i]]
        return dp[bagSize]

474. 一和零

leetcode-动态规划【背包问题】

dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]

class Solution(object):
    def findMaxForm(self, strs, m, n):
        """
        :type strs: List[str]
        :type m: int
        :type n: int
        :rtype: int
        """
        # dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for str in strs:
            onenum = str.count('1')
            zeronum = str.count('0')
            for i in range(m, zeronum-1, -1):
                for j in range(n, onenum-1, -1):
                    dp[i][j] = max(dp[i][j], dp[i-zeronum][j-onenum] + 1)
        return dp[m][n]

完全背包:(元素可以重复放入)

518. 零钱兑换ii

leetcode-动态规划【背包问题】

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        # dp[i][j]表示coins[i]的面值加入排列后,总和为amount的组合数
        dp = [0 for _ in range(amount+1)]
        dp[0] = 1
        for i in range(len(coins)):
            for j in range(coins[i], amount+1):
                dp[j] += dp[j-coins[i]]
        return dp[-1]

377. 组合总和iv

leetcode-动态规划【背包问题】

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        dp = [0 for _ in range(target+1)]
        dp[0] = 1
        for j in range(target+1):
            for i in range(len(nums)):
                if j-nums[i] >= 0:
                    dp[j] += dp[j-nums[i]]
        return dp[-1]

70. 爬楼梯

leetcode-动态规划【背包问题】

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        for j in range(n+1):
            for step in range(1,3):
                if j - step >= 0:
                    dp[j] += dp[j-step]
        return dp[-1]

322. 零钱兑换

leetcode-动态规划【背包问题】

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for coin in coins:
            for j in range(coin, amount + 1):
                dp[j] = min(dp[j], dp[j - coin] + 1)
        if dp[amount] < amount + 1:
            return dp[amount]
        else:
            return -1

279. 完全平方数

leetcode-动态规划【背包问题】

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        square, i = [], 1
        while i**2 <= n:
            square.append(i**2)
            i += 1

        dp = [n+1] * (n+1)
        dp[0] = 0
        for i in range(len(square)):
            for j in range(square[i], n+1):
                dp[j] = min(dp[j], dp[j-square[i]]+1)
        if dp[n] > n+1:
            return -1
        else:
            return dp[n]

139. 单词拆分

leetcode-动态规划【背包问题】文章来源地址https://www.toymoban.com/news/detail-403123.html

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        # dp[j]=1即截至此处s[:j+1]可划分,dp[j]=0即不可划分
        dp = [0 for _ in range(len(s)+1)]
        dp[0] = 1
        for j in range(1, len(s)+1):
            for word in wordDict:
                if j >= len(word):
                    dp[j] = dp[j] or (dp[j - len(word)] and word == s[j - len(word):j])
        return dp[-1] == 1

多重背包:

到了这里,关于leetcode-动态规划【背包问题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode动态规划#06】分割等和子集(01背包问题一维写法实战)

    分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 示例 2: 输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割

    2023年04月09日
    浏览(62)
  • acwing算法基础之动态规划--背包问题

    (零) 背包问题描述:有 N N N 个物品,每个物品的体积是 v i v_i v i ​ ,价值是 w i w_i w i ​ ,现有容量是 V V V 的背包,求这个背包能装下的物品的最大价值。 01背包问题:每个物品只有1个。 完全背包问题:每个物品有无穷多个。 多重背包问题:第 i i i 个物品有 s i s_i s

    2024年02月05日
    浏览(45)
  • 【LeetCode动态规划#10】完全背包问题实战,其三(单词拆分,涉及集合处理字符串)

    力扣题目链接(opens new window) 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明: 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1: 输入: s = \\\"leetcode\\\", wordDict = [\\\"lee

    2023年04月20日
    浏览(58)
  • 【LeetCode动态规划#07】01背包问题一维写法(状态压缩)实战,其二(目标和、零一和)

    力扣题目链接(opens new window) 难度:中等 给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 示例: 输入

    2023年04月18日
    浏览(60)
  • 代码随想录 Day35 动态规划04 01背包问题和完全背包问题 LeetCode T416 分割等和子集

    说到背包问题大家都会想到使用动规的方式来求解,那么为什么用动规呢, dp数组代表什么呢 ? 初始化是什么 , 遍历方式又是什么 ,这篇文章笔者将详细讲解背包问题的经典例题0-1背包问题和完全背包问题的解题方式,希望能帮助到大家 有人一提到背包问题就只会使用动态规划来

    2024年02月06日
    浏览(71)
  • Python 算法基础篇:背包问题的动态规划解法

    背包问题是计算机科学中一个重要的组合优化问题,动态规划是解决该问题的高效算法技术。本篇博客将重点介绍背包问题的动态规划解法,包括状

    2024年02月16日
    浏览(39)
  • 算法基础复盘笔记Day09【动态规划】—— 背包问题

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2023年04月22日
    浏览(46)
  • Acwing-基础算法课笔记之动态规划(背包问题)

    01背包中的0和1指的是放与不放,而且不能出现放多个的情况,背包只能放相同物品中的一个; 首先是对 d [ i ] [ j ] d[i][j] d [ i ] [ j ] 数组的解释,该数组表示的是只看前 i i i 个物品,总体积是 j j j 的情况下,总价值最大是多少; 不选第 i i i 个物品,只考虑前 i − 1 i-1 i −

    2024年04月17日
    浏览(47)
  • 【LeetCode动态规划#08】完全背包问题实战与分析(零钱兑换II--求组合、组合总和IV--求排列)

    力扣题目链接(opens new window) 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3

    2023年04月19日
    浏览(40)
  • 动态规划-背包问题-完全背包

    对比01背包,完全背包中的每件物品有无数件。 也就是说,每件物品可以拿0,1,…,k,…件。 dp[i][j]表示前i种物品,体积为j时的最大价值 对于第i件物品: 不拿:dp[i][j]⇐dp[i-1][j] 拿一件:dp[i][j]⇐dp[i-1][j-w[i]]+v[i] 拿两件:dp[i][j]⇐dp[i-1][j-2w[i]]+2v[i] … 拿k件:dp[i]][j]⇐dp[i

    2024年04月08日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包