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

[leetcode]01背包问题

news 来源：原创 2025/9/16 7:43:20

一.问题描述

01背包问题是一个经典的组合优化问题，属于动态规划算法的典型应用场景。其问题描述如下： 有一个容量为C的背包，以及 n 个物品，每个物品都有重量w[i] 和价值 v[i]。要求在有限的背包容量下选择一些物品放入背包，使得放入背包的物品总价值最大，且放入物品的总重量不能超过背包的容量。同时，对于每个物品，只能选择放入背包或者不放入背包，即每个物品只有两种状态，这也是“01”背包名称的由来。

例如，有一个容量为5的背包，有3个物品，分别是重量为2、价值为3的物品1，重量为3、价值为4的物品2，以及重量为1、价值为2的物品3。如何选择物品放入背包，才能使背包内物品的总价值最大呢？这就是01背包问题需要解决的。

Coding:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, bagweight;// bagweight代表行李箱空间

    cin >> n >> bagweight;

    vector<int> weight(n, 0); // 存储每件物品所占空间
    vector<int> value(n, 0);  // 存储每件物品价值

    for (int i = 0; i < n; ++i) {
        cin >> weight[i];
    }
    for (int j = 0; j < n; ++j) {
        cin >> value[j];
    }
    // dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

    // 初始化, 因为需要用到dp[i - 1]的值
    // j < weight[0]已在上方被初始化为0
    // j >= weight[0]的值就初始化为value[0]
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    for (int i = 1; i < weight.size(); i++) { // 遍历科研物品
        for (int j = 0; j <= bagweight; j++) { // 遍历行李箱容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 如果装不下这个物品,那么就继承dp[i - 1][j]的值
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
    cout << dp[n - 1][bagweight] << endl;

    return 0;
}

相关文章：

[leetcode]01背包问题

一.问题描述 01背包问题是一个经典的组合优化问题&#xff0c;属于动态规划算法的典型应用场景。其问题描述如下&#xff1a; 有一个容量为C的背包&#xff0c;以及 n 个物品&#xff0c;每个物品都有重量w[i] 和价值 v[i]。要求在有限的背包容量下选择一些物品放入背包&#…...

编程日记 2025/9/16 7:43:20

洛谷刷题Day1——P1706+P1157+P2089+P3654

目录 1. P1706 全排列问题题目描述输入格式输出格式输入输出样例 #1输入 #1输出 #1 说明/提示代码 2. P1157 组合的输出题目描述输入格式输出格式输入输出样例 #1输入 #1输出 #1 代码 3. P2089 烤鸡题目背景题目描述输入格式输出格式输入输出样例 #1输入 #1输出 #1 说明/提示代…...

编程日记 2025/9/11 20:18:05

游戏引擎学习第214天

总结并为当天的任务做好准备 昨天&#xff0c;我们将所有调试控制代码迁移到使用新的调试接口中&#xff0c;但我们没有机会实际启用这些代码。我们做了很多准备工作&#xff0c;比如规划、将其做成宏、并将其放入调试流中&#xff0c;但实际上我们还没有办法进行测试。 今天…...

编程日记 2025/9/15 7:09:32

算法题型讲解

一.双指针 主要分为俩种类型&#xff1a; 1.左右指针&#xff1a;双指针指向开头&#xff0c;以一定标准移动或交换&#xff0c;对区域进行划分&#xff0c;或找到特殊点的位置 &#xff08;如&#xff1a;快慢指针判断有无环&#xff0c;移动零&#xff09; 2.对撞指针&am…...

编程日记 2025/9/11 22:44:56

Qt零散知识点

Qt零散知识点 Qt优点 跨平台接口简单&#xff0c;易上手一定程度上简化了内存的回收 Qt创建新项目 第一个窗口类默认的三个基类 QWidgetQMainWindowQDialog 其中QWidget是QMainWindow和QDialog的基类 一个Qt项目默认创建的文件 main.cpp 入口函数pro文件&#xff1a;工…...

编程日记 2025/9/14 5:58:54

算法导论（递归回溯）——⼆叉树中的深搜

算法思路&#xff08;129&#xff09; 前序遍历遵循“根节点、左子树、右子树”的顺序遍历二叉树的所有节点&#xff0c;常用于解决子节点状态依赖于父节点状态的问题。 算法思路&#xff1a; 在前序遍历的过程中&#xff0c;我们可以将信息从节点向左右子树传递&#xff0c…...

编程日记 2025/8/31 2:33:16

UE像素流发布linux并进行容器化部署

一、宿主机软硬件要求 主要需要关注两部分&#xff1a;对像素流的支持、对linux容器的支持。 1、像素流要求&#xff1a; https://dev.epicgames.com/documentation/zh-cn/unreal-engine/unreal-engine-pixel-streaming-reference?application_version5.3 2、linux容器要求…...

编程日记 2025/9/7 18:32:51

arco-design-vue：给＜a-table＞组件每一行添加data-id属性，并根据id数组是否包含此行id进行样式处理

场景需求&#xff1a; 需要支持框选&#xff0c;框住的行需要更改背景色来标识选中了。如下图所示 【shiftq】表示【加入】&#xff0c;【shiftw】表示【移除】 拆分要实现的功能&#xff1a; 1.框选&#xff0c;选中行数据 2.选中行之后&#xff0c;当前行的样式要有所改变 …...

编程日记 2025/9/10 12:49:13

为什么ChatGPT选择SSE而非WebSocket？

为什么ChatGPT选择SSE而非WebSocket&#xff1f; 一、ChatGPT回答问题的技术逻辑 ChatGPT的响应生成基于Transformer架构和自注意力机制&#xff0c;其核心是通过概率预测逐词生成文本。当用户输入问题后&#xff0c;模型会先解析上下文&#xff0c;再通过预训练的庞大语料库…...

编程日记 2025/9/10 12:18:26

【论文精读与实现】EDC²-RAG:基于动态聚类的文档压缩方法提升检索增强生成RAG性能

🧠 向所有学习者致敬！ “学习不是装满一桶水，而是点燃一把火。” —— 叶芝 我的博客主页： https://lizheng.blog.csdn.net 🌐 欢迎点击加入AI人工智能社区！ 🚀 让我们一起努力，共创AI未来！ 🚀 1. 论文核心思想 这篇由清华大学团队提出的EDC-RAG框架，针对当前…...

编程日记 2025/9/12 6:39:09

SAP S/4HANA Public Cloud的实施特点、项目阶段、资源和工具

1、SAP S/4HANA Public Cloud与OP、PCE部署的区别 近年来，SAP大力推广S/4HANA Public Cloud版本，越来越多的顾问开始接触SAP Public Cloud项目。S/4HANA Public Cloud强调标准化和简化，适合快速实施的企业，在实施方法、技术特点以及项目管理方法上，都与OP版本、PCE版本都…...

编程日记 2025/9/11 0:56:30

Kafka的生产者和消费者的关系

Apache Kafka 是一个分布式流处理平台&#xff0c;生产者和消费者是 Kafka 中两个核心角色&#xff0c;它们之间存在着紧密的关系&#xff0c;以下从多个方面为你详细介绍&#xff1a; 工作模式 生产者&#xff1a;负责将数据发送到 Kafka 的主题&#xff08;Topic&#xff0…...

编程日记 2025/9/8 20:42:33

DAY01：【pytorch】张量

1、张量的简介 1.1 Variable Variable 是 torch.autograd 中的数据类型&#xff0c;主要用于封装 Tensor&#xff0c;进行自动求导 data&#xff1a;被包装的 Tensorgrad&#xff1a;data 的梯度grad_fn&#xff1a;创建 Tensor 的 Function&#xff0c;是自动求导的关键req…...

编程日记 2025/9/8 20:35:59

如何用VBA编辑器合并Word文档：详细教程

在实际办公中&#xff0c;我们经常需要将多个Word文档合并为一个。我将详细讲解如何通过VBA编辑器实现Word文档的自动合并。 前提&#xff1a;先将主文档另存为“docm宏格式”&#xff0c;将要合并的所有文档放在同一个文件夹内。 一、安装VBA编辑器 VBA编辑器是Word自带的工…...

编程日记 2025/9/11 10:42:22

智能体代理模式（Agent Agentic Patterns）深度解析

一、智能体代理模式的理论演进与核心定义 1.1 从自动化工具到认知代理的范式转变 传统AI系统以 规则驱动型工作流 为核心&#xff0c;依赖预设程序执行确定性任务&#xff08;如制造业机器人&#xff09;。而智能体&#xff08;Agent&#xff09;通过 大语言模型&#xff08;…...

编程日记 2025/9/15 4:33:54

若依微服务集成Flowable仿钉钉工作流

项目简介 本项目工作流模块集成在若依项目单独一个模块&#xff0c;可实现单独运行部署&#xff0c; 前端采用微前端&#xff0c;嵌入在若依的前端项目中。因博主是后端开发&#xff0c;对前端不是太属性&#xff0c;没将工作流模块前端代码移到若依前端。下面贴上代码工程结构…...

编程日记 2025/9/14 11:22:05

关于数据结构B树部分的知识点，解题过程以及方法思路

关键点数和节点数的关系...

编程日记 2025/9/8 10:11:21

TOGAF之架构标准规范-技术架构

TOGAF是工业级的企业架构标准规范&#xff0c;本文主要描述技术架构阶段。 如上所示&#xff0c;技术架构&#xff08;Technology Architecture&#xff09;在TOGAF标准规范中处于D阶段 技术架构阶段 技术架构阶段的主要内容包括阶段目标、阶段输入、流程步骤、阶段输出、架构…...

编程日记 2025/9/9 13:52:36

经济金融优化：最优消费与投资分配的MATLAB实战

内容摘要 本文聚焦经济金融领域的优化问题&#xff0c;详细介绍最优消费和最优投资分配的理论与实践。 关键词&#xff1a;最优消费&#xff1b;最优投资分配&#xff1b;效用最大化&#xff1b;投资收益&#xff1b;MATLAB 一、引言 在经济金融领域&#xff0c;个体和企业常…...

编程日记 2025/9/12 18:22:44

【Python语言基础】17、继承

文章目录 1. 继承1.1 为什么要用继承1.2 继承的基本语法1.3 方法重写1.4 多重继承 2. supper()2.1 作用2.2 基本语法2.3 注意事项2.4 super() 在多继承中的特点 1. 继承 在 Python 里&#xff0c;继承是一种强大的编程概念&#xff0c;它允许一个类&#xff08;子类&#xff0…...

编程日记 2025/9/14 23:09:49

基于CNN-GRU的深度Q网络（Deep Q-Network，DQN）求解移动机器人路径规划，MATLAB代码

一、深度Q网络&#xff08;Deep Q-Network&#xff0c;DQN&#xff09;介绍 1、背景与动机 深度Q网络&#xff08;DQN&#xff09;是深度强化学习领域的里程碑算法&#xff0c;由DeepMind于2013年提出。它首次在 Atari 2600 游戏上实现了超越人类的表现&#xff0c;解决了传统…...

编程日记 2025/9/10 17:35:27

DAY06：【pytorch】图像增强

1、基本概念 数据增强&#xff0c;又称数据增广、数据扩增&#xff0c;是对训练集进行变换&#xff0c;使训练集更丰富&#xff0c;从而让模型更具泛化能力 2、裁剪 — — Crop 2.1 transforms.CenterCrop 功能&#xff1a;从图像中心裁剪图片 size&#xff1a;所需裁剪图…...

编程日记 2025/9/12 3:13:35

K_KMS工具（适用windows和office）

目录 前言 一、下载 二、运行 前言 KMS工具&#xff08;适用windows和office&#xff09;。 一、下载 访问下载 &#x1f4be;下载&#x1f449;工具下载地址&#xff1a;https://pan.quark.cn/s/bfdaa27ea823 二、运行 1、在下载目录中找到压缩包&#xff0c;并解压。 …...

编程日记 2025/8/17 19:41:56

Python Cookbook-5.12 检查序列的成员

任务 你需要对一个列表执行很频繁的成员资格检査。而in操作符的 O(n)时间复杂度对性能的影响很大&#xff0c;你也不能将序列转化为一个字典或者集合&#xff0c;因为你还需要保留原序列的元素顺序。 解决方案 假设需要给列表添加一个在该列表中不存在的元素。一个可行的方法…...

编程日记 2025/9/13 18:26:40

移动端六大语言速记：第13部分 - 网络与通信

移动端六大语言速记&#xff1a;第13部分 - 网络与通信 本文将对比Java、Kotlin、Flutter(Dart)、Python、ArkTS和Swift这六种移动端开发语言在网络与通信方面的特性&#xff0c;帮助开发者理解和掌握各语言的网络编程能力。 13. 网络与通信 13.1 HTTP请求 各语言HTTP请求实…...

编程日记 2025/9/12 13:12:01

kafka生产者partition数量和消费者数量的关系

在 Kafka 中&#xff0c;生产者的分区&#xff08;Partition&#xff09;数量和消费者数量之间存在着密切的关系&#xff0c;这种关系对 Kafka 集群的性能、数据处理的并行性以及负载均衡等方面都有着重要影响&#xff0c;以下为你详细介绍&#xff1a; 核心原则 Kafka 中每个…...

编程日记 2025/9/14 17:07:57

数据库主从复制学习笔记

目录 一、Binlog&#xff08;Binary Log&#xff09; 核心特性 核心用途 Binlog 格式&#xff08;3种类型&#xff09; 二、主从复制 核心原理 主库&#xff08;Master&#xff09; 从库&#xff08;Slave&#xff09; 配置步骤&#xff08;以 MySQL 为例&#xff09; …...

编程日记 2025/9/14 21:49:38

使用xml模板导出excel

下面这种表格如何使用xml导出呢&#xff1f; xml代码 <?xml version"1.0" encoding"UTF-8"?> <tables><styles><style id"h1" font.fontheightinpoints"14" font.fontname"黑体" alignment"c…...

编程日记 2025/9/12 6:12:26

深入解析栈式虚拟机与反向波兰表示法

1.1 什么是虚拟机&#xff1f; 虚拟机&#xff08;Virtual Machine, VM&#xff09;是一种软件实现的计算机系统&#xff0c;提供与物理计算机相类似的环境&#xff0c;但在软件层面运行。虚拟机的存在简化了跨平台兼容性、资源管理以及安全隔离等问题。 1.2 栈式虚拟机的架构…...

编程日记 2025/9/13 18:35:14

软件验收测试方法有哪些?验收测试报告如何获取?

大数据互联网时代&#xff0c;各种软件产品为我们的生活和工作带来了极大的便利&#xff0c;企业为了更好的保障软件产品质量&#xff0c;软件测试工作不可或缺。软件验收测试作为软件测试过程中的最后一个测试工作&#xff0c;也被称之为交付测试。验收测试主要是测试软件系统…...

编程日记 2025/9/10 3:09:56

Flexoo 柔性薄膜加热片技术全解析：从原理到应用优势

FLEXOO柔性薄膜加热片通过创新技术实现高效加热。它的柔性设计能够适配不同形状的表面，满足多种设备的需求。PTC加热技术让加热片具备自我调节功能，自动调整热输出以提升安全性与能效。固定功率加热技术则确保热量稳定输出，适合需要持续加热的场景。你可以依赖它的节能环保特…...

编程日记 2025/9/8 10:07:10

DeepSeek与搜索引擎：AI生成内容如何突破“语义天花板”

一、搜索引擎的“内容饥饿症”与AI的“产能悖论” 2024年&#xff0c;全球每天新增470万篇网络文章&#xff0c;但搜索引擎的索引拒绝率高达68%。这一矛盾的根源在于&#xff1a;算法对“高质量原创”的定义已从“形式独特性”转向“认知增值性”。传统AI生成内容&#xff08;…...

编程日记 2025/9/6 17:40:51

【1】k8s集群管理系列--包应用管理器之helm

一、helm概述 Helm核心是模板&#xff0c;即模板化K8s YAML文件。 通过模板实现Chart高效复用&#xff0c;当部署多个应用时&#xff0c;可以将差异化的字段进行模板化&#xff0c;在部署时使用-f或 者–set动态覆盖默认值&#xff0c;从而适配多个应用 helm工作流程&#xf…...

编程日记 2025/9/8 17:53:30

【零基础玩转多模态AI：Gemma3 27B开源视觉模型本地部署与远程访问】

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

编程日记 2025/9/10 22:13:46

安全岗の夺命连环问：（第壹篇）从XSS到0day的灵魂拷问

终极目录 一、面试官の死亡凝视&#xff1a;"给我手撕一个反射型XSS&#xff01;" 1.1 菜鸟の陨落&#xff1a;那些年我们写过的致命代码 1.2 渗透艺术&#xff1a;如何用XSS实现CSRF联动攻击 1.3 防御矩阵&#xff1a;OWASP ESAPI的十八层净化 二、血泪实战&am…...

编程日记 2025/9/16 5:25:59

IAP Firmware Upload Tools.exe IAP 网络固件升级教程

IAP是In Application Programming的简写&#xff0c;IAP升级可以被视为固件升级的一种形式,它是一种在应用程序运行过程中对固件进行更新的技术手段。允许MCU在运行过程中对MCU User Flash的部分区域进行烧写,目的是为了代替编程器对MCU烧录的依赖。 主程序UI 软件按钮说明&a…...

编程日记 2025/9/3 22:26:49

Redis 7高性能缓存与分布式架构实战

大家好&#xff0c;我是袁庭新。很高兴向大家推荐我的新课《Redis 7高性能缓存与分布式架构实战》。这套课程是我与两位一线大厂的高级开发工程师朋友共同研发的&#xff0c;他们分别来自华为和美团&#xff0c;拥有丰富的实战经验。我将担任课程的主讲&#xff0c;为大家带来全…...

编程日记 2025/9/5 10:49:53

自动驾驶时间同步

主要包含两个大的概念&#xff1a;时间系统间的时间同步与传感器数据间的时间同步 1. 时间系统间的时间同步 概念&#xff1a; 自动驾驶域控一般由多个芯片与多种类型的传感器组成&#xff0c;如&#xff1a;MCU SoC Camera Lidar Radar USS GNSS&#xff0c;其中 MCU…...

编程日记 2025/9/9 1:31:57

CISA关键措施要求解析:提升组织网络安全的实用指南

1. 引言 在当今日益复杂的网络安全环境中,组织面临着前所未有的挑战。美国网络安全与基础设施安全局(CISA)提出的关键措施要求,为组织提供了一个全面的框架来加强其网络安全态势。本文将深入探讨这些措施,并提供实际的实施建议。 2. CISA关键措施概述 CISA关键措施包括以下几…...

编程日记 2025/9/15 20:56:03

java笔记03

基本数据类型 数据值是存储在自己的空间中。 特点&#xff1a;赋值给其他变量&#xff0c;也是赋的真实的值。 引用数据类型 数据值是存储在其他空间中&#xff0c;自己空间中存储的是地址值。 特点&#xff1a;赋值给其他变量&#xff0c;赋的地址值。 综合练习 使用 ctrl…...

编程日记 2025/9/12 21:06:25

【HarmonyOS 5】鸿蒙的装饰器原理和自定义装饰器

【HarmonyOS 5】鸿蒙的装饰器原理和自定义装饰器 一、鸿蒙中的装饰器是什么&#xff1f; 在ArkTS中装饰器&#xff08;Decorator&#xff09;是一种特殊的声明&#xff0c;能够对类、方法、属性等进行标注和修改。 因为ArkTS 是TypeScript 扩展而来的编程语言&#xff0c;Ty…...

编程日记 2025/9/6 17:07:43

【Java学习】AI时代下如何学习Java语言开发

学习 Java 语言开发时&#xff0c;合理借助 AI 工具可以提升效率、深化理解&#xff0c;以下是具体的学习策略和方法&#xff1a; 一、利用 AI 辅助基础学习 1. 智能文档解读与语法解析 工具&#xff1a;ChatGPT、Bing Chat、Google Bard用法&#xff1a; 直接提问基础语法问…...

编程日记 2025/9/15 1:37:34

dd命令刻录CENT OS10 (.iso)光盘镜像文件到U盘

操作系统 | “扇区”、“簇”、“块”、“页”等概念_文件系统的簇和扇区-CSDN博客 Windows下面的DD工具_windows dd工具-CSDN博客 如何用 ISO 镜像制作 U 盘安装盘&#xff08;通用方法、无需 WinPE&#xff09;_isou-CSDN博客 1 到CENT OS 网站download iso光盘镜像文件 ht…...

编程日记 2025/9/16 4:53:29

2025年常见渗透测试面试题- Java考察（题目+回答）

网络安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 Java考察 一、Java MVC架构与数据流向 二、Java沙箱安全机制 三、iBATIS参数化查询与注入防御 四、…...

编程日记 2025/9/12 22:37:24

MySQL：事务的理解

一、CURD不加控制&#xff0c;会有什么问题 &#xff08;1&#xff09;因为&#xff0c;MySQL里面存的是数据&#xff0c;所以很有可能会被多个客户访问&#xff0c;所以mysqld可能一次会接受到多个关于CURD的请求。&#xff08;2&#xff09;且mysql内部是采用多线程来完成数…...

编程日记 2025/9/15 1:37:39

开源推荐#5：CloudFlare-ImgBed — 基于 CloudFlare Pages 的开源免费文件托管解决方案

大家好&#xff0c;我是 jonssonyan。 寻找一个稳定、快速、还最好是免费或成本极低的图床服务&#xff0c;一直是许多开发者、博主和内容创作者的痛点。公共图床可能说关就关&#xff0c;付费服务又增加成本。现在&#xff0c;一个名为 CloudFlare-ImgBed 的开源项目&#xf…...

编程日记 2025/9/8 15:50:31

[设计模式]发布订阅者模式解耦业务和UI（以Axios拦截器处理响应状态为例）

当前的代码使用了多个if-else分支来处理不同的状态码，这会导致代码耦合度高，难以维护和扩展。比如，如果未来要新增一个状态码的处理，就需要修改原有的拦截器代码，这违反了开闭原则。发布订阅模式可以将不同状态码的处理逻辑解耦，每个状态码对应一个订阅者，通过中间件来管…...

编程日记 2025/9/7 15:39:45

Redis的过期和内存淘汰策略

文章目录 惰性删除定期删除内存满了&#xff0c;数据淘汰策略 Redis 提供了两种删除策略&#xff1a; 惰性删除 、定期删除 惰性删除 定期删除 两种清除模式: 内存满了&#xff0c;数据淘汰策略 Redis 提供了八种数据淘汰策略&#xff1a; 1. 默认是不淘汰任何的 key&#x…...

编程日记 2025/9/14 15:54:59

每日一题-力扣-2999. 统计强大整数的数目 0410

2999. 统计强大整数的数目 问题分析 题目描述 题目要求统计区间 [start, finish] 内的强大整数数量。强大整数需满足以下条件： 每位数字不超过 limit以字符串 s 作为后缀关键要点理解 强大整数的定义：整数的每一位都不超过 limit，且必须以字符串 s 结尾。区间计数：需要统…...

编程日记 2025/9/11 8:40:01

Flink回撤流详解 代码实例

一、概念介绍 1. 回撤流的定义 在 Flink 中&#xff0c;回撤流主要出现在使用 Table API 或 SQL 进行聚合或更新操作时。对于那些结果并非单纯追加&#xff08;append-only&#xff09;的查询&#xff0c;Flink 会采用“回撤流”模式来表达更新。 回撤流的数据格式&#xff…...

编程日记 2025/9/8 9:59:32