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

动态规划：多重背包

news 来源：原创 2025/8/24 8:23:40

本题力扣上没有原题，大家可以去卡码网第56题 (opens new window)去练习，题意是一样的。

56. 携带矿石资源（第八期模拟笔试）

题目描述

你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。

给定一个宇航舱，最大容量为 C。现在有 N 种不同类型的矿石，每种矿石有一个重量 w[i]，一个价值 v[i]，以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下，最大化你所能获取的总价值。

输入描述

输入共包括四行，第一行包含两个整数 C 和 N，分别表示宇航舱的容量和矿石的种类数量。

接下来的三行，每行包含 N 个正整数。具体如下：

第二行包含 N 个整数，表示 N 种矿石的重量。

第三行包含 N 个整数，表示 N 种矿石的价格。

第四行包含 N 个整数，表示 N 种矿石的可用数量上限。

输出描述

输出一个整数，代表获取的最大价值。

输入示例

输出示例

提示信息

数据范围：
1 <= C <= 2000;
1 <= N <= 100;
1 <= w[i], v[i], k[i] <= 1000;

思路：把多重背包当成0-1背包来做

题解1 （潜在数组越界过不了）

def knapsack(c, n, weight, value, use):dp = [0]*(c+1)weight_update = []value_update = []for i in range(n):for j in range(use[i]):weight_update.append(weight[i])value_update.append(value[i])item_count = len(weight_update)for i in range(item_count):for j in range(c, weight_update[i]-1, -1):dp[j] = max(dp[j], dp[j-weight_update[i]]+value_update[i])return dp[c]c, n = map(int, input().split())
weight = []
value = []
use = []
#total 里面的元素被更新后，weight、value 和 use 这三个数组也会同步更新。
# 这是因为在 Python 中，列表是可变对象，而 total 中的元素是对 weight、value 和 use 的引用，而不是它们的副本。
total = [weight, value, use]
for item in total:item.extend(map(int, input().split())) # extend将一个可迭代对象中的每个元素逐个添加到列表的末尾。它不会将可迭代对象作为一个整体添加，而是将其“展开”后添加
max_value = knapsack(c, n, weight, value, use)
print(max_value)

题解2（AC)

需要剪枝，似乎不能更新数组

def knapsack(c, n, weight, value, use):dp = [0]*(c+1)for i in range(n):for j in range(c, weight[i]-1, -1):for k in range(1, min(use[i] + 1, j//weight[i] + 1)): #剪枝dp[j] = max(dp[j], dp[j-weight[i]*k]+value[i]*k)return dp[c]c, n = map(int, input().split())
weight = []
value = []
use = []
#total 里面的元素被更新后，weight、value 和 use 这三个数组也会同步更新。
# 这是因为在 Python 中，列表是可变对象，而 total 中的元素是对 weight、value 和 use 的引用，而不是它们的副本。
total = [weight, value, use]
for item in total:item.extend(map(int, input().split())) # extend将一个可迭代对象中的每个元素逐个添加到列表的末尾。它不会将可迭代对象作为一个整体添加，而是将其“展开”后添加
max_value = knapsack(c, n, weight, value, use)
print(max_value)

题解3（AC) 优化输入

def knapsack(c, n, weight, value, use):dp = [0]*(c+1)for i in range(n):for j in range(c, weight[i]-1, -1):for k in range(1, min(use[i] + 1, j//weight[i] + 1)): #剪枝dp[j] = max(dp[j], dp[j-weight[i]*k]+value[i]*k)return dp[c]c, n = map(int, input().split())
weight = list(map(int, input().split()))
value = list(map(int, input().split()))
use = list(map(int, input().split()))
max_value = knapsack(c, n, weight, value, use)
print(max_value)

动态规划：多重背包

本题力扣上没有原题，大家可以去卡码网第56题 (opens new window)去练习，题意是一样的。 56. 携带矿石资源（第八期模拟笔试） 题目描述你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类…...

编程日记 2025/8/24 8:23:40

AI编程：一个案例对比CPU和GPU在深度学习方面的性能差异

背景字节跳动正式发布中国首个AI原生集成开发环境工具（AI IDE）——AI编程工具Trae国内版。该工具模型搭载doubao-1.5-pro，支持切换满血版DeepSeek R1&V3， 可以帮助各阶段开发者与AI流畅协作，更快、更高质量地完…...

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

TensorFlow 的基本概念和使用场景

TensorFlow 是一个由 Google 开发的开源深度学习框架，用于构建和训练机器学习模型。它的基本概念包括以下几点： 张量（Tensor）：在 TensorFlow 中，数据以张量的形式表示，张量可以是多维数组&#…...

编程日记 2025/8/21 12:59:10

gRPC学习笔记

微服务一旦某个服务器宕机，会引起整个应用不可用，隔离性差只能整体应用进行伸缩，浪费资源，可伸缩性差代码耦合在一起，可维护性差微服务架构：解决了单体架构的弊端可以按照服务进行单独扩容各个…...

编程日记 2025/8/21 10:12:29

Linux常见指令

Linux常见指令 1、ls指令2、pwd命令3、cd指令4、touch指令5、mkdir指令6、rmdir指令和rm指令7、man指令8、cp指令9、mv指令10、cat指令11、重定向12、more指令13、less指令14、head指令15、tail指令16、管道17、时间相关指令18、cal指令19、find指令20、grep指令21、zip/unzip指…...

编程日记 2025/8/24 8:22:30

1、Vue项目搭建 npm init vuelatest cd 文件目录 npm i npm run dev // npm run _ 这个在package.json中查看scripts /* vue_study\.vscode可删 // vue_study\src\components也可删除(基本语法，不使用组件) */ // vue_study\.vscode\lau…...

编程日记 2025/8/24 8:21:33

用OpenCV写个视频播放器可还行？（C++版）

引言提到OpenCV，大家首先想到的可能是图像处理、目标检测，但你是否想过——用OpenCV实现一个带进度条、倍速播放、暂停功能的视频播放器？本文将通过一个实战项目，带你深入掌握OpenCV的视频处理能力，并解锁以下功能&a…...

编程日记 2025/8/21 8:34:10

clion+arm-cm3+MSYS-mingw +jlink配置用于嵌入式开发

0.前言正文可以跳过这段初识clion，应该是2015年首次发布的时候， 那会还是大三，被一则推介广告吸引到，当时还在用vs studio，但是就喜欢鼓捣新工具，然后下载安装试用了clion，但是当时对cmake规…...

编程日记 2025/8/23 17:59:11

物联网-IoTivity：开源的物联网框架

IoTivity 是一个开源的物联网（IoT）框架，旨在为物联网设备提供互操作性、安全性和可扩展性。它由 Open Connectivity Foundation (OCF) 主导开发，遵循 OCF 的标准，致力于实现设备之间的无缝连接和通信。IoTivity 提供了一个统一的框架，支持设备发现、数据交换、设备管理和…...

编程日记 2025/8/16 10:06:30

Acrobat DC v25.001 最新专业版已破，像word一样编辑PDF！

在数字化时代，PDF文件以其稳定性和通用性成为了文档交流和存储的热门选择。无论是阅读、编辑、转换还是转曲，大家对PDF文件的操作需求日益增加。因此，一款出色的PDF处理软件不仅要满足多样化的需求，还要通过简洁的界面和强大的功能…...

编程日记 2025/8/22 22:16:32

【c++】模板进阶

在前面我们学习了模板的基础用法【c】模板初阶-CSDN博客初步认识了函数模板和类模板，接下来让我们看看模板还有哪些进阶的应用。非类型模板参数之前我们用到的模板全都使用了类型参数类型参数：表示某种数据类型（如 int、double、自定义…...

编程日记 2025/8/21 21:39:58

IntelliJ IDEA 2021版创建springboot项目的五种方式

第一种方式，通过https://start.spring.io作为spring Initializr的url来创建项目。第二种方式，通过https://start.spring.io官网来直接创建springboot项目压缩包，然后导入至我们的idea中。点击generate后，即可生成压缩包&#xf…...

编程日记 2025/8/19 10:38:35

数字信号处理之信号功率谱计算welch方法（分段加窗平均周期图）、Bartlett方法（周期图）（Python)

welch方法原理说明 welch方法[1]通过将数据划分为重叠的段，计算每个段的进行修改(加窗)后的周期图，然后对所有段的周期图求和进行平均，得到最终的功率谱密度。 Python和Matlab中均存在welch函数。welch函数通过配置noverlap为0，可…...

编程日记 2025/8/21 11:58:40

【面试】Java 基础

基础 1、Java 中几种基本数据类型什么，各自占用多少字节2、基本数据同包装类的区别3、Java 基本类型的参数传递和引用类型的参数传递有啥区别4、隐式类型转换和显式类型转换5、switch 语句表达式结果的类型6、数组的扩容方式7、面向对象三大特征8、静态变量和成员变…...

编程日记 2025/8/22 15:51:37

【工具使用】IDEA 社区版如何创建 Spring Boot 项目（详细教程）

IDEA 社区版如何创建 Spring Boot 项目（详细教程） Spring Boot 以其简洁、高效的特性，成为 Java 开发的主流框架之一。虽然 IntelliJ IDEA 专业版提供了Spring Boot 项目向导，但社区版（Community Edition&#xff09…...

编程日记 2025/8/23 3:24:53

CTFHub-FastCGI协议/Redis协议

将木马进行base64编码 <?php eval($_GET[cmd]);?> 打开kali虚拟机，使用虚拟机中Gopherus-master工具 Gopherus-master工具安装 git clone https://github.com/tarunkant/Gopherus.git 进入工具目录 cd Gopherus 使用工具 python2 "位置" --expl…...

编程日记 2025/8/23 12:09:19

【Python字符串】\n是什么？它与raw字符串、多行字符串的运用有什么关系？

李升伟整理在Python中，\n 是换行符，用于在字符串中表示新的一行。当你在字符串中使用 \n 时，Python 会在该位置插入一个换行符，使得输出在 \n 处换行。 1. 普通字符串中的 \n 在普通字符串中，\n 会被解释为换行符…...

编程日记 2025/8/20 2:34:33

Linux 配置静态 IP

一、简介在 Linux CentOS 系统中默认动态分配 IP 地址，每次启动虚拟机服务都是不一样的 IP，因此要配置静态 IP 地址避免每次都发生变化，下面将介绍配置静态 IP 的详细步骤。首先先理解一下动态 IP 和静态 IP 的概念： 动态 IP…...

编程日记 2025/8/22 10:43:18

git lfs使用方法指南【在github保存100M以上大文件】

为了在 GitHub 仓库中存储超过 100MB 的大文件并避免推送失败，使用 Git LFS（Large File Storage） 是最佳解决方案。以下是详细步骤： 一、安装 Git LFS 下载并安装 Git LFS： 访问 Git LFS 官网下载对应系统的安装包。或…...

编程日记 2025/8/19 16:42:06

【Linux】初识线程

目录一、什么是线程： 重定义线程和进程： 执行流： Linux中线程的实现方案： 二、再谈进程地址空间三、小结： 1、概念： 2、进程与线程的关系： 3、线程优点： 4、线程…...

编程日记 2025/8/22 17:20:23

【Linux学习笔记】Linux基本指令分析和权限的概念

【Linux学习笔记】Linux基本指令分析和权限的概念 🔥个人主页：大白的编程日记 🔥专栏：Linux学习笔记文章目录【Linux学习笔记】Linux基本指令分析和权限的概念前言一. 指令的分析1.1 alias 指令1.2 grep 指令1.3 zip/unzip 指…...

编程日记 2025/8/23 7:22:35

uniapp登录用户名在其他页面都能响应

使用全局变量 1、在APP.vue中定义一个全局变量，然后在需要的地方引用它； <script>export default {onLaunch: function() {console.log(App Launch)this.globalData { userInfo: {} };},onShow: function() {console.log(App Show)},onHide: fu…...

编程日记 2025/8/22 14:37:29

ESP8266 入门（第 2 部分）：使用 AT 命令

使用 AT 命令对 WiFi 收发器ESP8266编程本教程是上一个教程 ESP8266 入门（第 1 部分）的延续。因此，简单回顾一下，在之前的教程中，我们介绍了 ESP 模块，并学习了一些基础知识。我们还使用 FTDI 串行适配器模块制作了一个开发板，该模块可以很容易地用于使用 AT 命令和 A…...

编程日记 2025/8/24 4:54:37

介绍一下Qt 中的QSizePolicy 布局策略

在 Qt 中，QSizePolicy 类用于描述一个控件在布局中如何分配空间，它定义了控件在水平和垂直方向上对空间的需求和响应策略。以下是对 QSizePolicy 策略的详细介绍： 基本概念 QSizePolicy 包含两个主要的属性：Policy（策…...

编程日记 2025/8/22 11:18:35

从ETL到数仓分层：大数据处理的“金字塔”构建之道

在当今数据驱动的时代，大数据处理已成为企业决策和业务优化的核心。而ETL（Extract, Transform, Load）作为数据处理的基石，其背后的数仓分层理念更是决定了数据处理的效率与质量。本文将深入探讨ETL工作中的数仓分层理念&#xff0…...

编程日记 2025/8/19 3:05:55

springBoot集成声明式和编程式事务的方式

一、声明式事务前提集成了mybatisplus插件 1、pom依赖 <dependencies><dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><version>3.5.3.4&l…...

编程日记 2025/8/18 22:17:15

前端实现版本更新自动检测✅

🤖 作者简介：水煮白菜王，一位资深前端劝退师 👻 👀 文章专栏： 前端专栏 ，记录一下平时在博客写作中，总结出的一些开发技巧和知识归纳总结✍。感谢支持💕💕&a…...

编程日记 2025/8/16 11:40:42

Python零基础学习第三天：函数与数据结构

一、函数基础函数是什么？ 想象你每天都要重复做同一件事，比如泡咖啡。函数就像你写好的泡咖啡步骤说明书，每次需要时直接按步骤执行，不用重新想流程。 # 定义泡咖啡的函数 def make_coffee(sugar1): # 默认加1勺糖 print("…...

编程日记 2025/8/22 22:08:33

深入了解Linux —— 调试程序

前言我们已经学习了linux下许多的工具，vim、gcc、make/makefile等； 已经能够在linux写代码，并且进行编译运行，让程序在linux下跑起来。但是，如果我们在写代码的时候遇见了错误；但是我们并不知道错误在哪&…...

编程日记 2025/8/20 14:48:18

解决VScode 连接不上问题

问题 ：VScode 连接不上解决方案： 1、手动杀死VS Code服务器进程，然后重新尝试登录打开xshell ，远程连接服务器 ，查看vscode的进程 ，然后全部杀掉 [cxqiZwz9fjj2ssnshikw14avaZ ~]$ ps ajx | grep vsc…...

编程日记 2025/8/16 10:11:01

行式数据库与列式数据库区别

列式数据库（Columnar Database）和行式数据库（Row-based Database）是两种不同的数据存储和检索方式，它们在数据组织、存储结构和适用场景上有显著区别。以下是对两者的详细对比： 1. 数据存储方式行式数据库…...

编程日记 2025/8/19 7:22:47

如何将本地已有的仓库上传到gitee （使用UGit）

1、登录Gitee。 2、点击个人头像旁边的加号，选择新建仓库： 3、填写仓库相关信息 4、复制Gitee仓库的地址 5、绑定我们的本地仓库与远程仓库 6、将本地仓库发布（推送）到远程仓库： 注意到此处报错&#xff…...

编程日记 2025/8/16 13:01:17

FIWARE：开源的物联网平台，支持设备虚拟化和数据管理

FIWARE 是一个开源的物联网（IoT）平台，旨在为物联网应用提供强大的数据管理和设备虚拟化功能。FIWARE 提供了一系列通用的 API 和组件，支持设备管理、数据采集、数据处理、数据共享和安全通信等功能，使得开发者能够快速构建和扩展物联网解决方案。以下是 FIWARE 的核心功能…...

编程日记 2025/8/22 5:21:17

RISC-V汇编学习（三）—— RV指令集

有了前两节对于RISC-V汇编、寄存器、汇编语法等的认识，本节开始介绍RISC-V指令集和伪指令。前面说了RISC-V的模块化特点，是以RV32I为作为ISA的核心模块，其他都是要基于此为基础，可以这样认为：RISC-V ISA 基本整数指…...

编程日记 2025/8/16 10:11:30

【Linux】冯诺依曼体系与操作系统理解

🌟🌟作者主页：ephemerals__ 🌟🌟所属专栏：Linux 目录前言一、冯诺依曼体系结构二、操作系统 1. 操作系统的概念 2. 操作系统存在的意义 3. 操作系统的管理方式 4. 补充：理解系统调用…...

编程日记 2025/8/18 14:17:40

Android15使用FFmpeg解码并播放MP4视频完整示例

效果: 1.编译FFmpeg库：下载FFmpeg-kit的源码并编译生成安装平台库 2.复制生成的FFmpeg库so文件与包含目录到自己的Android下如果没有prebuiltLibs目录，创建一个，然后复制包含目录只复制arm64-v8a下...

编程日记 2025/8/16 12:36:12

音视频入门基础：RTP专题（16）——RTP封装音频时，音频的有效载荷结构

一、引言《RFC 3640》和《RFC 6416》分别定义了两种对MPEG-4流的RTP封包方式，这两个文档都可以从RFC官网下载： RFC Editor 本文主要对《RFC 3640》中的音频打包方式进行简介。《RFC 3640》总共有43页，本文下面所说的“页数”是指在pdf阅读…...

编程日记 2025/8/18 3:04:40

3.3.2 Proteus第一个仿真图

文章目录文章介绍0 效果图1 新建“点灯”项目2 添加元器件3 元器件布局接线4 补充文章介绍本文介绍：使用Proteus仿真软件画第一个仿真图 0 效果图 1 新建“点灯”项目修改项目名称和路径，之后一直点“下一步”直到完成 2 添加元器件点击元…...

编程日记 2025/8/22 10:05:34

MySQL创建数据库和表，插入四大名著中的人物

一、登录数据库并创建数据库db_ck 二、创建表t_hero 表属性包括（id，name，nickname，age，gender，address，weapon，types） mysql> create table t_hero(-> id int,-…...

编程日记 2025/8/19 11:53:50

matlab和FPGA联合仿真时读写.txt文件数据的方法

在FPGA开发过程中，往往需要将MATLAB生成的数据作为原始激励灌入FPGA进行仿真。为了验证FPGA计算是否正确，又需要将FPGA计算结果导入MATLAB绘图与MATLAB计算结果对比。下面是MATLAB“写.txt”、“读.txt”，Verilog“读.txt”、“写.txt”的代…...

编程日记 2025/8/16 11:44:03

C++修炼之路：初识C++

Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！ 我的博客：<但凡. 我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》欢迎点赞，关注！ 引言 …...

编程日记 2025/8/21 22:02:03

ACE协议学习1

在多核系统或复杂SoC（System on Chip）中，不同处理器核心或IP（Intellectual Property）模块之间需要保持数据的一致性。常用的是ACE协议or CHI。先对ACE协议进行学习 ACE协议（Advanced Microcontroller Bu…...

编程日记 2025/8/22 17:15:29

通俗易懂的介绍LLM大模型技术常用专业名词（通用版）

1. 神经网络 (Neural Network) 解释: 一种模拟人脑神经元结构的计算模型，用于处理复杂的数据模式。示例: 图像识别中的卷积神经网络（CNN）。 2. 深度学习 (Deep Learning) 解释: 基于多层神经网络的机器学习方法，能够自动提取数…...

编程日记 2025/8/21 9:25:27

深度学习环境安装

Anaconda 3.0 下载地址 Download Success | Anaconda CUDA 下载地址 cuda_12.4.0 https://developer.nvidia.com/cuda-12-4-0-download-archive?target_osWindows&target_archx86_64&target_version11&target_typeexe_local pytorch 下载地址 （2…...

编程日记 2025/8/22 2:09:33

【哇! C++】类和对象（五） - 赋值运算符重载

目录编辑一、运算符重载 1.1 运算符重载概念 1.2 全局运算符重载 1.3 运算符重载为成员函数二、赋值运算符重载的特性 2.1 赋值运算符重载需要注意的点 2.2 赋值运算符重载格式 2.2.1 传值返回 2.2.2 传引用返回 2.2.3 检查自己给自己赋值三、赋值运算符重载的…...

编程日记 2025/8/17 11:28:22

【时序图】1.StarUML绿化

1)下载地址官网: StarUML 如下: 2)绿化 step1:用管理员打开cmd，执行如下 npm install -g asar cd C:\Program Files\StarUML\resources //进入到StarUML的默认安装目录下面 asar extract app.asar app //反编译软件step2:把resources下的app文件夹拷贝出来到…...

编程日记 2025/8/22 5:21:21

mysql练习

创建数据库db_ck，再创建表t_hero，将四大名著中的主要人物都插入这个表中，将实现过程中sql提交上上来 1、创建数据库db_ck mysql> create database db_ck; 2、创建表t_hero mysql> use db_ck Database changed mysql> create table …...

编程日记 2025/8/23 2:14:23