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

C++---背包模型---数字组合(每日一道算法2023.3.14)

注意事项:
本题是"动态规划—01背包"的扩展题,优化思路不多赘述,dp思路会稍有不同,下面详细讲解。

题目:
给定 N个正整数 A1,A2,…,AN,从中选出若干个数,使它们的和为 M,求有多少种选择方案。

输入格式
第一行包含两个整数 N和 M。
第二行包含 N个整数,表示 A1,A2,…,AN。

输出格式
包含一个整数,表示可选方案数。

数据范围
1≤N≤100,
1≤M≤10000,
1≤Ai≤1000,
答案保证在 int 范围内。

输入:
4 4
1 1 2 2
输出:
3
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int N = 10010;
int n, m;
int v[N], f[N], s[N][N];//基础版二维
void base() {s[0][0] = 1;for (int i = 1; i<=n; i++) {for (int j = 0; j<=m; j++) {s[i][j] += s[i-1][j];if (j >= v[i]) s[i][j] += s[i-1][j-v[i]];}}cout << s[n][m];
}//01背包优化,一维滚动数组
void op() {f[0] = 1;for (int i = 1; i<=n; i++) {for (int j = m; j>=0; j--) {f[j] += f[j-v[i]];}}cout << f[m];
}int main() {cin >> n >> m;for (int i = 1; i<=n; i++) cin >> v[i];// base();op();return 0;
}

思路:
经典的y式dp法

1.状态表示
f[i][j]: 表示从前i个数中选,总和刚好为j的方案,属性为Count。

2.状态计算
以 选择/不选择 第i个物品为划分,
1.当不选择第i个物品时:
f[i][j] += f[i-1][j]
2.当选择第二个物品时:
f[i][j] += f[i-1][j-v[i]]

切记我们这里f[i][j]中记录的是前i个数中总和为j的方案总数
是在计算数量,也就是+=。

还有就是初始步骤,f[0][0]为1,
因为从前0个数中选总和为0也是一种方案。

声明:
算法思路来源为y总,详细请见https://www.acwing.com/
本文仅用作学习记录和交流

相关文章:

C++---背包模型---数字组合(每日一道算法2023.3.14)

注意事项&#xff1a; 本题是"动态规划—01背包"的扩展题&#xff0c;优化思路不多赘述&#xff0c;dp思路会稍有不同&#xff0c;下面详细讲解。 题目&#xff1a; 给定 N个正整数 A1,A2,…,AN&#xff0c;从中选出若干个数&#xff0c;使它们的和为 M&#xff0c;…...

并查集(不相交集)详解

目录 一.并查集 1.什么是并查集 2.并查集的基本操作 3.并查集的应用 4.力扣上的题目 二.三大操作 1.初始化 2.查找 3.合并 三.省份数量 1.题目描述 2.问题分析 3.代码实现 四.冗余连接 1.题目描述 2.问题分析 3.代码实现 一.并查集 1.什么是并查集 并查集&…...

10个最频繁用于解释机器学习模型的 Python 库

文章目录什么是XAI&#xff1f;可解释性实践的步骤技术交流1、SHAP2、LIME3、Eli54、Shapash5、Anchors6、BreakDown7、Interpret-Text8、aix360 (AI Explainability 360)9、OmniXAI10、XAI (eXplainable AI)XAI的目标是为模型的行为和决定提供有意义的解释&#xff0c;本文整理…...

final关键字:我偏不让你继承

哈喽&#xff0c;小伙伴们大家好&#xff0c;我是兔哥呀&#xff0c;今天就让我们继续这个JavaSE成神之路&#xff01; 这一节啊&#xff0c;咱们要学习的内容是Java所有final关键字。 之前呢&#xff0c;我们学习了继承&#xff0c;这大大提高了代码的灵活性和复用性。但是总…...

8大主流编程语言的适用领域,你可能选错了语言

很多人学编程经常是脑子一热然后就去网上一搜资源就开始学习了&#xff0c;但学到了后面发现目前所学的东西并不是自己最喜欢的&#xff0c;好像自己更喜欢另一个技术&#xff0c;感觉自己学错了&#xff0c;于是乎又去学习别的东西。 结果竹篮打水一场空&#xff0c;前面所付…...

关于Python库的问题

关于Python库的问题 问题1&#xff1a; ModuleNotFoundError: No module named ‘requests’ Python库 Pycharm使用Requests库时报错&#xff1a; No module named requests’解决方法 未安装requests库&#xff0c;使用"pip install requests"命令安装 依然提示P…...

好记性不如烂笔头(2)

概述&#xff1a;用来记录一些小技巧。 1.查看MyBatis执行的sql 类&#xff1a;org.apache.ibatis.mapping.MappedStatement方法&#xff1a;getBoundSql(Object parameterObject)在IDEA的Evaluate Expression查看sql&#xff1a;boundSql.getSql() 2.maven仓库地址为https&…...

Java for循环嵌套for循环,你需要懂的代码性能优化技巧

前言 本篇分析的技巧点其实是比较常见的&#xff0c;但是最近的几次的代码评审还是发现有不少兄弟没注意到。 所以还是想拿出来说下。 正文 是个什么场景呢&#xff1f; 就是 for循环 里面还有 for循环&#xff0c; 然后做一些数据匹配、处理 这种场景。 我们结合实例代码来…...

关于我拒绝了腾讯测试开发岗offer这件事

2022年刚开始有了向要跳槽的想法&#xff0c;之前的公司不能算大厂但在重庆也算是数一数二。开始跳槽的的时候我其实挺犹豫的 其实说是有跳槽的想法在2022年过年的时候就有了&#xff0c;因为每年公司3月会有涨薪的机会&#xff0c;所以想着看看那能不能涨&#xff08;其实还是…...

从GPT到GPT-3:自然语言处理领域的prompt方法

❤️觉得内容不错的话&#xff0c;欢迎点赞收藏加关注&#x1f60a;&#x1f60a;&#x1f60a;&#xff0c;后续会继续输入更多优质内容❤️&#x1f449;有问题欢迎大家加关注私戳或者评论&#xff08;包括但不限于NLP算法相关&#xff0c;linux学习相关&#xff0c;读研读博…...

Git代码提交规范

Git 代码规范Git 每次提交代码&#xff0c;都是需要写 Commit message&#xff08;提交说明&#xff09;&#xff0c;否则就不允许提交。Commit message 的格式 (三部分)&#xff1a;Heaher ----- 必填type ---必需scope --- 可选subject --- 必需Body ---- 可省略Footer ---- …...

【JavaScript速成之路】JavaScript内置对象--Math和Date对象

&#x1f4c3;个人主页&#xff1a;「小杨」的csdn博客 &#x1f525;系列专栏&#xff1a;【JavaScript速成之路】 &#x1f433;希望大家多多支持&#x1f970;一起进步呀&#xff01; 文章目录前言1&#xff0c;Math对象1.1&#xff0c;常用属性方法1.1.1&#xff0c;获取x的…...

(自用POC)Fortinet-CVE-2022-40684

本文转载于&#xff1a;https://mp.weixin.qq.com/s?__bizMzIzNDU5Mzk2OQ&mid2247485332&idx1&sn85931aa474f1ae2c23a66bf6486eec63&chksme8f54c4adf82c55c44bc7b1ea919d44d377e35a18c74f83a15e6e20ec6c7bc65965dbc70130d&mpshare1&scene23&srcid…...

ConvNeXt V2实战:使用ConvNeXt V2实现图像分类任务(二)

文章目录训练部分导入项目使用的库设置随机因子设置全局参数图像预处理与增强读取数据设置Loss设置模型设置优化器和学习率调整算法设置混合精度&#xff0c;DP多卡&#xff0c;EMA定义训练和验证函数训练函数验证函数调用训练和验证方法运行以及结果查看测试热力图可视化展示完…...

【人工智能与深度学习】基于正则化潜在可变能量的模型

【人工智能与深度学习】基于正则化潜在可变能量的模型 正则化潜变量能量基础模型稀疏编码FISTALISTA稀疏编码示例卷积稀疏编码自然图像上的卷积稀疏编码可变自动编码器正则化潜变量能量基础模型 具有潜在变量的模型能够生成预测分布 y ‾ \overline{y}...

【Leetcode——排序的循环链表】

&#x1f60a;&#x1f60a;&#x1f60a; 文章目录一、力扣题之排序循环链表二、解题思路1. 使用双指针法2、找出最大节点&#xff0c;最大节点的下一个节点是最小节点&#xff0c;由此展开讨论总结一、力扣题之排序循环链表 题目如下&#xff1a;航班直达&#xff01;&#…...

ChatGPT研究分享:机器第一次开始理解人类世界目录

0、为什么会对ChatGPT感兴趣一开始&#xff0c;我对ChatGPT是没什么关注的&#xff0c;无非就是有更大的数据集&#xff0c;完成了更大规模的计算&#xff0c;所以能够回答更多的问题。但后来了解到几个案例&#xff0c;开始觉得这个事情并不简单。我先分别列举出来&#xff0c…...

【linux】Linux基本指令(上)

前言&#xff1a; 在之前我们已经简单了介绍了一下【Linux】&#xff0c;包括它的概念&#xff0c;由来啊等进行了讲解&#xff0c;接下来我们就将正式的踏入对其的学习&#xff01;&#xff01;&#xff01; 本文目录&#x1f449;操作系统的概念1.命令的语法1.1命令介绍1.2选…...

程序员必会技能—— 使用日志

目录 1、为什么要使用日志 2、自定义日志打印 2.1、在程序中得到日志对象 2.2、使用日志对象打印日志 2.3、日志格式 3、日志的级别 3.1、日志级别的分类 3.2、日志级别的设置 4、持久化日志 5、更简单的日志输出——lombok 5.1、如何在已经创建好的SpringBoot项目中添加…...

生成项目的包依赖文件requirements.txt

目录生成项目的包依赖文件requirements.txtrequirements.txt文件怎么来&#xff1f;使用pipreqs第三方库requirements.txt文件使用requirements.txt生成项目的包依赖文件requirements.txt 在安装部署代码时或者使用别人的项目时&#xff0c;会需要安装项目的依赖包&#xff0c…...

sdkman 一键切换 JDK 版本管理工具

&#x1f449; 这是一个或许对你有用的社群&#x1f431; 一对一交流/面试小册/简历优化/求职解惑&#xff0c;欢迎加入「芋道快速开发平台」知识星球。下面是星球提供的部分资料&#xff1a; 《项目实战&#xff08;视频&#xff09;》&#xff1a;从书中学&#xff0c;往事中…...

超好看的Win10音量控制工具Eartrumpet

链接&#xff1a;https://pan.quark.cn/s/48beeba09372Eartrumpe是一款非常好用的系统音量控制工具&#xff0c;可以针对不同的应用进行音量控制&#xff0c;让你同时播放多个音频&#xff0c;在打游戏的时候可以调小游戏声音播放音乐&#xff0c;有需要的朋友欢迎下载使用&…...

60个AI核心概念,不背定义,全落到工作场景!老王手把手教你建知识库、搭Agent,附原型库+PRD模板

&#x1f4a1; Chunking 文档分块 你的 RAG 知识库上线了&#xff0c;用户问一个具体问题&#xff0c;系统返回了一段莫名其妙的内容。一查发现&#xff0c;检索到的文档片段被切在了一个句子中间&#xff0c;上半句话在一个块里&#xff0c;下半句在另一个块里。模型看到半句…...

N_m3u8DL-RE:现代流媒体下载的终极解决方案

N_m3u8DL-RE&#xff1a;现代流媒体下载的终极解决方案 【免费下载链接】N_m3u8DL-RE 跨平台、现代且功能强大的流媒体下载器&#xff0c;支持MPD/M3U8/ISM格式。支持英语、简体中文和繁体中文。 项目地址: https://gitcode.com/GitHub_Trending/nm3/N_m3u8DL-RE 在当今…...

中国 AI 大模型应用市场趋势分析报告

中国 AI 大模型应用市场趋势分析报告 报告类型&#xff1a;新兴趋势识别 蓝海机会评估 覆盖市场&#xff1a;中国大陆 数据时效&#xff1a;截至 2026 年 3 月 研究方法&#xff1a;多源数据交叉验证&#xff08;艾媒咨询、中商情报、36氪研究院、虎嗅、中国工业互联网研究院等…...

零基础玩转OpenClaw:星图GPU百川2-13B量化镜像体验报告

零基础玩转OpenClaw&#xff1a;星图GPU百川2-13B量化镜像体验报告 1. 为什么选择星图平台的OpenClaw镜像 作为一个长期关注AI工具但苦于本地配置复杂度的普通用户&#xff0c;当我发现星图平台提供预装OpenClaw和百川2-13B量化模型的"开箱即用"镜像时&#xff0c;…...

命令行玩转JUnit测试:Linux环境配置+批量执行技巧(JDK8/JUnit4.12)

命令行玩转JUnit测试&#xff1a;Linux环境配置批量执行技巧&#xff08;JDK8/JUnit4.12&#xff09; 在持续集成和DevOps实践中&#xff0c;服务器环境下的自动化测试执行能力直接影响交付效率。本文将深入讲解如何在Linux服务器上搭建无IDE的JUnit测试环境&#xff0c;解决依…...

DeEAR语音情感识别入门必看:为何唤醒度比‘情绪极性’更能反映真实交互状态?

DeEAR语音情感识别入门必看&#xff1a;为何唤醒度比‘情绪极性’更能反映真实交互状态&#xff1f; 如果你用过一些语音助手&#xff0c;或者跟客服机器人打过交道&#xff0c;可能会发现一个有趣的现象&#xff1a;有时候系统能识别出你“生气”了&#xff0c;但它的回应方式…...

3D Face HRN在影视特效中的应用:快速制作数字替身面部模型

3D Face HRN在影视特效中的应用&#xff1a;快速制作数字替身面部模型 1. 引言&#xff1a;数字替身制作的技术革命 在影视特效制作中&#xff0c;数字替身的创建一直是一项耗时且昂贵的工作。传统方法需要演员进行复杂的3D扫描&#xff0c;使用昂贵的设备在专业工作室中完成…...

Optimizing ImageNet Classification with Advanced Deep Convolutional Neural Networks

1. 深度卷积神经网络在ImageNet分类中的核心挑战 ImageNet分类任务一直是计算机视觉领域的标杆性挑战&#xff0c;这个包含1400万张手工标注图像的数据集&#xff0c;要求模型能够准确识别22000个不同类别的物体。当我第一次尝试用传统卷积神经网络处理这个任务时&#xff0c;遇…...