当前位置: 首页 > news >正文

Day 44 | 动态规划 完全背包、518. 零钱兑换 II 、 377. 组合总和 Ⅳ

完全背包

题目
文章讲解
视频讲解

完全背包和0-1背包的区别在于:物品是否可以重复使用

思路:对于完全背包问题,内层循环的遍历方式应该是从weight[i]开始一直遍历到V,而不是从V到weight[i]。这样可以确保每种物品可以被选择多次放入背包,从而求解完全背包问题。

对于完全背包问题,需要对内层循环进行调整,以确保每种物品可以被选择多次放入背包。

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt(); // 研究材料种类int V = sc.nextInt(); // 行李箱空间int[] values = new int[N]; // 物品价值int[] weight = new int[N]; // 物品重量// 依次输入每种物品的重量和价值for (int i = 0; i < N; i++) {weight[i] = sc.nextInt(); // 物品重量values[i] = sc.nextInt(); // 物品价值}int[] dp = new int[V + 1]; // 动态规划数组for (int i = 0; i < N; i++) {for (int j = weight[i]; j <= V; j++) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i]); // 动态规划状态转移方程}}System.out.println(dp[V]); // 输出结果}
}

一维0-1背包求解法示例如下

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt(); // 研究材料种类int V = sc.nextInt(); // 行李箱空间int[] values = new int[N]; // 物品价值int[] weight = new int[N]; // 物品重量// 依次输入每种物品的重量和价值for (int i = 0; i < N; i++) {weight[i] = sc.nextInt(); // 物品重量values[i] = sc.nextInt(); // 物品价值}int[] dp = new int[V + 1]; // 动态规划数组for (int i = 0; i < N; i++) {for (int j = V; j >= weight[i]; j--) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i]); // 动态规划状态转移方程}}System.out.println(dp[V]); // 输出结果}
}

对比:

  • 完全背包:
    在这里插入图片描述

  • 0-1背包:
    在这里插入图片描述

518. 零钱兑换 II

题目
文章讲解
视频讲解

思路:

  1. dp[j]:凑成总金额j的货币组合数为dp[j]
  2. 递推公式:dp[j] 就是所有的dp[j - coins[i]](考虑coins[i]的情况)相加
  3. 初始化需要注意 dp[0]=1;
class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0] = 1;for (int i = 0; i < coins.length; i++) {for (int j = coins[i]; j <= amount; j++) {dp[j] += dp[j - coins[i]];}}return dp[amount];}
}

377. 组合总和 Ⅳ

题目
文章讲解
视频讲解

思路:

如果求组合数就是外层for循环遍历物品,内层for遍历背包;
如果求排列数就是外层for遍历背包,内层for循环遍历物品。

class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1;for (int i = 0; i <= target; i++) {for (int j = 0; j < nums.length; j++) {if (i >= nums[j])dp[i] += dp[i - nums[j]];}}return dp[target];}
}

相关文章:

Day 44 | 动态规划 完全背包、518. 零钱兑换 II 、 377. 组合总和 Ⅳ

完全背包 题目 文章讲解 视频讲解 完全背包和0-1背包的区别在于&#xff1a;物品是否可以重复使用 思路&#xff1a;对于完全背包问题&#xff0c;内层循环的遍历方式应该是从weight[i]开始一直遍历到V&#xff0c;而不是从V到weight[i]。这样可以确保每种物品可以被选择多次…...

使用PaddleNLP UIE模型提取上市公司PDF公告关键信息

项目地址&#xff1a;使用PaddleNLP UIE模型抽取PDF版上市公司公告 - 飞桨AI Studio星河社区 (baidu.com) 背景介绍 本项目将演示如何通过PDFPlumber库和PaddleNLP UIE模型&#xff0c;抽取公告中的相关信息。本次任务的PDF内容是破产清算的相关公告&#xff0c;目标是获取受理…...

软件工程师,OpenAI Sora驾到,快来围观

概述 近期&#xff0c;OpenAI在其官方网站上公布了Sora文生视频模型的详细信息&#xff0c;展示了其令人印象深刻的能力&#xff0c;包括根据文本输入快速生成长达一分钟的高清视频。Sora的强大之处在于其能够根据文本描述&#xff0c;生成长达60秒的视频&#xff0c;其中包含&…...

【Linux 04】编辑器 vim 详细介绍

文章目录 &#x1f308; Ⅰ 基本概念&#x1f308; Ⅱ 基本操作1. 进入 / 退出 vim2. vim 模式切换 &#x1f308; Ⅲ 命令模式1. 光标的移动2. 复制与粘贴3. 剪切与删除4. 撤销与恢复 &#x1f308; Ⅳ 底行模式1. 保存文件2. 查找字符3. 退出文件4. 替换内容5. 显示行号6. 外…...

KMP算法详解

1. 问题引入 链接&#xff1a;leetcode_28 题目&#xff1a;s1字符串是否包含s2字符串&#xff0c;如果包含返回s1中包含s2的最左开头位置&#xff0c;不包含返回-1 暴力方法就是s1的每个位置都做开头&#xff0c;然后去匹配s2整体&#xff0c;时间复杂度O(n*m) KMP算法可以…...

ubuntu22.04@laptop OpenCV Get Started: 013_contour_detection

ubuntu22.04laptop OpenCV Get Started: 013_contour_detection 1. 源由2. 应用Demo2.1 C应用Demo2.2 Python应用Demo 3. contour_approx应用3.1 读取图像并将其转换为灰度格式3.2 应用二进制阈值过滤算法3.3 查找对象轮廓3.4 绘制对象轮廓3.5 效果3.6 CHAIN_APPROX_SIMPLE v.s…...

[ai笔记5] 个人AI资讯助手实战

欢迎来到文思源想的ai空间&#xff0c;这是技术老兵重学ai以及成长思考的第5篇分享&#xff0c;也是把ai场景化应用的第一篇实操内容&#xff01; 既然要充分学习和了解ai&#xff0c;自然少不了要时常看看ai相关资讯&#xff0c;所以今天特地用字节的“扣子”做了一个ai的资讯…...

QT+OSG/osgEarth编译之八十九:osgdb_ply+Qt编译(一套代码、一套框架,跨平台编译,版本:OSG-3.6.5插件库osgdb_ply)

文章目录 一、osgdb_ply介绍二、文件分析三、pro文件四、编译实践一、osgdb_ply介绍 斯坦福三角形格式(Stanford Triangle Format)是一种用于存储三维模型数据的文件格式,也称为 PLY 格式。它最初由斯坦福大学图形实验室开发,用于存储和共享三维扫描和计算机图形数据。 P…...

机器人专题:我国机器人产业园区发展现状、问题、经验及建议

今天分享的是机器人系列深度研究报告&#xff1a;《机器人专题&#xff1a;我国机器人产业园区发展现状、问题、经验及建议》。 &#xff08;报告出品方&#xff1a;赛迪研究院&#xff09; 报告共计&#xff1a;26页 机器人作为推动工业化发展和数字中国建设的重要工具&…...

算法沉淀——哈希算法(leetcode真题剖析)

算法沉淀——哈希算法 01.两数之和02.判定是否互为字符重排03.存在重复元素04.存在重复元素 II05.字母异位词分组 哈希算法&#xff08;Hash Algorithm&#xff09;是一种将任意长度的输入&#xff08;也称为消息&#xff09;映射为固定长度的输出的算法。这个输出通常称为哈希…...

深入理解Redis哨兵原理

哨兵模式介绍 在深入理解Redis主从架构中Redis 的主从架构中&#xff0c;由于主从模式是读写分离的&#xff0c;如果主节点&#xff08;master&#xff09;挂了&#xff0c;那么将没有主节点来服务客户端的写操作请求&#xff0c;也没有主节点给从节点&#xff08;slave&#…...

MySQL-存储过程(PROCEDURE)

文章目录 1. 什么是存储过程&#xff1f;2. 存储过程的优点3. MySQL中的变量3.1 系统变量3.2 用户自定义变量3.3 局部变量 4. 存储过程的相关语法4.1 创建存储过程&#xff08;CREATE&#xff09;4.2 查看存储过程&#xff08;SHOW&#xff09;4.3 修改存储过程&#xff08;ALT…...

linux系统监控工具prometheus的安装以及监控mysql

prometheus 安装服务端客户端监控mysql prometheus浏览器查看 安装 https://prometheus.io/download/下载客户端和服务端以及需要监控的所有的包服务端 官网下载下载prometheustar -xf prometheus-2.47.2.linux-amd64.tar.gz -C /usr/local/ cd /usr/local/ mv prometheus-2.…...

初识tensorflow程序设计模式

文章目录 建立计算图tensorflow placeholdertensorflow数值运算常用的方法 tensorboard启动tensorboard的方法 建立一维与二维张量建立一维张量建立二维张量建立新的二维张量 矩阵的基本运算矩阵的加法矩阵乘法与加法 github地址https://github.com/fz861062923/TensorFlow 建…...

【QT+QGIS跨平台编译】之三十八:【GDAL+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、gdal介绍二、文件下载三、文件分析四、pro文件五、编译实践一、gdal介绍 GDAL(Geospatial Data Abstraction Library)是一个用于读取、写入和处理地理空间数据的开源库。它支持多种栅格和矢量地理空间数据格式,包括常见的GeoTIFF、Shapefile、NetCDF、HDF5等,…...

黑马鸿蒙教程学习1:Helloworld

今年打算粗略学习下鸿蒙开发&#xff0c;当作兴趣爱好&#xff0c;通过下华为那个鸿蒙开发认证&#xff0c; 发现黑马的课程不错&#xff0c;有视频和完整的代码和课件下载&#xff0c;装个devstudio就行了&#xff0c;建议32G内存。 今年的确是鸿蒙大爆发的一年呀&#xff0c;…...

蓝桥杯每日一题------背包问题(四)

前言 前面讲的都是背包的基础问题&#xff0c;这一节我们进行背包问题的实战&#xff0c;题目来源于一位朋友的询问&#xff0c;其实在这之前很少有题目是我自己独立做的&#xff0c;我一般习惯于先看题解&#xff0c;验证了题解提供的代码是正确的后&#xff0c;再去研究题解…...

OpenAI发布Sora技术报告深度解读!真的太强了!

&#x1f60e; 作者介绍&#xff1a;我是程序员洲洲&#xff0c;一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主、前后端开发、人工智能研究生。公粽号&#xff1a;洲与AI。 &#x1f388; 本文专栏&#xff1a;本文收录…...

AJAX——接口文档

1 接口文档 接口文档&#xff1a;描述接口的文章 接口&#xff1a;使用AJAX和服务器通讯时&#xff0c;使用的URL&#xff0c;请求方法&#xff0c;以及参数 传送门&#xff1a;AJAX阶段接口文档 <!DOCTYPE html> <html lang"en"><head><meta c…...

leetcode hot100不同路径

本题可以采用动态规划来解决。还是按照五部曲来做 确定dp数组&#xff1a;dp[i][j]表示走到&#xff08;i&#xff0c;j&#xff09;有多少种路径 确定递推公式&#xff1a;我们这里&#xff0c;只有两个移动方向&#xff0c;比如说我移动到&#xff08;i&#xff0c;j&#x…...

FreeRTOS中断管理实战:如何用信号量优雅处理硬件中断(附STM32代码)

FreeRTOS中断管理实战&#xff1a;信号量在STM32硬件中断中的高效应用 1. 嵌入式实时系统中的中断挑战 在嵌入式开发中&#xff0c;中断处理就像餐厅里的紧急订单——它可能随时打断主厨正在准备的常规菜品。想象你正在安静地享用下午茶&#xff0c;突然门铃响起&#xff08;…...

工业能量:04.选型小Tips:预算2000元玩转工厂电源

04.选型小Tips:预算2000元玩转工厂电源(新手也能选对不踩坑,PLC机器人稳稳的)** 在工厂里,最昂贵的不是设备,而是“停机一秒的代价”。 哎,师傅们,槐树底下风儿吹得正凉快,今天咱不拆原理、不讲高端配置,就聊最接地气的——2000块钱怎么给车间PLC和机器人挑个靠谱心脏…...

OpenClaw人人养虾:密钥管理

Gateway 提供安全的密钥管理&#xff08;Secrets Management&#xff09;功能&#xff0c;用于加密存储 API Key、Token 等敏感凭证&#xff0c;避免在配置文件中暴露明文。为什么需要密钥管理明文风险将 API Key 直接写在配置文件中存在严重安全风险&#xff1a;配置文件可能被…...

实测!用DeepSeek R1和通义千问Max分别写代码、解数学题,结果有点意外

DeepSeek R1与通义千问Max实战对比&#xff1a;当代码遇上数学题 上周我在开发一个需要同时处理算法优化和复杂数学计算的个人项目时&#xff0c;突然萌生了一个想法&#xff1a;为什么不把市面上最火的两个AI编程助手——DeepSeek R1和通义千问Max拉出来比一比&#xff1f;作…...

ChatGLM-6B角色扮演功能开发:基于Prompt的智能对话系统

ChatGLM-6B角色扮演功能开发&#xff1a;基于Prompt的智能对话系统 1. 引言 想象一下&#xff0c;你正在开发一个智能客服系统&#xff0c;需要让AI能够扮演不同角色的专业人士来回答用户问题。或者你正在创建一个教育应用&#xff0c;希望AI能够化身历史人物、科学导师或文学…...

利用AI改写工具,五个策略帮助论文查重率快速降至合规标准

嘿&#xff0c;大家好&#xff01;我是AI菌。今天咱们来聊聊一个让无数学生头疼的问题&#xff1a;论文重复率飙到30%以上怎么办&#xff1f;别慌&#xff0c;我这就分享5个实用降重技巧&#xff0c;帮你一次搞定&#xff0c;轻松压到合格线以下。这些方法都是我亲身试验过的&a…...

Windows下用MSYS2编译axel多线程下载工具的保姆级教程(附常见错误解决方案)

Windows下MSYS2编译axel多线程下载工具全指南 如果你厌倦了商业下载工具的臃肿和限制&#xff0c;又对Python多线程下载的稳定性不满&#xff0c;那么编译一个原生的axel多线程下载工具可能是最佳选择。本文将带你从零开始在Windows环境下&#xff0c;通过MSYS2完整编译axel&a…...

手把手教你实现glitch free的时钟切换电路(附Verilog代码)

手把手教你实现glitch free的时钟切换电路&#xff08;附Verilog代码&#xff09; 时钟切换电路是数字系统设计中的关键模块&#xff0c;尤其在多时钟域系统中&#xff0c;可靠的时钟切换能确保系统稳定运行。本文将深入探讨如何实现无毛刺&#xff08;glitch free&#xff09;…...

告别DLSS版本迷宫:DLSS Swapper如何实现3步智能优化

告别DLSS版本迷宫&#xff1a;DLSS Swapper如何实现3步智能优化 【免费下载链接】dlss-swapper 项目地址: https://gitcode.com/GitHub_Trending/dl/dlss-swapper 核心价值&#xff1a;解决三大核心矛盾&#xff0c;让DLSS管理化繁为简 您是否曾遇到这样的场景&#x…...

【具身智能07】具身智能世界模型与端到端架构:从看见到理解物理规律

07_具身智能世界模型与端到端架构 关键词 世界模型,端到端架构,VLA模型,DreamerV3,RoboCat,WALL-A,云边端协同,系统012架构,多时间尺度预测,因果推理一、引言:从反应式感知到预测式认知的范式转变 2024年之前,具身智能的主流是"感知-行动"反应式回路——机器人看到杯…...