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

代码随想录第33天：动态规划6（完全背包基础）

news 来源：原创 2025/8/25 0:12:11

一、完全平方数（Leetcode 279）

本题与“零钱兑换”基本一致。

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

dp[j]：和为j的完全平方数的最少数量为dp[j]

2.确定递推公式

dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。

此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

3.dp数组初始化

dp[ 0 ]= 0

4.遍历顺序

求组合先物品后背包，求排列先背包后物品

本题求最小次数，哪种顺序都可以，习惯先物品后背包

class Solution:def numSquares(self, n: int) -> int:# 初始化 dp 数组，长度为 n+1，初始值为正无穷（表示无法凑出）# dp[i] 表示凑出数字 i 所需的最少完全平方数数量dp = [float('inf')] * (n + 1)# 凑出数字 0 所需的完全平方数个数为 0dp[0] = 0# 枚举所有可能的完全平方数 i*i（i 从 1 到 sqrt(n)）for i in range(1, int(n ** 0.5) + 1):square = i * i  # 当前的完全平方数# 更新所有大于等于当前平方数的 dp[j]for j in range(square, n + 1):# 状态转移方程：dp[j] 最小为 dp[j - square] + 1dp[j] = min(dp[j], dp[j - square] + 1)# 返回凑出 n 的最少完全平方数个数return dp[n]

二、单词拆分（Leetcode 139）

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

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

2.确定递推公式

if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

3.dp数组初始化

dp[ 0 ]= True

dp = [False] * ( len(s) + 1 )

4.遍历顺序

求组合先物品后背包，求排列先背包后物品

本题物品放入背包是有顺序的，等价于排列问题，所以先遍历背包后遍历物品

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:wordSet = set(wordDict)  # 优化查找效率dp = [False] * (len(s) + 1)dp[0] = True  # 空字符串可以被组成for i in range(1, len(s) + 1):for j in range(i):if dp[j] and s[j:i] in wordSet:dp[i] = Truebreak  # 找到一个可拆分位置即可跳出return dp[len(s)]

三、多重背包理论基础（Kamacoder 56）

有 N 种物品和一个容量为 V 的背包。第i种物品最多有 Mi 件可用，每件耗费的空间是 Ci ，价值是 Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

多重背包和01背包类似，我们只需要将 Mi 件摊开，变成多个“单件的物品”，就转换为01背包问题了。

例如：

你有一种物品 A，重量为 2，价值为 5，你有 13 个 A。
背包容量为 20。
你不能像完全背包那样无限放入 A，也不能像 0-1 背包那样只选一个 A。
你最多只能选 13 个 A，如何放入这些 A，使得价值最大？

为什么不能直接暴力？

for i in range(N):             # 遍历每种物品for j in range(C, w[i], -1):   # 遍历背包容量for k in range(1, nums[i] + 1):  # 枚举每种物品的个数if k * w[i] <= j:dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i])

这种写法的时间复杂度是 O(N * C * M)，其中 M 是物品最大数量。如果 M 很大，比如 10^5，就会超时。

1.解决办法：二进制拆分优化

原理：任何一个正整数都可以用不重复的二进制数之和表示。例如：

13 = 1 + 2 + 4 + 6（剩余部分）
19 = 1 + 2 + 4 + 8 + 4（最后一个4是19-15）

⛳ 也就是说，我们可以把 13 个物品拆分成若干批次：1个、2个、4个、剩下6个物品。

原始数量：13
k = 1      -> 拆出 1 个
剩余 = 12
k = 2      -> 拆出 2 个
剩余 = 10
k = 4      -> 拆出 4 个
剩余 = 6
k = 8      -> 拆不出8个（超过了），所以拆出剩下的 6 个
完成拆分：1, 2, 4, 6（共13个）

问题：

背包容量 C = 10
有一种物品：重量 = 2，价值 = 3，数量 = 5

你不能直接一次枚举 0~5 个的所有组合。我们改用二进制拆分优化。

拆分：

5 可以拆成 1, 2, 2（即 1 + 2 + 2 = 5）

那么我们等价于有 3 个 01背包物品：

一个重量 2，价值 3 的物品（1 个）
一个重量 4（2×2），价值 6（3×2）的物品（2 个）
一个重量 4，价值 6 的物品（再 2 个）

再用 0-1 背包处理这些分拆后的“独立物品”。

好处？

原来要枚举 0~5 的所有选择，共 6 种情况。
拆成二进制后，最多只需要 log2(数量) 次枚举（时间复杂度从线性降到对数）。

# 读取输入：C 表示背包容量，N 表示物品种类数量
C, N = map(int, input().split())# 分别读取每个物品的重量、价值和数量
weights = list(map(int, input().split()))  # 每个物品的重量
values = list(map(int, input().split()))   # 每个物品的价值
nums = list(map(int, input().split()))     # 每个物品的数量# 初始化一维 dp 数组，dp[j] 表示容量为 j 的背包可以获得的最大价值
dp = [0] * (C + 1)# 遍历每一个物品
for i in range(N):w, v, m = weights[i], values[i], nums[i]  # 当前物品的重量、价值和数量k = 1  # 用于二进制拆分（从1开始，每次乘2）# 将物品数量 m 拆成多个 2 的幂形式（如 1, 2, 4, 8...），直到耗尽 mwhile m > 0:cnt = min(k, m)  # 本次拆分出来的个数不能超过剩余数量 mm -= cnt         # 减去本次已处理的数量# 将 cnt 个该物品当作一个“01背包物品”处理# 倒序遍历背包容量，确保每个物品只被使用一次（01背包）for j in range(C, w * cnt - 1, -1):dp[j] = max(dp[j], dp[j - w * cnt] + v * cnt)  # 状态转移方程k <<= 1  # k *= 2，下一轮准备拆更大的 2 的幂# 最终输出背包容量为 C 时的最大价值
print(dp[-1])

代码随想录第33天：动态规划6（完全背包基础）

一、完全平方数（Leetcode 279） 本题与“零钱兑换”基本一致。 1.确定dp数组以及下标的含义 dp[j]：和为j的完全平方数的最少数量为dp[j] 2.确定递推公式 dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] 1 便可以凑成dp[j]。 …...

编程日记 2025/8/25 0:12:11

Android控件View、ImageView、WebView用法

一控件清单 View、ImageView、WebView 二控件UI代码 <?xml version="1.0" encoding="utf-8"?> <androidx.coordinatorlayout.widget.CoordinatorLayoutxmlns:android="http://schemas.android.com/apk/res/android"xmlns:app=&qu…...

编程日记 2025/8/23 1:00:06

关于浏览器页面自动化操作

Selenium 是一个用于自动化浏览器操作的强大框架，广泛应用于Web应用程序的测试自动化。它主要由以下几个核心组件组成： Selenium WebDriver： WebDriver 是 Selenium 的核心组件，它提供了一组API，允许开发者编写程序来…...

编程日记 2025/8/25 0:07:56

P5739 计算阶乘详解

此题目，对于会递归的很简单很简单，但作者是野人不会，只能是边刷边学，且题解比较有意思，所有我这次的重心不是题目，而是题解里面创作者展示的不一样的东西，先看题目题目要求不用for循环&#xf…...

编程日记 2025/8/25 0:07:56

把Android设备变成“国标摄像头”：GB28181移动终端实战接入指南

把Android设备变成“国标摄像头”：GB28181移动终端实战接入指南 ——执法记录仪、巡检终端、布控球，如何通过大牛直播SDK直接挂到GB28181平台？ 在过去，GB28181 通常用于固定摄像头、NVR等“设备端”。但在政务、安防、应急等行业…...

编程日记 2025/8/25 0:09:40

机器学习项目流程极简入门：从数据到部署的完整指南

前言本文将通过一个简单案例（根据水果外观特征判断是否为橘子），逐步拆解机器学习项目的完整流程，帮助读者掌握从数据收集到模型部署的全流程方法论。通常，一个完整的机器学习项目可以分为以下几个步骤： …...

编程日记 2025/8/23 10:20:01

PrivKV: Key-Value Data Collection with Local Differential Privacy论文阅读

文献阅读课需要制作ppt但是感觉选的这篇论文都是公式，决定做点动画直观展示一下。还没有完成会继续更新这个笔记 manim动画代码需要下载ffmpeg下载latex https://docs.manim.org.cn/getting_started/installation.html ffmpeg下载教程 texlive官网但是其实不需要…...

编程日记 2025/8/23 13:40:03

RViz（机器人可视化工具）的配置文件（moveitcpp）

1. Panels（面板设置） 面板是RViz界面中的各个功能区域，用于显示和操作不同的数据。 Displays（显示面板） Class: rviz_common/Displays 指定面板的类型，这里是显示面板。 Help Height: 78 帮助区域的高度…...

编程日记 2025/8/24 16:59:23

kotlin 01flow-StateFlow 完整教程

一 Android StateFlow 完整教程：从入门到实战 StateFlow 是 Kotlin 协程库中用于状态管理的响应式流，特别适合在 Android 应用开发中管理 UI 状态。本教程将带全面了解 StateFlow 的使用方法。 1. StateFlow 基础概念 1.1 什么是 StateFlow? StateF…...

编程日记 2025/8/23 20:40:03

OpenGl实战笔记（1）基于qt5.15.2+mingw64+opengl绘制三角形

一、实现效果二、实现原理 （1）各函数作用与原理 initialize() 作用： 初始化 OpenGL 函数（initializeOpenGLFunctions()） 设置背景清除颜色为 rgba(0.2, 0.3, 0.4, 1.0)。原理： initializeOpenGLFunctio…...

编程日记 2025/8/23 2:30:26

S100平台调试RS485/RS232

提供一个C语言的测试程序Demo #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h>...

编程日记 2025/8/23 13:20:14

蓝桥杯 19. 植树

植树题目描述小明和朋友们一起去郊外植树，他们带了一些在实验室中精心研究出的小树苗。一共有 n 个人，每个人挑选了一个适合植树的位置，一共 n 个位置。每人准备在自己的位置种下一棵树苗。但他们遇到一个问题：有的树苗比…...

编程日记 2025/8/23 19:40:02

Spring Boot 中 @Bean 注解详解：从入门到实践

在 Spring Boot 开发中，Bean注解是一个非常重要且常用的注解，它能够帮助开发者轻松地将 Java 对象纳入 Spring 容器的管理之下，实现对象的依赖注入和生命周期管理。对于新手来说，理解并掌握Bean注解，是深入学习 Spring…...

编程日记 2025/8/22 5:49:59

git项目迁移，包括所有的提交记录和分支 gitlab迁移到gitblit

之前git都是全新项目上传，没有迁移过，因为迁移的话要考虑已有项目上的分支都要迁移过去，提交记录能迁移就好；分支如果按照全新项目上传的方式需要新git手动创建好老git已有分支，在手动一个一个克隆老项目分支代码依次提…...

编程日记 2025/8/21 2:30:03

前端面试每日三题 - Day 25

这是我为准备前端/全栈开发工程师面试整理的第25天每日三题练习，涵盖了： CSS中如何实现一个保持宽高比的自适应正方形元素Angular的变更检测（Change Detection）机制项目实战 - 设计一个微前端架构的前端应用。 ✅ 题目1&#xff…...

编程日记 2025/8/21 18:43:23

基于windows安装MySQL8.0.40

基于windows安装MySQL8.0.40 基于windows 安装 MySQL8.0.40，解压文件到D:\mysql-8.0.40-winx64 在D:\mysql-8.0.40-winx64目录下创建my.ini文件，并更新一下内容 [client] #客户端设置，即客户端默认的连接参数 # 设置mysql客户端连接服务…...

编程日记 2025/8/21 18:43:21

基于机器学习算法预测二手车市场数据清洗与分析平台（源码+定制+讲解）基于Python的数据挖掘与可视化二手车数据处理与分析系统开发 (机器学习算法预测）

博主介绍： ✌我是阿龙，一名专注于Java技术领域的程序员，全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师，我在计算机毕业设计开发方面积累了丰富的经验。同时，我也是掘金、华为云、阿里云、InfoQ等平台…...

编程日记 2025/8/23 5:48:51

【神经网络与深度学习】普通自编码器和变分自编码器的区别

引言自编码器（Autoencoder，AE）和变分自编码器（Variational Autoencoder，VAE）是深度学习中广泛应用的两类神经网络结构，主要用于数据的压缩、重构和生成。然而，二者在模型设计、训练…...

编程日记 2025/8/21 18:43:17

【现代深度学习技术】现代循环神经网络07：序列到序列学习（seq2seq）

【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈PyTorch深度学习 ⌋ ⌋ ⌋ 深度学习 (DL, Deep Learning) 特指基于深层神经网络模型和方法的机器学习。它是在统计机器学习、人工神经网络等算法模型基础上，结合当代大数据和大算力的发展而发展出来的。深度学习最重…...

编程日记 2025/8/21 18:43:14

【Linux我做主】进度条小程序深度解析

Linux下C语言进度条程序深度解析进度条小程序GitHub地址前言前置知识回车换行（CR/LF）的深度解析历史渊源与技术规范在进度条/倒计时中的应用缓冲区机制的全面剖析缓冲区引入缓冲类型对比进度条开发中的关键控制进度条实现以小见大——倒计时倒计时最…...

编程日记 2025/8/21 16:45:49

Vue项目安全实践指南：从输入验证到状态管理的全方位防护

一、项目背景在Vue2项目开发过程中，我们遇到了一些需要优化的安全实践问题。本文将分享我们在项目中的一些安全优化经验，希望能帮助到其他开发者。主要优化点： 输入输出安全处理请求安全防护数据存储安全路由访问控制文件上传处理表单数…...

编程日记 2025/8/21 20:08:12

Pinocchio导入URDF关节为continuous的问题及详细解释

视频讲解： Pinocchio导入URDF关节为continuous的问题及详细解释仓库地址：GitHub - LitchiCheng/mujoco-learning 问题背景：打算测试将之前的panda的urdf换成so-arm100的urdf，发现pinocchio的代码不能用，很奇怪&#…...

编程日记 2025/8/21 18:43:12

《Python星球日记》第30天：Flask数据库集成

名人说：路漫漫其修远兮，吾将上下而求索。—— 屈原《离骚》创作者：Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder😊） 专栏：《Python星球日记》，限时特价订阅中ing 目录一、数据库…...

编程日记 2025/8/22 19:44:03

GAF-CNN-SSA-LSSVM故障诊断/分类预测，附带模型研究报告（Matlab）

GAF-CNN-SSA-LSSVM故障诊断/分类预测，附带模型研究报告（Matlab） 目录 GAF-CNN-SSA-LSSVM故障诊断/分类预测，附带模型研究报告（Matlab）效果一览基本描述程序设计参考资料效果一览基本描述本研究提出的GA…...

编程日记 2025/8/21 12:34:33

轻松养生：让健康融入生活

养生不是负担，而是可以轻松融入日常的生活方式。掌握以下要点，就能开启健康之旅。清晨醒来，先喝一杯常温水，唤醒沉睡的肠胃。早餐选择富含膳食纤维的燕麦片搭配新鲜水果，补充能量又促进消化。午餐和晚餐做到荤素搭配&…...

编程日记 2025/8/24 1:57:06

工业主义与民主的兴衰：历史逻辑与未来危机

一、工业主义催生大众民主的机制经济基础变革非技术工人崛起：工业革命后，机器生产替代传统手工业，非熟练工人（包括妇女、儿童）收入提升，财富分配趋于平等，形成新兴中产阶级。政府财政能力增…...

编程日记 2025/8/23 20:05:01

从代码学习深度学习 - 目标检测前置知识(二) PyTorch版

文章目录前言一、多尺度目标检测1.1 多尺度锚框1.2 绘图工具函数 (`utils_for_huitu.py`)1.3 可视化多尺度锚框1.4 多尺度检测（理论）二、自定义目标检测数据集2.1 读取数据2.2 创建 Dataset 类2.3 创建 DataLoader2.4 验证数据加载2.5 可视化数据集样本总结前言大家好！欢…...

编程日记 2025/8/21 11:45:22

什么是“系统调用”

一、什么是“系统调用”？用生活中的比喻理解可以把“系统调用”比作你（用户）向“管理员”请求帮助完成某件事情的过程。举个例子： 你想借书，去图书馆（操作系统）找管理员（内核&a…...

编程日记 2025/8/21 18:43:04

代码异味（Code Smell）识别与重构指南

1、引言：什么是“代码异味”？在软件开发中，“代码异味（Code Smell）”是指那些虽然不会导致程序编译失败或运行错误，但暗示着潜在设计缺陷或可维护性问题的代码结构。它们是代码演进过程中的“信号灯”，提示我们某段代码可能需要优化。 1.1 ✅ 为什么关注代码异味？预…...

编程日记 2025/8/21 18:43:02

005-nlohmann/json 基础方法-C++开源库108杰

《二、基础方法》：节点访问、值获取、显式 vs 隐式、异常处理、迭代器、类型检测、异常处理……一节课搞定C处理JSON数据85%的需求…… JSON 字段的简单类型包括：number、boolean、string 和 null（即空值）；复杂类型则有…...

编程日记 2025/8/21 18:43:00

java学习之数据结构：四、树（代码补充）

这部分主要是用代码实现有序二叉树、树遍历、删除节点目录 1.构建有序二叉树 1.1原理 1.2插入实现 2.广度优先遍历--队列实现 3.深度优先遍历--递归实现 3.1先序遍历 3.2中序遍历 3.3后序遍历 4.删除 4.1删除叶子节点 4.2删除有一棵子树的节点 4.3删除有两棵子树的节…...

编程日记 2025/8/21 4:20:37

Java面试场景分析：从音视频到安全与风控的技术探讨

Java面试场景分析：从音视频到安全与风控的技术探讨在一个阳光明媚的早晨，互联网大厂的面试室里，面试官李老师坐在桌前，严肃认真；而程序员小张则显得有些紧张，甚至有些搞笑。第一轮提问： 李老…...

编程日记 2025/8/21 18:42:57

《OmniMeetProTrack 全维会议链智能追录系统软件设计文档》

撰稿人：wjz 一、引言 1.1 目的本软件设计文档详细描述了 OmniMeetProTrack 全维会议链智能追录系统的架构、组件、模块设计及实现细节，旨在为开发人员、利益相关者和维护人员提供系统的全面设计蓝图。本文档基于需求定义文档，确保系统实现…...

编程日记 2025/8/21 20:08:10

C 语言逻辑运算符：组合判断，构建更复杂的条件

各类资料学习下载合集 https://pan.quark.cn/s/8c91ccb5a474 在 C 语言编程中，我们已经学习了如何使用比较运算符（如 ==, <, >）来判断两个值之间的关系，从而得到“真”或“假”的结果。但很多时候，我们需要根据多个条件的组合…...

编程日记 2025/8/23 2:30:34

大模型推理框架简介

概述通常需要大量的计算资源，高效运行LLMs仍然是一个挑战， 推理框架作为LLM高效部署的关键组件，直接关系到应用的性能、成本和开发效率。高性能框架 vLLM GitHub，由SKYPILOT构建的推理优化框架，旨在提高在GPU上…...

编程日记 2025/8/21 20:08:06

《MATLAB实战训练营：从入门到工业级应用》高阶挑战篇-《5G通信速成：MATLAB毫米波信道建模仿真指南》

《MATLAB实战训练营：从入门到工业级应用》高阶挑战篇-5G通信速成：MATLAB毫米波信道建模仿真指南 🚀📡 大家好！今天我将带大家进入5G通信的奇妙世界，我们一起探索5G通信中最激动人心的部分之一——毫米波信…...

编程日记 2025/8/22 7:26:00

word导出pdf带有目录导航栏-error记

1、打开word文档——>点击"视图"选项卡——>勾选"导航窗格" 2、点击"文件"——>导出——>创建PDF/XPS 3、点击"选项"——>勾选"创建书签时使用(C)" "标题(H)" 4、点击"确定"——>点击…...

编程日记 2025/8/21 20:08:02

word怎么删除空白页？word最后一页删不掉怎么办

在使用word的过程中，有时出现空白页就可能会给大家带来一些困扰。到底怎么样才能把这些空白页删除，又应该如何解决最后也删不掉的问题呢？ 要想删除普通的空白页，那就需要将光标直接放在空白页，然后按【Delete】键&…...

编程日记 2025/8/23 10:12:08

虚幻基础：硬件输入

文章目录 triggered：按下一直触发等于tickcompleted：必须等到triggered结束后才触发松下triggered结束默认按键触发顺序按下：触发两个先 Started后 Triggered 松开Completed 触发器：用于修改triggered 触发和结束驱动阈值&…...

编程日记 2025/8/21 20:07:58

【Java ee初阶】多线程（5）

一、wait 和 notify wait notify 是两个用来协调线程执行顺序的关键字，用来避免“线程饿死”的情况。 wait 和 notify 其实都是 Object 这个类的方法，而 Object这个类是所有类的“祖宗类”，也就是说明，任何一个类，都…...

编程日记 2025/8/21 20:07:56

售前赢单评分是越权吗？

相关文章软件实施工作个人看法当前部门软件产品经理的职责涵盖售前支持工作。此前梳理工作时，计划在每个售前支持项目完成后，由支持人对项目赢单概率进行评估，旨在通过这一机制筛选重点项目，为赢单率高的项目优先配置资源。 …...

编程日记 2025/8/21 20:07:53

uniapp中用canvas绘制简单柱形图，小容量，不用插件——简单使用canvas

uniapp中用canvas绘制简单柱形图，小容量，不用插件——简单使用canvas 完整代码 <template><view><view class"navTab"><view :class"listIndexi?activite:"…...

编程日记 2025/8/21 20:07:51

SecureCRT 使用指南：安装、设置与高效操作

目录一、SecureCRT 简介 1.1 什么是 SecureCRT？ 1.2 核心功能亮点 1.3 软件特点二、SecureCRT 安装与激活 2.1 安装步骤（Windows 系统） 2.2 激活与破解（仅供学习参考） 三、基础配置与优化 3.1 界面与编码设…...

编程日记 2025/8/21 11:15:57

WebRTC 服务器之SRS服务器概述和环境搭建

1.概述 SRS（Simple Realtime Server）是一款高性能、跨平台的流媒体服务器，支持多种协议，包括 RTMP、WebRTC、HLS、HTTP-FLV、SRT、MPEG-DASH 和 GB28181。本文介绍了 SRS，包括其用途、关键功能、架构和支持协议。SRS 旨…...

编程日记 2025/8/21 20:07:47

第R8周：RNN实现阿尔兹海默病诊断（pytorch）

- **🍨 本文为[🔗365天深度学习训练营](https://mp.weixin.qq.com/s/rnFa-IeY93EpjVu0yzzjkw) 中的学习记录博客** - **🍖 原作者：[K同学啊](https://mtyjkh.blog.csdn.net/)** 一：前期准备工作 1.设置硬件设备 impo…...

编程日记 2025/8/21 20:07:45

vue+element 导航实现例子

项目使用的是 vue 3，安装配置可以查看栏目前面的文章。组件导航：https://element-plus.org/zh-CN/component/menu.html 面包屑：https://element-plus.org/zh-CN/component/breadcrumb.html 安装element库 PS D:\code\my-vue3-project&g…...

编程日记 2025/8/21 20:07:43