刷题DAY44 | 完全背包问题 LeetCode 518-零钱兑换 II 377-组合总和 Ⅳ

完全背包问题模版

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是,每种物品有无限件。

依然举这个例子:

背包最大重量为4。物品为:

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

每件商品都有无限个!

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

01背包和完全背包唯一不同就是体现在遍历顺序上

回顾一下01背包的核心代码

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

我们知道01背包内嵌的循环是从大到小遍历,为了保证每个物品仅被添加一次。

而完全背包的物品是可以添加多次的,所以要从小到大去遍历,即:

// 先遍历物品,再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了,一维dp数组的两个for循环先后循序一定是先遍历物品,再遍历背包容量。

在完全背包中,对于一维dp数组来说,其实两个for循环嵌套顺序是无所谓的!

因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。

代码实现1:

// 先遍历物品,再遍历背包
void test_CompletePack() {
    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++) { // 遍历物品
        for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    test_CompletePack();
}

代码实现2:

// 先遍历背包,再遍历物品
void test_CompletePack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

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

    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        for(int i = 0; i < weight.size(); i++) { // 遍历物品
            if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    test_CompletePack();
}

详细解析:
思路视频
代码实现文章



完全背包问题应用

518 零钱兑换 II(medium)

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

思路:完全背包问题,本题为组合,关键在于内外侧循环的顺序

注意题目描述中是凑成总金额的硬币组合数,为什么强调是组合数呢?

例如示例一:

5 = 2 + 2 + 1

5 = 2 + 1 + 2

这是一种组合,都是 2 2 1。

如果问的是排列数,那么上面就是两种排列了。

组合不强调元素之间的顺序,排列强调元素之间的顺序。

回归本题,动规五步曲来分析如下:

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

dp[j]:凑成总金额j的货币组合数为dp[j]

  1. 确定递推公式

dp[j] 就是所有的dp[j - coins[i]](考虑coins[i]的情况)相加。

所以递推公式:dp[j] += dp[j - coins[i]];

  1. dp数组如何初始化

首先dp[0]一定要为1,dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话,后面所有推导出来的值都是0了。

那么 dp[0] = 1 有没有含义,其实既可以说 凑成总金额0的货币组合数为1,也可以说 凑成总金额0的货币组合数为0,好像都没有毛病。

但题目描述中,也没明确说 amount = 0 的情况,结果应该是多少。后台测试数据是默认,amount = 0 的情况,组合数为1的。

下标非0的dp[j]初始化为0,这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]

dp[0]=1还说明了一种情况:如果正好选了coins[i]后,也就是j-coins[i] == 0的情况表示这个硬币刚好能选,此时dp[0]为1表示只选coins[i]存在这样的一种选法。

  1. 确定遍历顺序

本题中我们是外层for循环遍历物品(钱币),内层for遍历背包(金钱总额),还是外层for遍历背包(金钱总额),内层for循环遍历物品(钱币)呢?

纯完全背包求得装满背包的最大价值是多少,和凑成总和的元素有没有顺序没关系,即:有顺序也行,没有顺序也行!

而本题要求凑成总和的组合数,元素之间明确要求没有顺序。

所以纯完全背包是能凑成总和就行,不用管怎么凑的。

本题是求凑出来的方案个数,且每个方案个数是为组合数。

那么本题,两个for循环的先后顺序可就有说法了。

先来看 外层for循环遍历物品(钱币),内层for遍历背包(金钱总额)的情况。

代码如下:

for (int i = 0; i < coins.size(); i++) { // 遍历物品
    for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
        dp[j] += dp[j - coins[i]];
    }
}

假设:coins[0] = 1,coins[1] = 5。

那么就是先把1加入计算,然后再把5加入计算,得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

所以这种遍历顺序中dp[j]里计算的是组合数!

如果把两个for交换顺序,代码如下:

for (int j = 0; j <= amount; j++) { // 遍历背包容量
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}

背包容量的每一个值,都是经过 1 和 5 的计算,包含了{1, 5} 和 {5, 1}两种情况。

此时dp[j]里算出来的就是排列数!

  1. 举例推导dp数组

输入: amount = 5, coins = [1, 2, 5] ,dp状态图如下:
在这里插入图片描述
最后红色框dp[amount]为最终结果。

代码实现:

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};

时间复杂度: O(mn),其中 m 是amount,n 是 coins 的长度
空间复杂度: O(m)

详细讲解:
思路视频
代码实现文章


377 组合总和 Ⅳ(medium)

给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

思路:完全背包问题,本题为排列,关键在于内外侧循环的顺序

代码实现:

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 0; i <= target; i++) { // 遍历背包
            for (int j = 0; j < nums.size(); j++) { // 遍历物品
                if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
};
  • 时间复杂度: O(target * n),其中 n 为 nums 的长度
  • 空间复杂度: O(target)

C++测试用例有两个数相加超过int的数据,所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。

详细讲解:
思路视频
代码实现文章

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

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

相关文章

《UE5_C++多人TPS完整教程》学习笔记29 ——《P30 Blaster 角色(Blaster Character)》

本文为B站系列教学视频 《UE5_C多人TPS完整教程》 —— 《P30 Blaster 角色&#xff08;Blaster Character&#xff09;》 的学习笔记&#xff0c;该系列教学视频为 Udemy 课程 《Unreal Engine 5 C Multiplayer Shooter》 的中文字幕翻译版&#xff0c;UP主&#xff08;也是译…

网络原理 - HTTP / HTTPS(3)——http响应

目录 一、认识 “状态码”&#xff08;status code&#xff09; 常见的状态码 &#xff08;1&#xff09;200 OK &#xff08;2&#xff09;404 Not Found &#xff08;3&#xff09;403 ForBidden &#xff08;4&#xff09;405 Method Not Allowed &#xff08;5&…

从零到一:基于 K3s 快速搭建本地化 kubeflow AI 机器学习平台

背景 Kubeflow 是一种开源的 Kubernetes 原生框架&#xff0c;可用于开发、管理和运行机器学习工作负载&#xff0c;支持诸如 PyTorch、TensorFlow 等众多优秀的机器学习框架&#xff0c;本文介绍如何在 Mac 上搭建本地化的 kubeflow 机器学习平台。 注意&#xff1a;本文以 …

从头开发一个RISC-V的操作系统(二)RISC-V 指令集架构介绍

文章目录 前提ISA的基本介绍ISA是什么CISC vs RISCISA的宽度 RISC-V指令集RISC-V ISA的命名规范模块化的ISA通用寄存器Hart特权级别内存管理与保护异常和中断 目标&#xff1a;通过这一个系列课程的学习&#xff0c;开发出一个简易的在RISC-V指令集架构上运行的操作系统。 前提…

JavaSE-11笔记【多线程2(+2024新)】

文章目录 6.线程安全6.1 线程安全问题6.2 线程同步机制6.3 关于线程同步的面试题6.3.1 版本16.3.2 版本26.3.3 版本36.3.4 版本4 7.死锁7.1 多线程卖票问题 8.线程通信8.1 wait()和sleep的区别&#xff1f;8.2 两个线程交替输出8.3 三个线程交替输出8.4 线程通信-生产者和消费者…

硬件了解 笔记 2

CPU 内存控制器&#xff1a;负责读写数据 代理系统和平台IO&#xff1a;与主板上的芯片组通信&#xff0c;并管理PC中其他组件之间的数据流 主板&#xff1a;巨大的印刷电路板 Chipset&#xff1a;芯片组&#xff0c;位于散热器下方&#xff0c;直接连接到CPU的系统代理部分 …

应急响应-网站入侵篡改指南Webshell内存马查杀漏洞排查时间分析

知识点 网站入侵篡改防范应对指南 主要需了解&#xff1a;异常特征&#xff0c;处置流程&#xff0c;分析报告等 主要需了解&#xff1a;日志存储&#xff0c;Webshell检测&#xff0c;分析思路等掌握 中间件日志存储&#xff0c;日志格式内容介绍&#xff08;IP,UA头,访问方…

KV260 BOOT.BIN更新 ubuntu22.04 netplan修改IP

KV260 2022.2设置 BOOT.BIN升级 KV260开发板需要先更新BOOT.BIN到2022.2版本&#xff0c;命令如下&#xff1a; sudo xmutil bootfw_update -i “BOOT-k26-starter-kit-202305_2022.2.bin” 注意BOOT.BIN应包含全目录。下面是更新到2022.1 FW的示例&#xff0c;非更新到2022.…

IPSec VPN

IP Security,IP安全 1、特点 L3的VPN 缺:不支持组播、配置复杂、延迟增加、资源消耗较多 优:具备访问控制、密码学四个维度、抗重放打击 2、组件 ①安全协议 1)验证头技术(AH) IP协议号51 提供数据完整性检查,身份验证,抗重放攻击 无法做数据的机密性 AH的完…

【异常错误】 Expected to have finished reduction in the prior iteration before star、find_unused_parameters

运行代码时出现了错误&#xff1a; RuntimeError: Expected to have finished reduction in the prior iteration before starting a new one. This error indicates that your module has parameters that were not used in producing loss. You can enable unused parameter …

【Django学习笔记(四)】JavaScript 语言介绍

JavaScript 语言介绍 前言正文1、JavaScript 小案例2、代码位置2.1 在当前 HTML 文件中2.2 在其他 js 文件中 3、代码注释3.1 HTML的注释3.2 CSS的注释3.3 Javascript的注释 4、变量 & 输出4.1 字符串4.2 数组4.3 对象(python里的字典) 5、条件语句6、函数7、DOM7.1 根据 I…

【树上倍增】【内向基环树】【 图论 】2836. 在传球游戏中最大化函数值

本文涉及知识点 树上倍增 内向基环树 图论 LeetCode2836. 在传球游戏中最大化函数值 给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。 总共有 n 名玩家&#xff0c;玩家 编号 互不相同&#xff0c;且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏&am…

ideaSSM图书借阅管理系统VS开发mysql数据库web结构java编程计算机网页源码maven项目

一、源码特点 SSM 图书借阅管理系统是一套完善的信息管理系统&#xff0c;结合SSM框架和bootstrap完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用SSM框架&#xff08;MVC模式开发&#xff09;&#xff0c;系统具有完整的源代码 和数据库&#xff0c;系统主…

【爬虫+数据清洗+数据分析+可视化】“淄博烧烤”现象热评舆情python数据分析大屏

一、开发背景 您好&#xff0c;我是马哥小迷弟132 &#xff0c;一枚10年程序猿。 自从2023.3月以来&#xff0c;"淄博烧烤"现象持续占领热搜流量&#xff0c;体现了后疫情时代众多网友对人间烟火气的美好向往&#xff0c;本现象级事件存在一定的数据分析实践意义。…

Java零基础入门-java8新特性(上篇)

一、本期教学目标 java8有哪些新特性什么是函数式接口什么是Lambda表达式掌握Stream ApiStream和Collect集合区别Stream创建方式Stream操作三步骤 二、概述 上几期&#xff0c;我们是完整的学完了java异常类的学习及实战演示、以及学习了线程进程等基础概念&#xff0c;而这一…

Cache多核之间的一致性MESI

快速链接: 【精选】ARMv8/ARMv9架构入门到精通-[目录] &#x1f448;&#x1f448;&#x1f448; 思考: 1、为什么要学习MESI协议&#xff1f; 哪里用到了&#xff1f;你确定真的用到了&#xff1f; 2、MESI只是一个协议&#xff0c;总得依赖一个硬件去执行该协议吧&#xff0c…

电商技术揭秘一:电商架构设计与核心技术

文章目录 引言一、电商平台架构概述1.1 架构设计原则与架构类型选择1.2 传统电商平台架构与现代化架构趋势分析 二、高并发处理与负载均衡2.1 高并发访问特点分析与挑战2.2 负载均衡原理与算法选择 三、分布式数据库与缓存技术3.1 分布式数据库设计与一致性考量3.2 缓存策略与缓…

C++实现二叉搜索树的增删查改(非递归玩法)

文章目录 一、二叉搜索树的概念结构和时间复杂度二、二叉搜索树的插入三、二叉搜索树的查找四、二叉搜索树的删除&#xff08;最麻烦&#xff0c;情况最多&#xff0c;一一分析&#xff09;3.1首先我们按照一般情况下写&#xff0c;不考虑特殊情况下4.1.1左为空的情况&#xff…

分享:搭建企微知识库简单易学步骤

说起企微知识库&#xff0c;可能有些人还不太清楚&#xff0c;为什么现在很懂企业选择搭建企微知识库&#xff1f;其实&#xff0c;企微知识库就是一个装满了企业的各种知识、经验和资料的载体。目的是为了方便员工随时查找和学习、有助于知识的传承和共享、加强团队协作和沟通…

自然语言处理: 第二十一章大模型基底之llama2

文章地址: LLaMA:OpenandEfficient Foundation Language Models 项目地址: meta-llama/llama: Inference code for Llama models (github.com) 前言 在LLaMa1的基础之上有兴趣的可以看看我上一篇博客自然语言处理: 第二十一章大模型基底之llama1。Meta 又继续推出了LLaMa2&a…