当前位置: 首页 > 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…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法 大家好,我是Echo_Wish。最近刷短视频、看直播,有没有发现,越来越多的应用都开始“懂你”了——它们能感知你的情绪,推荐更合适的内容,甚至帮客服识别用户情绪,提升服务体验。这背后,神经网络在悄悄发力,撑起…...

goreplay

1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具&#xff0c;可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长&#xff0c;测试它所需的工作量也会呈指数级增长。GoRepl…...

FOPLP vs CoWoS

以下是 FOPLP&#xff08;Fan-out panel-level packaging 扇出型面板级封装&#xff09;与 CoWoS&#xff08;Chip on Wafer on Substrate&#xff09;两种先进封装技术的详细对比分析&#xff0c;涵盖技术原理、性能、成本、应用场景及市场趋势等维度&#xff1a; 一、技术原…...

Linux操作系统共享Windows操作系统的文件

目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项&#xff0c;设置文件夹共享为总是启用&#xff0c;点击添加&#xff0c;可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download&#xff08;这是我共享的文件夹&#xff09;&…...