代码随想录day42|背包问题、416. 分割等和子集

 背包问题:

 

 01 背包

二维数组dp[i][j]解法

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

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

 递推公式:对于dp[i][j]来说,有两种方式得到一种时正上方,就时不放物品i,还有一种就是从左上方得来,就是放物品i

  • 不放物品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]);

初始化:dp[i][0] = 0,这里的意思是当重量为零的时候,无论选取哪些物品,背包总价值都是为零的,

dp[0][j],即:i为0,存放编号0的物品的时候,各个容量的背包所能存放的最大价值。

那么很明显当 j < weight[0]的时候,dp[0][j] 应该是 0,因为背包容量比编号0的物品重量还小。

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

其他的位置的话,其实初始什么数值都是可以的,因为dp[i][j]是由左上方和正上方决定的,其他的位置都是会被覆盖的,初始化成零的话,更方便一点

遍历顺序:

先遍历物品还是先遍历重量都一样

所以说当是dp二维数组时候,不管是遍历那个方向都可以 

代码实现:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define ARR_SIZE(a) (sizeof((a)) / sizeof((a)[0]))
#define BAG_WEIGHT 4

void backPack(int* weights, int weightSize, int* costs, int costSize, int bagWeight) {
    // 开辟dp数组
    int dp[weightSize][bagWeight + 1];
    memset(dp, 0, sizeof(int) * weightSize * (bagWeight + 1));

    int i, j;
    // 当背包容量大于物品0的重量时,将物品0放入到背包中
    for(j = weights[0]; j <= bagWeight; ++j) {
        dp[0][j] = costs[0];
    }

    // 先遍历物品,再遍历重量
    for(j = 1; j <= bagWeight; ++j) {
        for(i = 1; i < weightSize; ++i) {
            // 如果当前背包容量小于物品重量
            if(j < weights[i])
                // 背包物品的价值等于背包不放置当前物品时的价值
                dp[i][j] = dp[i-1][j];
            // 若背包当前重量可以放置物品
            else
                // 背包的价值等于放置该物品或不放置该物品的最大值
                dp[i][j] = MAX(dp[i - 1][j],  dp[i - 1][j - weights[i]] + costs[i]);
        }
    }

    printf("%d\n", dp[weightSize - 1][bagWeight]);
}

int main(int argc, char* argv[]) {
    int weights[] = {1, 3, 4};
    int costs[] = {15, 20, 30};
    backPack(weights, ARR_SIZE(weights), costs, ARR_SIZE(costs), BAG_WEIGHT);
    return 0;
}

memset 是 C 和 C++ 标准库中的一个函数,用于将内存区域的前 num 个字节设置为指定的值。它的原型通常在 <string.h> 或 <cstring> 头文件中定义。

函数的原型如下:

c复制代码

void *memset(void *s, int c, size_t n);

参数解释:

  • s:指向要设置的内存区域的指针。
  • c:要设置的值。通常,这是一个整数,但会被强制转换为 unsigned char,然后复制到目标内存的每个字节。
  • n:要设置的字节数。

函数返回指向 s 的指针。

一维数组(滚动数组)

一维数组就是将二维数组给压缩了, 将上一层的情况复制到下一层去(这就是滚动数组的由来,需要满足的条件是上一层可以重复利用,直接拷贝到当前层。)

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

递推公式:

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

 这个其实就是二维数组没有i那个维度,dp[j]相当于的dp[i-1][j]这一层

初始化:

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

那么dp数组除了下标0的位置,初始为0,其他下标应该初始化多少呢?

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

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

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

那么我假设物品价值都是大于0的,所以dp数组初始化的时候,都初始为0就可以了。

4遍历顺序:

背包容量是从大到小,就是倒序遍历

——这是为了保证物品i只被放入一次,因为正序遍历中,要进行减一操作,所以说会有一个物品被同时放入的情况

为什么二维数组中可以不用考虑遍历顺序?

——因为二维数组中每一层的数据是单独分开来的,而一维数组中是重复利用的,为了保证只放入一次,所以一维数组中要倒序

#include <stdio.h>
#include <string.h>

#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define ARR_SIZE(arr) ((sizeof((arr))) / sizeof((arr)[0]))
#define BAG_WEIGHT 4

void test_back_pack(int* weights, int weightSize, int* values, int valueSize, int bagWeight) {
    int dp[bagWeight + 1];
    memset(dp, 0, sizeof(int) * (bagWeight + 1));

    int i, j;
    // 先遍历物品
    for(i = 0; i < weightSize; ++i) {
        // 后遍历重量。从后向前遍历
        for(j = bagWeight; j >= weights[i]; --j) {
            dp[j] = MAX(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

    // 打印最优结果
    printf("%d\n", dp[bagWeight]);
}

int main(int argc, char** argv) {
    int weights[] = {1, 3, 4};
    int values[] = {15, 20, 30};
    test_back_pack(weights, ARR_SIZE(weights), values, ARR_SIZE(values), BAG_WEIGHT);
    return 0;
}

 416. 分割等和子集

这道题目可以抽象成一道背包问题,只不过是这时候物品的重量和价值都是子集本身

dp[j]:容量为j,最大值为dp[j]

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

初始化:dp[0] = 0,题目中提到这个子集为正数的,所以不可能存在负数

其他应该初始化成什么?

——是初始成任意的数字嘛,因为递推公式中有比较的关系,假如初始化过大,可能导致正确的值无法被保存到,所以说要初始化到最小的值

遍历顺序:从后到前

#define MAX(a, b) (((a) > (b)) ? (a) : (b))
int getsum(int* nums, int numsSize){
    int sum = 0;

    int i;
    for(i = 0; i < numsSize; ++i){
        sum += nums[i];
    }
    return sum ;
}
bool canPartition(int* nums, int numsSize) {
    int sum = getsum(nums, numsSize);

    if(sum % 2)
        return false;
    
    int target = sum / 2;

    int dp[target + 1];
    memset(dp, 0, sizeof(int) * (target +1 ));

    int i, j;
    for(i = 0; i < numsSize; ++i)
    {
        for(j = target; j >= nums[i]; --j){
            dp[j] = MAX(dp[j],dp[j - nums[i]] + nums[i]);
        }
    }
    return dp[target] == target;
}

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

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

相关文章

React面试

React渲染流程(重点) jsx描述界面 jsx babel render function>vdom vdom fiber 在进行渲染 vdom 转换fiber reconcile 转换过程创建dom commit 到domvdom React Element 对象, 只记录了子节点, 没有记录兄弟节点, 因为渲染不可中断 fiber fiberNode 对象, 是一个链表 父节…

算法:完全背包问题dp

文章目录 一、完全背包问题的特征二、定义状态三、状态转移四、降维优化五、参考例题5.1、Acwing&#xff1a;3.完全背包问题5.2、Acwing&#xff1a;900. 整数划分 一、完全背包问题的特征 完全背包问题是动态规划中的一种经典问题&#xff0c;它的主要特征可以总结如下&…

政安晨:【深度学习神经网络基础】(四)—— 自组织映射

目录 自组织映射和邻域函数 理解邻域函数 墨西哥帽邻域函数 计算SOM误差 政安晨的个人主页&#xff1a;政安晨 欢迎 &#x1f44d;点赞✍评论⭐收藏 收录专栏: 政安晨的机器学习笔记 希望政安晨的博客能够对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

APx500音频分析仪硬件简介

两通道模拟输出&#xff0c;两通道或以上的模拟输入接口 线性编码数字音频接口&#xff08;AES/EBU,TOSLINK,SPDIF&#xff09;Linear PCM 脉冲密度调制码流&#xff08;需要APx-PDM选件支持&#xff09; Bluetooth蓝牙音频码流&#xff08;需APx-BT选件支持&#xff09; 最…

打印月历 Open Judge

题面链接: http://noi.openjudge.cn/ch0113/24/ 题目描述: 评析: 大模拟题&#xff0c;考察的是你的耐心和毅力&#xff01;很不错的模拟题练习题&#xff0c;小白(like me)可以练一练 思路: 先一个月一个月的模拟&#xff0c;求出来题目问的这个一年的这一个月的第一天是星期…

C#互联网区域医学检验中心云LIS系统源码

云LIS联通四级&#xff08;市、县、乡、村&#xff09;检验服务网构建互联网检验服务新体系落地检验资源区域共享建设。云LIS系统是一种基于云计算技术的区域实验室信息管理系统&#xff0c;它的主要功能是管理实验室中的各种信息数据&#xff0c;包括样品数据、检测结果、仪器…

多视觉传感器协同弱小目标检测

源自&#xff1a;指挥与控制学院 作者&#xff1a;王田&#xff0c; 程嘉翔&#xff0c; 刘克新&#xff0c;王薇&#xff0c; 吕金虎 “人工智能技术与咨询” 发布 摘 要 多视觉传感器协同对空实现全区域覆盖的弱小目标检测&#xff0c;在近距离防空领域中具有重要意义。…

酷开科技不断深耕智能电视领域,用酷开系统带给消费者更多可能性

在这个网络快速发展的时代&#xff0c;电视行业也发生了巨大变革。与以往单纯的“看”电视不同&#xff0c;人们不再满足于现有的状态&#xff0c;消费者对电视娱乐的追求更加丰富&#xff0c;这也就带给智能电视产业无限的发展可能。酷开科技瞄准这一产业趋势&#xff0c;不断…

Golang | Leetcode Golang题解之第18题四数之和

题目&#xff1a; 题解&#xff1a; func fourSum(nums []int, target int) (quadruplets [][]int) {sort.Ints(nums)n : len(nums)for i : 0; i < n-3 && nums[i]nums[i1]nums[i2]nums[i3] < target; i {if i > 0 && nums[i] nums[i-1] || nums[i]…

VLAN间的通信

目录 原理概述 实验目的 实验内容 实验拓扑 1.基本配置 2.使用VLANIF接口实现VLAN间的通信 3.使用VLAN聚合实现VLAN间的通信。 原理概述 通常情况下&#xff0c;如果不采用一些特殊的方法&#xff08;如采用Hybrid端口的方法&#xff09;&#xff0c;不同的VLAN之间是不…

力扣--动态规划完全背包/深度优先08.11.零币

如果暴力的深度优先&#xff1a; class Solution {// 定义硬币的面值数组int fangx[4] {25, 10, 5, 1};// 计数变量&#xff0c;用于记录配合得到 n 的方法数long long count 0;// 定义深度优先搜索函数// now: 当前总值// n: 目标总值// notbig: 上一次选择的硬币面值索引…

PCB学习记录-----入门基础知识

一、搭建环境 1.下载嘉立创EDA 软件下载 - 嘉立创EDA (lceda.cn) 选专业版 在线编辑&#xff1a;嘉立创EDA(专业版) - V2.1.45 (lceda.cn) 官方教程&#xff1a;立创EDA专业版-使用教程 (lceda.cn) 2.新建工程 文件-新建-项目&#xff0c;右键Board1可以重命名&#xff…

Debian 12.0安装NVM管理器

cd到一个自己创建的目录 要在Debian 12.0上安装 Node Version Manager&#xff08;NVM&#xff09;来管理 Node.js 版本&#xff0c;您可以按照以下步骤进行操作&#xff1a; 首先&#xff0c;您需要使用 cURL 下载 NVM 安装脚本。在终端中运行以下命令&#xff1a; curl -o…

读博做FPGA上的AI加速能不能搞啊?

从企业的角度来看&#xff0c;选择在FPGA上进行AI加速仍然有其一定的优势和适用场景&#xff0c;但也有一些挑战需要考虑。我这里有一套嵌入式入门教程&#xff0c;不仅包含了详细的视频讲解&#xff0c;项目实战。如果你渴望学习嵌入式&#xff0c;不妨点个关注&#xff0c;给…

使用Datax自定义采集组件Reader/Writer实现国产数据库支持以及_Datax数据清洗/过滤规则功能自定义---大数据之DataX工作笔记007

我们基于datax来做的自己的数据采集系统,现在基本的数据采集已经实现了,也就是调用datax的数据采集能力,实现在已支持的数据库之间同步数据.我们是基于datax-web实现的,里面都有开源的代码了,可以分析以后拿过来用,这个过程并不复杂,而且,结合xxljob的web那个开源项目,也可以让…

S19文件解析

目录 一、概述 二、S19文件解析 三、举例 一、概述&#xff1a; Motorola S-record是一种文件格式&#xff0c;由摩托罗拉在20世纪70年代中期为Motorola 6800处理器创建&#xff0c;以ASCII文本形式传达二进制信息的十六进制值&#xff0c;其文件格式也可能为SRECORD&#xf…

如何使用宝塔面板搭建MySQL数据库并实现无公网IP远程访问

文章目录 前言1.Mysql服务安装2.创建数据库3.安装cpolar3.2 创建HTTP隧道 4.远程连接5.固定TCP地址5.1 保留一个固定的公网TCP端口地址5.2 配置固定公网TCP端口地址 前言 宝塔面板的简易操作性,使得运维难度降低,简化了Linux命令行进行繁琐的配置,下面简单几步,通过宝塔面板cp…

Macos 部署自己的privateGpt(2024-0404)

Private Chatgpt 安装指引 https://docs.privategpt.dev/installation/getting-started/installation#base-requirements-to-run-privategpt 下载源码 git clone https://github.com/imartinez/privateGPT cd privateGPT安装软件 安装&#xff1a; Homebrew /bin/bash -c…

《C语言深度解剖》(3):探索函数递归、传值、传址调用的奥秘

&#x1f921;博客主页&#xff1a;醉竺 &#x1f970;本文专栏&#xff1a;《C语言深度解剖》 &#x1f63b;欢迎关注&#xff1a;感谢大家的点赞评论关注&#xff0c;祝您学有所成&#xff01; ✨✨&#x1f49c;&#x1f49b;想要学习更多数据结构与算法点击专栏链接查看&am…

Linux锁的使用

一、临界资源与临界区 多线程会共享例如全局变量等资源&#xff0c;我们把会被多个执行流访问的资源称为临界资源&#xff0c;我们是通过代码访问临界资源的&#xff0c;而我们访问临界资源的那部分代码称为临界区。 实现一个抢票系统 只有一个线程抢票时 #include <ios…