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

小米笔试题——01背包问题变种

在这里插入图片描述
这段代码的主要思路是使用动态规划来构建一个二维数组 dp,其中 dp[i][j] 表示前 i 个产品是否可以组合出金额 j。通过遍历产品列表和可能的目标金额,不断更新 dp 数组中的值,最终返回 dp[N][M] 来判断是否可以组合出目标金额 M。如果 dp[N][M] 为 true,则表示可以组合出目标金额,否则表示无法组合出目标金额。

#include <iostream>
#include <vector>
#include <limits>using namespace std;bool miHomeGiftBag(vector<int> p, int M) {int N = p.size(); // 获取产品列表中产品的数量vector<vector<bool>> dp(N + 1, vector<bool>(M + 1, false)); // 创建一个二维动态规划数组,dp[i][j] 表示前 i 个产品是否能够组合出金额 jdp[0][0] = true; // 初始化,金额为0时总是可以组合出来for (int i = 1; i <= N; i++) { // 遍历产品列表for (int j = 0; j <= M; j++) { // 遍历可能的目标金额dp[i][j] = dp[i - 1][j]; // 初始情况,不使用当前产品 iif (j - p[i - 1] >= 0) { // 如果当前目标金额 j 大于等于当前产品的价格// 尝试使用当前产品 i,判断前 i-1 个产品是否可以组合出目标金额 j - p[i-1]dp[i][j] = dp[i - 1][j - p[i - 1]] || dp[i][j];}}}return dp[N][M]; // 返回 dp[N][M],表示前 N 个产品是否可以组合出目标金额 M
}int main() {bool res;int _p_size = 0;cin >> _p_size;cout << _p_size << endl;vector<int> _p;int _p_item;for(int _p_i=0; _p_i<_p_size; _p_i++) {cin >> _p_item;cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');_p.push_back(_p_item);}int _M;cin >> _M;cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');res = miHomeGiftBag(_p, _M);cout << res << endl;return 0;}

相关文章:

小米笔试题——01背包问题变种

这段代码的主要思路是使用动态规划来构建一个二维数组 dp&#xff0c;其中 dp[i][j] 表示前 i 个产品是否可以组合出金额 j。通过遍历产品列表和可能的目标金额&#xff0c;不断更新 dp 数组中的值&#xff0c;最终返回 dp[N][M] 来判断是否可以组合出目标金额 M。如果 dp[N][M…...

SkyWalking内置MQE语法

此文档出自SkyWalking官方git https://github.com/apache/skywalking docs/en/api/metrics-query-expression.md Metrics Query Expression(MQE) Syntax MQE is a string that consists of one or more expressions. Each expression could be a combination of one or more …...

Springboot2 Pandas Pyecharts 量子科技专利课程设计大作业

数据集介绍 1.背景 根据《中国科学&#xff1a;信息科学》期刊上的一篇文章&#xff0c;量子通信包括多种协议与应用类型&#xff1a; 基于量子隐形传态与量子存储中继等技术&#xff0c;可实现量子态信息传输&#xff0c;进而构建量子信息网络&#xff0c;已成为当前科研热点&…...

RabbitMQ里的几个重要概念

RabbitMQ中的一些角色&#xff1a; publisher&#xff1a;生产者consumer&#xff1a;消费者exchange个&#xff1a;交换机&#xff0c;负责消息路由&#xff0c;接受生产者发送的消息&#xff0c;把消息发送到一个或多个队列里queue&#xff1a;队列&#xff0c;存储消息virt…...

23. 图论 - 图的由来和构成

文章目录 图的由来图的构成Hi, 你好。我是茶桁。 从第一节课上到现在,我基本上把和人工智能相关的一些数学知识都教给大家了,终于来到我们人工智能数学的最后一个部分了,让我们从今天开始进入「图论」。 图论其实是一个比较有趣的领域,因为微积分其实更多的是对应连续型的…...

拼多多API接口解析,实现根据ID取商品详情

拼多多是一个流行的电商平台&#xff0c;它提供了API接口供开发者使用。要根据ID获取商品详情&#xff0c;您需要使用拼多多API接口并进行相应的请求。 以下是使用拼多多API接口根据ID获取商品详情的示例代码&#xff08;使用Python编写&#xff09;&#xff1a; import requ…...

【JavaScript】解构

解构&#xff08;Destructuring&#xff09;是 JavaScript 中一种强大的语法特性&#xff0c;它允许你从数组或对象中提取值并赋值给变量&#xff0c;使代码更加简洁和易读。JavaScript 中有两种主要的解构语法&#xff1a;数组解构和对象解构。 数组解构 数组解构用于从数组…...

现代卷积网络实战系列2:训练函数、PyTorch构建LeNet网络

4、训练函数 4.1 调用训练函数 train(epochs, net, train_loader, device, optimizer, test_loader, true_value)因为每一个epoch训练结束后&#xff0c;我们需要测试一下这个网络的性能&#xff0c;所有会在训练函数中频繁调用测试函数&#xff0c;所有测试函数中所有需要的…...

rust特性

特性&#xff0c;也叫特质&#xff0c;英文是trait。 trait是一种特殊的类型&#xff0c;用于抽象某些方法。trait类似于其他编程语言中的接口&#xff0c;但又有所不同。 trait定义了一组方法&#xff0c;其他类型可以各自实现这个trait的方法&#xff0c;从而形成多态。 一、…...

TouchGFX之画布控件

TouchGFX的画布控件&#xff0c;在使用相对较小的存储空间的同时保持高性能&#xff0c;可提供平滑、抗锯齿效果良好的几何图形绘制。 TouchGFX 设计器中可用的画布控件&#xff1a; LineCircleShapeLine Progress圆形进度条 存储空间分配和使用​ 为了生成反锯齿效果良好的…...

STM32F103RCT6学习笔记2:串口通信

今日开始快速掌握这款STM32F103RCT6芯片的环境与编程开发&#xff0c;有关基础知识的部分不会多唠&#xff0c;直接实践与运用&#xff01;文章贴出代码测试工程与测试效果图&#xff1a; 目录 串口通信实验计划&#xff1a; 串口通信配置代码&#xff1a; 测试效果图&#…...

Opencv-图像噪声(均值滤波、高斯滤波、中值滤波)

图像的噪声 图像的平滑 均值滤波 均值滤波代码实现 import cv2 as cv import numpy as np import matplotlib.pyplot as plt from pylab import mplmpl.rcParams[font.sans-serif] [SimHei]img cv.imread("dog.png")#均值滤波cv.blur(img, (5, 5))将对图像img进行…...

MasterAlign相机参数设置-增益调节

相机参数设置-曝光时间调节操作说明 相机参数的设置对于获取清晰、准确的图像至关重要。曝光时间是其中一个关键参数&#xff0c;它直接影响图像的亮度和清晰度。以下是关于曝光时间调节的详细操作步骤&#xff0c;以帮助您轻松进行设置。 步骤一&#xff1a;登录系统 首先&…...

9月22日,每日信息差

今天是2023年09月22日&#xff0c;以下是为您准备的14条信息差 第一、亚马逊将于2024年初在Prime Video中加入广告。Prime Video内容中的广告将于2024年初在美国、英国、德国和加拿大推出&#xff0c;随后晚些时候在法国、意大利、西班牙、墨西哥和澳大利亚推出 第二、中国移…...

Java版本企业工程项目管理系统源码+spring cloud 系统管理+java 系统设置+二次开发

工程项目各模块及其功能点清单 一、系统管理 1、数据字典&#xff1a;实现对数据字典标签的增删改查操作 2、编码管理&#xff1a;实现对系统编码的增删改查操作 3、用户管理&#xff1a;管理和查看用户角色 4、菜单管理&#xff1a;实现对系统菜单的增删改查操…...

Android studio中如何下载sdk

打开 file -> settings 这个页面, 在要下载的 SDK 前面勾上, 然后点 apply 在 platforms 中就可以看到下载好的 SDK: Android SDK目录结构详细介绍可以参考这篇文章: 51CTO博客- Android SDK目录结构...

STM32单片机中国象棋TFT触摸屏小游戏

实践制作DIY- GC0167-中国象棋 一、功能说明&#xff1a; 基于STM32单片机设计-中国象棋 二、功能介绍&#xff1a; 硬件组成&#xff1a;STM32F103RCT6最小系统2.8寸TFT电阻触摸屏24C02存储器1个按键&#xff08;悔棋&#xff09; 游戏规则&#xff1a; 1.有悔棋键&…...

【PHP图片托管】CFimagehost搭建私人图床 - 无需数据库支持

文章目录 1.前言2. CFImagehost网站搭建2.1 CFImagehost下载和安装2.2 CFImagehost网页测试2.3 cpolar的安装和注册 3.本地网页发布3.1 Cpolar临时数据隧道3.2 Cpolar稳定隧道&#xff08;云端设置&#xff09;3.3.Cpolar稳定隧道&#xff08;本地设置&#xff09; 4.公网访问测…...

CCITT 标准的CRC-16检验算法

/******该文件使用查表法计算CCITT 标准的CRC-16检验码&#xff0c;并附测试代码********/ #include #define CRC_INIT 0xffff //CCITT初始CRC为全1 #define GOOD_CRC 0xf0b8 //校验时计算出的固定结果值 /****下表是常用ccitt 16,生成式1021反转成8408后的查询表格****/ u…...

docker启动mysql服务

创建基础文件 mkdir mysql mkdir -p mysql/data获取默认的my.cnf docker run -name mysql -d -p 3306:3306 mysql:latest docker cp mysql:/etc/my.cnf ./vim mysql/my.cnf # For advice on how to change settings please see # http://dev.mysql.com/doc/refman/8.1/en/se…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...

高效的后台管理系统——可进行二次开发

随着互联网技术的迅猛发展&#xff0c;企业的数字化管理变得愈加重要。后台管理系统作为数据存储与业务管理的核心&#xff0c;成为了现代企业不可或缺的一部分。今天我们要介绍的是一款名为 若依后台管理框架 的系统&#xff0c;它不仅支持跨平台应用&#xff0c;还能提供丰富…...

HTML中各种标签的作用

一、HTML文件主要标签结构及说明 1. <&#xff01;DOCTYPE html> 作用&#xff1a;声明文档类型&#xff0c;告知浏览器这是 HTML5 文档。 必须&#xff1a;是。 2. <html lang“zh”>. </html> 作用&#xff1a;包裹整个网页内容&#xff0c;lang"z…...