代码随想录算法训练营DAY42|C++动态规划Part4|0-1背包理论基础(一)、0-1背包理论基础之滚动数组(二)、416.分割等和子集

文章目录

  • 0-1背包理论基础(一)
    • 前置知识
    • 01背包
    • 动态规划:01背包
      • 二维dp数组
    • CPP代码
    • 再论01背包的遍历顺序
  • 0-1背包理论基础(二)
    • 一维dp数组如何初始化
    • 一维dp数组遍历顺序
    • 举例推导dp数组
    • CPP代码
  • 416.分割等和子集
    • 思路
      • 将题目抽象成0-1背包问题
    • CPP代码

0-1背包理论基础(一)

卡码网第46题

文章讲解:0-1背包理论基础(一)

视频讲解:带你学透0-1背包问题!

背包问题经典资料:背包九讲。卡哥文章里说:“对于面试的话,其实掌握01背包,和完全背包,就够用了,最多可以再来一个多重背包。”

前置知识

背包问题的各种分类:

在这里插入图片描述

在笔试面试中,基本搞清楚01背包和完全背包即可,在后续的文章中会简单讨论多重背包问题。

其中,完全背包问题从图中也可以看出,是由01背包问题演化而来。

01背包

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

首先我们思考用暴力解法

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

动态规划:01背包

假设背包最大重量是4,即 bagweight = 4

并在下文的叙述中,背包当前允许重量表示当前背包最高允许的重量(可能是0,1,2,3,4),背包容量表示背包的最大重量4

weightvalue
物品0115
物品1320
物品2430

二维dp数组

在后文中,我们会介绍一维dp数组的解法

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

对于背包问题,有一种写法, 是使用二维数组,即**dp[i][j] 表示从下标为[0-i]的物品里任意取,放进当前允许重量为j的背包(j <= bagweight),价值总和最大是多少**。

可视化:

  • 确定递推公式

    思考一下,我们可以从那两个方向推导出来dp[i][j]呢?(注意:物品只有1个,放完就没有了喔)

    • 一个是从上面格子[i-1][j]推导下面格子[i][j]——放不下物品i
      • dp[i - 1][j]推出,即背包当前允许重量j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j当前允许重量时,物品i无法放进背包中,所以背包内的价值依然和前面相同。)
    • 一个是从左上角的某个格子推导出[i][j]格子——能放下物品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得到的最大价值

    综上所述有两个递推公式:

    满足 j < weight[i]时,意味着放不下idp[i][j]=dp[i-1][j]

    满足j >= weight[i]时:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

  • dp数组输入初始化

    关于初始化,一定要和dp数组的定义温和,否组到递推公式的时候就会越来越乱

    1. 首先可以敲定,如果背包容量j为0的话,背包价值总和一定是0:
  1. 如果背包容量j < weight[0],也就是说背包根本装不下物品0,那么dp[0][j]当然也全部都是0;
  2. 如果背包 j >= weight[0],那么就是说背包能把物品零装下了,则初始化为dp[0][j],其值为value[0]
for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步,如果把dp数组预先初始化为0了,这一步就可以省略,但很多同学应该没有想清楚这一点。
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

初始化完成后,结果为:

剩下的格子,初始化为多少都无所谓,因为剩下的格子应该是在运行时推导填写出来的,这里为了处理方便,先初始化为0。总体的初始化代码如下:

// 初始化 dp
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++) { // 遍历物品
        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]);
    
        }
    }
    
    // weight数组的大小 就是物品个数
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        for(int i = 1; i < weight.size(); i++) { // 遍历物品
            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]);
        }
    }
    
  • 举例推导dp数组

做动态规划的题目,最好的过程就是自己在纸上举一个例子把对应的dp数组的数值推导一下,然后在动手写代码!

01234
物品0015151515
物品1015152035
物品2015152035

CPP代码

//二维dp数组实现
#include <bits/stdc++.h>
using namespace std;

int n, bagweight;// bagweight代表行李箱空间
void solve() {
    vector<int> weight(n, 0); // 存储每件物品所占空间
    vector<int> value(n, 0);  // 存储每件物品价值
    for(int i = 0; i < n; ++i) {
        cin >> weight[i];
    }
    for(int j = 0; j < n; ++j) {
        cin >> value[j];
    }
    // dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

    // 初始化, 因为需要用到dp[i - 1]的值
    // j < weight[0]已在上方被初始化为0
    // j >= weight[0]的值就初始化为value[0]
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    for(int i = 1; i < weight.size(); i++) { // 遍历科研物品
        for(int j = 1; j <= bagweight; j++) { // 遍历行李箱容量
            // 如果装不下这个物品,那么就继承dp[i - 1][j]的值
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            // 如果能装下,就将值更新为 不装这个物品的最大值 和 装这个物品的最大值 中的 最大值
            // 装这个物品的最大值由容量为j - weight[i]的包任意放入序号为[0, i - 1]的最大值 + 该物品的价值构成
            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() {
    while(cin >> n >> bagweight) {
        solve();
    }
    return 0;
}

再论01背包的遍历顺序

之前我们说,无论先遍历背包容量还是先遍历物品都是可以的,这是为什么呢?

其实简单思考一下就知道了,从图形上来说:

如果是从左到右去填值(先遍历物品),我们[i][j]位置只由上方和左上角某值决定,所以合理!

如果从上到下去填值(先遍历背包),我们仍然能先完成[i][j]位置上方和左上角某值的填充,非常合理!

0-1背包理论基础(二)

卡码网第46题

文章讲解:0-1背包理论基础(二)

视频讲解:带你学透0-1背包问题!(滚动数组)

还记得我们在[再论01背包的遍历顺序](# 再论01背包的遍历顺序)讨论的遍历顺序吗,我们发现一个很关键的点,那就是本次状态(第[i]层)只与其整个上一层的状态(第[i-1]层)有关,所以我们其实很容易想到,如果把dp[i - 1]那一层拷贝到dp[i]上,表达式完全可以是:dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);。还能再优化吗?与其把上一层的状态拷贝到本层上,我们不如只用一个一维数组,也就是dp[j]。这是状态的压缩,也就是滚动数组的由来。

d p [ j ] = m a x ( d p [ j ] , d p [ j − w e i g h t [ i ] ] + v a l u e [ i ] ) ; dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); dp[j]=max(dp[j],dp[jweight[i]]+value[i]);

滚动数组需要满足:需要满足的条件是上一层可以重复利用,直接拷贝到当前层。

下面我们直接从dp数组的初始化开始讲起:

一维dp数组如何初始化

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

那么dp[0]就应该是0,因为背包容量为0所背的物品的最大价值就是0。

dp数组在推导的时候一定是取价值最大的数,如果题目给的价值都是正整数那么非0下标都初始化为0就可以了

vector<int> dp(n + 1, 0);

一维dp数组遍历顺序

在讲遍历顺序之前,我想再谈一次为什么本题可以用一维数组来遍历:

因为我们对每一个格子本质上还是需要依靠上一层格子来计算出本格子的值(这一句话看不懂可以再次阅读[0-1背包理论基础(一)](# 0-1背包理论基础(一))中谈到的递推和遍历思想)。

只不过我们把上一个层的值保存到了一维数组中,我们是依靠已有的数组的值/来进行/待计算值的/更新。

通过块中的文字,我们就可以知道,本题是不能先遍历背包容量,再遍历物品的,因为在二维世界中,这种遍历方法是从上到下的,本格子的值依赖上一层左上角的值,这样我们在一维数组中无法保存上一层的状态。(如果不明白,待会可以自己试一试就知道了)


揭晓答案了!一维dp的遍历顺序只能是先物品,再背包!

并且本题中的背包只能逆序遍历,也就是从大到小遍历,知道减小到当前材料所占的空间,为什么从大到小遍历呢?

之前谈到我们本质上还是在遍历一个二维数组,只不过我们在不停得对其进行更新,如果从小到大遍历,我们就会覆盖掉上一层的值,导致之前状态的丢失!所以从大到小遍历,完美利用上一层左上角格子和上层格子的状态!

举例推导dp数组

还是用上一题中的例子

CPP代码

// 一维dp数组实现
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 读取 M 和 N
    int M, N;
    cin >> M >> N;

    vector<int> costs(M);
    vector<int> values(M);

    for (int i = 0; i < M; i++) {
        cin >> costs[i];
    }
    for (int j = 0; j < M; j++) {
        cin >> values[j];
    }

    // 创建一个动态规划数组dp,初始值为0
    vector<int> dp(N + 1, 0);

    // 外层循环遍历每个类型的研究材料
    for (int i = 0; i < M; ++i) {
        // 内层循环从 N 空间逐渐减少到当前研究材料所占空间
        for (int j = N; j >= costs[i]; --j) {
            // 考虑当前研究材料选择和不选择的情况,选择最大值
            dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
        }
    }

    // 输出dp[N],即在给定 N 行李空间可以携带的研究材料最大价值
    cout << dp[N] << endl;

    return 0;
}

416.分割等和子集

力扣题目链接

文章讲解:416.分割等和子集

视频讲解:动态规划之背包问题,这个包能装满吗?| LeetCode:416.分割等和子集

状态:如何把他抽象成一个背包问题呢?一脸懵逼
看了如何抽象成背包问题后建议直接开始做,很舒服

没有抓住题目的重点,题目是要求分割等和子集,规定的分割方式是吧给定集合分割成两个集合,两个子集合的值相等。

那么整个集合的和除以2,其实就是每个子集合的和。那么首先要求想到回溯算法,这里不加论述,因为回溯算法会超时,这里主要讲将本题抽象成一个01背包问题。

思路

本题的本质就是,选取集合中元素,看有哪些元素相加能够等于 sum(nums) / 2

这里举一个具体的例子 ,给定nums = [1, 5, 11, 5],数组元素和为22,现在我们要分隔两个等和子集,也就是要求每个子集和为11。所以我们需要从 nums里面选一些元素,使其和为11。那么剩下的元素肯定也是11

现在你能将本题抽象成一个背包问题吗?

将题目抽象成0-1背包问题

我们吧nums中的元素抽象成每个物品的重量,同时也是价值,然后要求的子集合之和11为背包容量。由于我们每个元素只能用一次,所以这不就是明显的01背包问题。

这里我们更加具体一点:

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

综上所述,我们开始用01背包套用本题!(用一维数组来讨论)

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

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

  1. 确定递推公式

跟之前一样,递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

本题中,由于相当于背包里放入数值,那么物品i的重量是nums[i],其价值也是nums[i],故:

dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

  1. dp数组如何初始化

跟之前一样dp[0]初始化为0,在一个本题的价值都是正整数,所以非0下标也是初始化为0

如果题目给的价值有负数,那么非0下标就要初始化为负无穷。

vector<int> dp(10001, 0);
  1. 确定遍历顺序

如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入,所以从大到小遍历
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}
  1. 举例推导dp数组

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

CPP代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;

        // dp[i]中的i表示背包内总和
        // 题目中说:每个数组中的元素不会超过 100,数组的大小不会超过 200
        // 总和不会大于20000,背包最大只需要其中一半,所以10001大小就可以了
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        // 也可以使用库函数一步求和
        // int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1) return false;
        int target = sum / 2;

        // 开始 01背包
        for(int i = 0; i < nums.size(); i++) {
            for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入,所以从大到小遍历
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        // 集合中的元素正好可以凑成总和target
        if (dp[target] == target) return true;
        return false;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/584504.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2013NOIP普及组真题 4. 车站分级

线上OJ&#xff1a; 一本通&#xff1a;http://ybt.ssoier.cn:8088/problem_show.php?pid1964 核心思想&#xff1a; 1、原文中提到 “如果这趟车次停靠了火车站 x&#xff0c;则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠”&#xff0c;如果设停靠站为A&…

ansible-playbook离线升级centos内核

目录 概述实践ansible目录结构关键代码执行效果 结束 概述 内核离线包官网下载地址如下&#xff1a; 地址 实践 ansible目录结构 如对 ansible 不熟悉&#xff0c;离线包下载有问题&#xff0c;请至此地址下载&#xff0c;按本文操作可直接使用。 相关文章链接如下 文章地…

如何在iPhone上恢复出厂设置后恢复数据

你不想让这种情况发生&#xff0c;但它确实发生了。您必须将iPhone恢复出厂设置。当您的 iPhone 上出现软件问题且无法修复时&#xff0c;可能会发生这种情况。相反&#xff0c;在更新期间&#xff0c;或者您的iPhone遇到问题时&#xff0c;iPhone上的数据不再存在。 不过不用…

goget配置多个golang 运行环境

一台主机安装多个golang 运行环境 本环境 windows10 为 基础 mac linux也可以按照此方法操作 背景 开发不同的运维工具会用到不同版本的golang&#xff0c;但是开发者不能一直进行重装来处理 &#xff0c;因此 需要一个工具进行golang版本的管理 go管理工具介绍 gvm (Go V…

android webview检测屏幕

1&#xff09;清单文件配置&#xff1a; 配置权限&#xff1a; <uses-permission android:name"android.permission.INTERNET" /> 注册activity&#xff1a; <activityandroid:name".TouchWebViewActivity"android:exported"true"&…

基于随机森林和Xgboost对肥胖风险的多类别预测

基于随机森林和Xgboost对肥胖风险的多类别预测 作者&#xff1a;i阿极 作者简介&#xff1a;数据分析领域优质创作者、多项比赛获奖者&#xff1a;博主个人首页 &#x1f60a;&#x1f60a;&#x1f60a;如果觉得文章不错或能帮助到你学习&#xff0c;可以点赞&#x1f44d;收藏…

学习【Mysql运维篇】这一篇就够了

运维篇 1. 日志1-1. 错误日志1-2. 二进制日志1-3. 查询日志1-4. 慢查询日志 2. 主从复制2-1. 概述2-2. 原理2-3. 搭建 3. 分库分表3-1. 介绍3-2. Mycat概述3-3. Mycat入门3-4. Mycat配置3-5. Mycat分片3-6. Mycat管理及监控 4. 读写分类 1. 日志 1-1. 错误日志 错误日志是MyS…

计算机服务器中了mkp勒索病毒怎么办,mkp勒索病毒解密数据恢复流程

网络技术的不断应用与发展&#xff0c;为企业的生产运营带来了极大便利&#xff0c;越来越多的企业依赖网络开展各项工作业务&#xff0c;网络也大大提升了企业的生产运营效率&#xff0c;但网络是一把双刃剑&#xff0c;在为企业提供便利的同时&#xff0c;也为企业的数据安全…

云里物里家电运输新模式:实时定位、智能监控、降本增效

随着电商行业的飞速发展&#xff0c;大家电作为大宗商品&#xff0c;其物流运输过程中面临的痛点日益凸显。如何确保大家电在运输过程中的安全、及时送达以及成本控制&#xff0c;成为了物流企业亟待解决的问题。云里物里自研的物流资产监控管理方案&#xff0c;有效解决了大家…

JAVA面试题分享--集合

常见的数据结构&#xff08;了解&#xff09; 常用的数据结构有&#xff1a;数组&#xff0c;栈&#xff0c;队列&#xff0c;链表&#xff0c;树&#xff0c;散列&#xff0c;堆&#xff0c;图等 数组是最常用的数据结构&#xff0c;数组的特点是长度固定&#xff0c;数组的大…

一、交换网络基础

目录 1.交换机的转发行为 2.数据帧的类型 3.ARP地址解析步骤 Hub&#xff1a;物理层设备 交换机&#xff1a;数据链路层设备 1.交换机的转发行为 泛洪&#xff08;Flooding&#xff09;&#xff08;有可能是单播帧&#xff08;未知单播帧&#xff09;&#xff0c;也有可能是…

10GMAC层设计系列-(1)10G Ethernet PCS/PMA

一、引言 对于10G以太网MAC层的实现&#xff0c;Xilinx提供了 3种IP核&#xff0c;分别是 10G Ethernet MAC、10G Ethernet PCS/PMA、10G Ethernet Subsystem。 10G Ethernet MAC只包含MAC层&#xff0c;外部需要提供一个PHY芯片进行数据对齐&#xff0c;10G Ethernet MAC与P…

Python 深度学习(二)

原文&#xff1a;zh.annas-archive.org/md5/98cfb0b9095f1cf64732abfaa40d7b3a 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 第五章&#xff1a;图像识别 视觉可以说是人类最重要的感官之一。我们依赖视觉来识别食物&#xff0c;逃离危险&#xff0c;认出朋友和家人…

Kompas.ai的可持续内容生态:绿色营销的新选择

在全球环境保护意识日益增强的今天&#xff0c;绿色营销已成为企业树立品牌形象、展示社会责任的重要手段。绿色营销不仅关注产品的环保特性&#xff0c;还包括企业的整体可持续发展战略和对环境的积极贡献。本文将讨论企业如何通过绿色营销树立品牌形象&#xff0c;介绍Kompas…

el-cascader 数据回显 checkbox没有被勾选

需求&#xff1a; 需要支持多选以及能搜索&#xff0c;并且 点击所有队伍最新版本这个功能按钮时&#xff0c;要将用户勾选的数据保存的前提下&#xff0c;将满足条件的数据也一并勾选。最后保存的数据 只需要子级的id&#xff0c;组成数组就行了&#xff0c;所以我这里有用到…

ITMS-90426: Invalid Swift Support

原文 Please correct the following issues and upload a new binary to App Store Connect. ITMS-90426: Invalid Swift Support - The SwiftSupport folder is missing. Rebuild your app using the current public (GM) version of Xcode and resubmit it. 解决方式 ITMS-…

U盘提示“未初始化”?别慌,数据还有救!

当你满心期待地将U盘插入电脑&#xff0c;准备传输或读取重要文件时&#xff0c;突然弹出一个提示框&#xff1a;“U盘没有初始化”。遇到这样的情况&#xff0c;相信很多人都会感到焦虑和迷茫。别急&#xff0c;这篇文章将为你详细解析U盘未初始化的原因&#xff0c;并提供有效…

【设计模式】简单工厂模式(Simple Factory Pattern)

工厂模式&#xff08;Factory Pattern&#xff09; 用于创建不同类型的奖品对象。您可以创建一个奖品工厂&#xff0c;根据配置的类型来实例化相应的奖品对象。 public interface Prize {void award(); }public class MoneyPrize implements Prize {Overridepublic void awar…

一、初识Django

简介 Django 是一个用于构建 Web 应用程序的高级 Python Web 框架。 版本对应 不同版本的django框架是基于特定的不同的python版本开发的&#xff0c;所以不同版本的django框架要正常执行功能只能安装特定的python版本 Django安装 安装 Django # 全局安装 pip install dj…

实战干货|Spark 在袋鼠云数栈的深度探索与实践

Spark 是一个快速、通用、可扩展的大数据计算引擎&#xff0c;具有高性能、易用、容错、可以与 Hadoop 生态无缝集成、社区活跃度高等优点。在实际使用中&#xff0c;具有广泛的应用场景&#xff1a; 数据清洗和预处理&#xff1a;在大数据分析场景下&#xff0c;数据通常需要…