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

手把手教你优化SiC MOSFET模块:从铜带键合到双面散热的5个关键技术

SiC MOSFET功率模块封装优化实战&#xff1a;五大关键技术深度解析 在电力电子领域&#xff0c;碳化硅(SiC)MOSFET功率模块正逐步取代传统硅基IGBT&#xff0c;成为高效率、高功率密度应用的首选。然而&#xff0c;要充分发挥SiC材料的性能优势&#xff0c;封装技术面临前所未…...

FlowState Lab新手避坑指南:快速上手时间序列预测的5个技巧

FlowState Lab新手避坑指南&#xff1a;快速上手时间序列预测的5个技巧 1. 环境准备与快速部署 1.1 系统要求与安装步骤 FlowState Lab作为基于IBM Granite架构的时间序列分析工具&#xff0c;对运行环境有以下要求&#xff1a; 操作系统&#xff1a;Linux (推荐Ubuntu 20.…...

tao-8k在AI应用开发中的价值:为LangChain+LlamaIndex提供高质量向量底座

tao-8k在AI应用开发中的价值&#xff1a;为LangChainLlamaIndex提供高质量向量底座 1. 为什么需要高质量的文本嵌入模型 在构建AI应用时&#xff0c;我们经常需要将文本转换为计算机能够理解的数值表示&#xff0c;这就是文本嵌入&#xff08;embedding&#xff09;的核心任务…...

OptiLLM性能基准测试:在AIME、IMO、LiveCodeBench上的惊人表现

OptiLLM性能基准测试&#xff1a;在AIME、IMO、LiveCodeBench上的惊人表现 【免费下载链接】optillm Optimizing inference proxy for LLMs 项目地址: https://gitcode.com/gh_mirrors/op/optillm OptiLLM是一款强大的AI推理优化代理工具&#xff0c;能够在零训练的情况…...

Simula:革命性Linux VR桌面窗口管理器完全指南

Simula&#xff1a;革命性Linux VR桌面窗口管理器完全指南 【免费下载链接】Simula Linux VR Desktop 项目地址: https://gitcode.com/gh_mirrors/si/Simula Simula是一款专为Linux系统打造的革命性VR桌面窗口管理器&#xff0c;它将传统的桌面操作体验带入虚拟现实空间…...

YOLO X Layout案例集:10类典型文档(发票/简历/论文/合同/说明书)Layout识别效果汇总

YOLO X Layout案例集&#xff1a;10类典型文档Layout识别效果汇总 获取更多AI镜像 想探索更多AI镜像和应用场景&#xff1f;访问 CSDN星图镜像广场&#xff0c;提供丰富的预置镜像&#xff0c;覆盖大模型推理、图像生成、视频生成、模型微调等多个领域&#xff0c;支持一键部署…...

Ollama部署LFM2.5-1.2B-Thinking:从CSDN文档到实际调用的完整链路

Ollama部署LFM2.5-1.2B-Thinking&#xff1a;从CSDN文档到实际调用的完整链路 1. 认识LFM2.5-1.2B-Thinking模型 LFM2.5-1.2B-Thinking是一个专门为设备端部署设计的智能文本生成模型。这个模型属于LFM2.5系列&#xff0c;是在LFM2架构基础上通过扩展预训练和强化学习进一步优…...

django基于在线音乐分享的社交网站全vue

目录功能模块划分技术架构设计核心功能实现性能优化方案测试策略部署方案项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作功能模块划分 用户模块 注册/登录&#xff08;邮箱/手机号验证&#xff09;个人资料管理&#xff08;头像…...

实测分享:用Miniconda-Python3.10镜像快速创建独立开发环境

实测分享&#xff1a;用Miniconda-Python3.10镜像快速创建独立开发环境 1. 为什么需要独立Python环境 在日常开发中&#xff0c;我们经常会遇到这样的困扰&#xff1a;不同项目依赖的Python包版本冲突&#xff0c;导致项目无法正常运行。比如项目A需要TensorFlow 2.4&#xf…...

如何保证代码质量?

一、编码阶段&#xff1a;从源头控制质量1. 统一代码规范&#xff08;强制执行&#xff09;核心目标&#xff1a;减少风格差异&#xff0c;提高可读性常见工具&#xff1a;ESLint&#xff1a;代码规范校验Prettier&#xff1a;自动格式化Stylelint&#xff1a;样式规范&#x1…...