代码编织梦想

_36LeetCode代码随想录算法训练营第三十六天-动态规划背包问题

题目列表

  • 01背包问题,你该了解这些!
  • 01背包问题,你该了解这些!滚动数组
  • 416.分割等和子集

代码随想录地址

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html

https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html

01背包问题,你该了解这些!

背包问题分类

背包问题的经典资料当然是:背包九讲,已经下载,是竞赛级别的,学有余力计划去看看。

标准背包问题

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

举例:

背包最大重量为4。

物品为:

重量价值
物品0115
物品1320
物品2430

问背包能背的物品最大价值是多少?

在这里插入图片描述

背包问题暴力解法

每一件物品其实只有两个状态,取或者不取,所以可以使用回溯法搜索出所有的情况,那么时间复杂度就是 o ( 2 n ) o(2^n) o(2n),这里的n表示物品数量。(这种方式在力扣上面会超时)

动态规划解决背包问题

思路

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

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

在这里插入图片描述

  • 确定递推公式

此递推公式的前提为:重量越大,价值越高。

不放物品i:背包容量为j,当物品i的重量大于背包j的重量时,物品i无法放进背包中,此时dp[i] [j]就是dp[i - 1] [j]。

放物品i:背包容量为j,当物品i的重量小于等于背包j的重量时,物品i可以放进背包中;当物品i的重量等于背包的容量时,直接将物品i放进背包即可获得最大价值;当物品i的重量小于背包的容量时,为了将背包尽量塞满,就要找到背包的容量为j - weight[i]时的最大价值,然后加上value[i]即可获得价值最大值。

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

  • 初始化dp

1.当背包容量为0时,背包价值总和一定为0;此时需要初始化背包为0时的所有dp。

2.状态转移方程 dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来,那么i为0的时候就一定要初始化。

当 j < weight[0]的时候,dp[0] [j] 应该是 0。

当j >= weight[0]时,dp[0] [j] 应该是value[0],因为背包容量放足够放编号0物品。

3.其他的dp元素可以根据递推公式求得。

在这里插入图片描述

  • 遍历顺序

两个遍历的维度:物品与背包重量。

本题中先遍历物品和先遍历背包重量都可以,主要根据递推公式来判断。

代码

void test_2_wei_bag_problem1() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagweight = 4;

    // 二维数组 全部初始化为0
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

    // 初始化 第一行
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    // weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        //此处为什么不从j = weight[i]开始,因为需要将j<weight[i]的dp[i][j]复制过去
        for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];//防止溢出数组
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }

    cout << dp[weight.size() - 1][bagweight] << endl;
}

int main() {
    test_2_wei_bag_problem1();
}

02背包问题,你该了解这些!滚动数组

思路

对于二维背包问题,其实完全可以用一维数组解决问题。

使用二维数组的时候,递推公式:dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上,表达式完全可以是:dp[i] [j] = max(dp[i] [j], dp[i] [j - weight[i]] + value[i]);

与其把dp[i - 1]这一层拷贝到dp[i]上,不如只用一个一维数组了,只用dp[j](一维数组,也可以理解是一个滚动数组)。

动态规划五部曲

  • 确定dp数组的定义

在一维dp数组中,dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]。

  • 一维dp数组的递推公式

根据二维背包问题的递推公式,将前一层变为当前层即可。

所以递推公式为:

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  • 一维dp数组如何初始化

将所有元素初始化为0。根据递推公式可知,每次更新dp元素,都会将其与自己相比并且取较小值,因此初始化dp数组时应该将其赋值为正数的最小值,以减少干扰。

  • 一维dp数组遍历顺序

两层for循环,一层背包,一层物品,如何确定先遍历背包还是先遍历物品?

如何确定从大到小遍历还是从小到大遍历?

如果一层循环遍历物品,二层循环遍历背包,是可以的,但是在遍历背包时需要倒叙遍历,是为了防止一个物品加入多次

如果一层循环遍历背包,二层循环遍历物品:对于滚动数组,每个容量下的背包都只会装一个物品,原因是对于背包一定是倒序遍历的。这种遍历方式是不正确的。

  • 举例推导dp数组

这个就自己心算了。

代码

#include<iostream>
#include<vector>
using namespace std;

void test_1_wei_bag_problem() {
    vector<int> weight = { 1, 3, 4 };
    vector<int> value = { 15, 20, 30 };
    int bagWeight = 4;

    // 初始化
    vector<int> dp(bagWeight + 1, 0);
    for (int i = 0; i < weight.size(); i++) { // 遍历物品
        //这里为什么可以到j >= weight[i]结束,因为一维数组不需要复制了
        for (int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}

int main() {
    test_1_wei_bag_problem();
}

416.分割等和子集

题目

给你一个 只包含正整数非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

示例 1:

输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2:

输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。

提示:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

思路

分析

  • 背包的体积为sum / 2
  • 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
  • 背包如果正好装满,说明找到了总和为 sum / 2 的子集。
  • 背包中每一个元素是不可重复放入。

动规五部曲:

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

01背包中,dp[j] 表示: 容量为j的背包,所背的物品价值最大可以为dp[j]。

  • 确定递推公式

递推公式:dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

  • dp数组如何初始化

首先dp[0]一定是0,因为容量为0的背包所背物品价值最大可以为0。

如果题目给的价值都是正整数那么非0下标都初始化为0就可以了,如果题目给的价值有负数,那么非0下标就要初始化为负无穷。

这样才能让dp数组在递推的过程中取得最大的价值,而不是被初始值覆盖了

  • 确定遍历顺序

动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中就已经说明:如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!

  • 举例推导dp数组

如果dp[j] == j 说明,集合中的子集总和正好可以凑成总和j,理解这一点很重要。

代码

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(n),虽然dp数组大小为一个常数,但是大常数
/*
 * @lc app=leetcode.cn id=416 lang=cpp
 *
 * [416] 分割等和子集
 */

// @lc code=start
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        //因为是分为两组,因此求得target表示其中一组元素的总和
        int sum = 0;
        for(int data : nums)
            sum += data;
        //如果sum/2会得小数,那么肯定不可能分为两组
        if(sum % 2 == 1)
            return false;
        int target = sum / 2;
        //dp数组定义及其初始化
        vector<int> dp(target + 1, 0);
        //遍历物品和背包
        for(int i = 0; i < nums.size(); i++)//遍历物品,其实就是nums中的元素
            for(int j = target; j >= nums[i]; j--)//遍历背包
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        if(dp[target] == target)
            return true;
        else
            return false;
    }
};
// @lc code=end
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44410704/article/details/128792796

代码随想录算法训练营第四十四天| leetcode518. 零钱兑换 ii 377. 组合总和 Ⅳ_冰冰的coco的博客-爱代码爱编程

完全背包 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件 //01背包核心代码 for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背

代码随想录算法训练营第四十五天| leetcode70. 爬楼梯 322. 零钱兑换 79.完全平方数_冰冰的coco的博客-爱代码爱编程

70. 爬楼梯 (进阶) 题目:力扣 class Solution { public: int climbStairs(int n) { vector<int> dp(n+1,0); dp[0] = 1; for(int j = 1; j &l

代码随想录算法训练营第44天 | 完全背包理论基础 518. 零钱兑换 ii 377. 组合总和 Ⅳ_lebowskii的博客-爱代码爱编程

代码随想录系列文章目录 动态规划篇 - 完全背包 文章目录 代码随想录系列文章目录完全背包理论基础518. 零钱兑换 II377. 组合总和 Ⅳ 完全背包和01背包不同之处就在于, 完全背包的内层遍

代码随想录算法训练营第四十六天| leetcode70. 爬楼梯 322. 零钱兑换 79.完全平方数_冰冰的coco的博客-爱代码爱编程

139.单词拆分 题目: class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordSet(wordDic

代码随想录算法训练营day47 | 背包总结_jzh013的博客-爱代码爱编程

在讲解背包问题的时候,我们都是按照如下五部来逐步分析,相信大家也体会到,把这五部都搞透了,算是对动规来理解深入了。 确定dp数组(dp table)以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 其实这五部里哪一步都很关键,但确定递推公式和确定遍历顺序都具有规律性和代表性,所以下面我从这两点来对背包问题做一做总结。 #背包递推

代码随想录算法训练营第四十二天| leetcode416. 分割等和子集_喵的博客-爱代码爱编程

一、LeetCode416. 分割等和子集         1:题目描述(416. 分割等和子集)         给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。         2:解题思路         本题需要使用01背包的解题思路         什么事01背

代码随想录算法训练营第四十四天| leetcode518. 零钱兑换 ii、leetcode377. 组合总和 Ⅳ_喵的博客-爱代码爱编程

一、LeetCode518. 零钱兑换 II         1:题目描述(518. 零钱兑换 II)         给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。         请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。         假设每一种面额的

代码随想录算法训练营第四十五天| leetcode70. 爬楼梯、leetcode322. 零钱兑换、leetcode279. 完全平方数_喵的博客-爱代码爱编程

一、LeetCode70. 爬楼梯         1:题目描述(70. 爬楼梯)         假设你正在爬楼梯。需要 n 阶你才能到达楼顶。         每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?         2:解题思路 class Solution: def climbStairs(sel

代码随想录算法训练营第42天 | 01背包问题 416. 分割等和子集-爱代码爱编程

01背包问题 由于leetcode上没原题,故参考卡哥意见自己编题记录一下。 一、题干 背包最大重量为4。物品为: 物品名称重量价值011513202430––– 问背包能背的物品最大价值是多少? 二、解法 二维d

代码随想录算法训练营第四十二天| 第九章 动态规划:01背包问题二维,01背包问题一维,416.分割等和子集(python)-爱代码爱编程

目录 01背包问题二维 01背包问题一维 416.分割等和子集 01背包问题二维 视频讲解链接 文字讲解链接 问题描述:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。 def bagproblem1(bag

代码随想录算法训练营day42| 01背包问题:416. 分割等和子集-爱代码爱编程

416. 分割等和子集 题目链接 思路:01背包问题:参考代码随想录 代码: class Solution { public boolean canPartition(int[] nums) {

代码随想录算法训练营第四十二天-爱代码爱编程

01背包问题 二维 视频讲解https://www.bilibili.com/video/BV1cg411g7Y6文章讲解https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83

java练习29-爱代码爱编程

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 一、题目-只出现一次的数字 1.题目描述 2.思路与代码 2.1 思路 2.2 代码 总结 前言 提示:这里可以添加本文要记录的大概内容: 1月23日练习内容 提示:以下是本篇文章正文内容,下面案例可供参考 一、题目-只出现一次的数字

代码随想录算法训练营第五十天-爱代码爱编程

LeetCdoe 139.单词拆分         给你一个非空字符串 s 和一个包含非空单词的列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意:         不要求字典中出现的单词全部都使用,并且字典中的单词可以 重复使用;         字典中没有重复的单词。

代码随想录算法训练营第四十六天|● 139.单词拆分 ● 关于多重背包,你该了解这些! ● 背包问题总结篇!-爱代码爱编程

动态规划: 一、139.单词拆分 题目: 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明: 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1: 输入: s = "leetcode", wordDict =

【代码随想录训练营】day42-爱代码爱编程

代码随想录训练营 Day42 今日任务 01背包问题二维 01背包问题一维 416.分割等和子集 语言:Java 背包问题辨析 01背包:物品只有一个 完全背包:物品有无数个 多重背包:不同的物品数量不同 分组背包:

代码随想录算法训练营-爱代码爱编程

01背包相关知识 相关基础知识移步链接: 416. 分割等和子集 学习文章链接:思路:两个子集的相等,那目标值肯定是数组值和的一半。我们只要判断只是否有子集和为目标值即可,这就可以搬出01背包啦!!!详情见代码和注释!

代码随想录算法训练营第四十二天|背包问题 416. 分割等和子集-爱代码爱编程

背包问题基础知识 详见代码随想录背包理论基础。 416. 分割等和子集 将这个问题套入0-1背包模板,数组的元素就是物品的重量和价值,首先将数组的和求出来,然后除以2就是所需要的target,也就是背包的容量 dp数

代码随想录训练营第42天|01背包问题、leetcode 416. 分割等和子集-爱代码爱编程

参考 代码随想录 01背包问题 01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2至Wn,与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物

代码随想录算法训练营第四十六天| leetcode139. 单词拆分-爱代码爱编程

一、LeetCode139. 单词拆分         1:题目描述(139. 单词拆分)         给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。         注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。         2:解题思路