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)
注意事项: 本题是"动态规划—01背包"的扩展题,优化思路不多赘述,dp思路会稍有不同,下面详细讲解。 题目: 给定 N个正整数 A1,A2,…,AN,从中选出若干个数,使它们的和为 M,…...
并查集(不相交集)详解
目录 一.并查集 1.什么是并查集 2.并查集的基本操作 3.并查集的应用 4.力扣上的题目 二.三大操作 1.初始化 2.查找 3.合并 三.省份数量 1.题目描述 2.问题分析 3.代码实现 四.冗余连接 1.题目描述 2.问题分析 3.代码实现 一.并查集 1.什么是并查集 并查集&…...
10个最频繁用于解释机器学习模型的 Python 库
文章目录什么是XAI?可解释性实践的步骤技术交流1、SHAP2、LIME3、Eli54、Shapash5、Anchors6、BreakDown7、Interpret-Text8、aix360 (AI Explainability 360)9、OmniXAI10、XAI (eXplainable AI)XAI的目标是为模型的行为和决定提供有意义的解释,本文整理…...
final关键字:我偏不让你继承
哈喽,小伙伴们大家好,我是兔哥呀,今天就让我们继续这个JavaSE成神之路! 这一节啊,咱们要学习的内容是Java所有final关键字。 之前呢,我们学习了继承,这大大提高了代码的灵活性和复用性。但是总…...
8大主流编程语言的适用领域,你可能选错了语言
很多人学编程经常是脑子一热然后就去网上一搜资源就开始学习了,但学到了后面发现目前所学的东西并不是自己最喜欢的,好像自己更喜欢另一个技术,感觉自己学错了,于是乎又去学习别的东西。 结果竹篮打水一场空,前面所付…...
关于Python库的问题
关于Python库的问题 问题1: ModuleNotFoundError: No module named ‘requests’ Python库 Pycharm使用Requests库时报错: No module named requests’解决方法 未安装requests库,使用"pip install requests"命令安装 依然提示P…...
好记性不如烂笔头(2)
概述:用来记录一些小技巧。 1.查看MyBatis执行的sql 类:org.apache.ibatis.mapping.MappedStatement方法:getBoundSql(Object parameterObject)在IDEA的Evaluate Expression查看sql:boundSql.getSql() 2.maven仓库地址为https&…...
Java for循环嵌套for循环,你需要懂的代码性能优化技巧
前言 本篇分析的技巧点其实是比较常见的,但是最近的几次的代码评审还是发现有不少兄弟没注意到。 所以还是想拿出来说下。 正文 是个什么场景呢? 就是 for循环 里面还有 for循环, 然后做一些数据匹配、处理 这种场景。 我们结合实例代码来…...
关于我拒绝了腾讯测试开发岗offer这件事
2022年刚开始有了向要跳槽的想法,之前的公司不能算大厂但在重庆也算是数一数二。开始跳槽的的时候我其实挺犹豫的 其实说是有跳槽的想法在2022年过年的时候就有了,因为每年公司3月会有涨薪的机会,所以想着看看那能不能涨(其实还是…...
从GPT到GPT-3:自然语言处理领域的prompt方法
❤️觉得内容不错的话,欢迎点赞收藏加关注😊😊😊,后续会继续输入更多优质内容❤️👉有问题欢迎大家加关注私戳或者评论(包括但不限于NLP算法相关,linux学习相关,读研读博…...
Git代码提交规范
Git 代码规范Git 每次提交代码,都是需要写 Commit message(提交说明),否则就不允许提交。Commit message 的格式 (三部分):Heaher ----- 必填type ---必需scope --- 可选subject --- 必需Body ---- 可省略Footer ---- …...
【JavaScript速成之路】JavaScript内置对象--Math和Date对象
📃个人主页:「小杨」的csdn博客 🔥系列专栏:【JavaScript速成之路】 🐳希望大家多多支持🥰一起进步呀! 文章目录前言1,Math对象1.1,常用属性方法1.1.1,获取x的…...
(自用POC)Fortinet-CVE-2022-40684
本文转载于:https://mp.weixin.qq.com/s?__bizMzIzNDU5Mzk2OQ&mid2247485332&idx1&sn85931aa474f1ae2c23a66bf6486eec63&chksme8f54c4adf82c55c44bc7b1ea919d44d377e35a18c74f83a15e6e20ec6c7bc65965dbc70130d&mpshare1&scene23&srcid…...
ConvNeXt V2实战:使用ConvNeXt V2实现图像分类任务(二)
文章目录训练部分导入项目使用的库设置随机因子设置全局参数图像预处理与增强读取数据设置Loss设置模型设置优化器和学习率调整算法设置混合精度,DP多卡,EMA定义训练和验证函数训练函数验证函数调用训练和验证方法运行以及结果查看测试热力图可视化展示完…...
【人工智能与深度学习】基于正则化潜在可变能量的模型
【人工智能与深度学习】基于正则化潜在可变能量的模型 正则化潜变量能量基础模型稀疏编码FISTALISTA稀疏编码示例卷积稀疏编码自然图像上的卷积稀疏编码可变自动编码器正则化潜变量能量基础模型 具有潜在变量的模型能够生成预测分布 y ‾ \overline{y}...
【Leetcode——排序的循环链表】
😊😊😊 文章目录一、力扣题之排序循环链表二、解题思路1. 使用双指针法2、找出最大节点,最大节点的下一个节点是最小节点,由此展开讨论总结一、力扣题之排序循环链表 题目如下:航班直达!&#…...
ChatGPT研究分享:机器第一次开始理解人类世界目录
0、为什么会对ChatGPT感兴趣一开始,我对ChatGPT是没什么关注的,无非就是有更大的数据集,完成了更大规模的计算,所以能够回答更多的问题。但后来了解到几个案例,开始觉得这个事情并不简单。我先分别列举出来,…...
【linux】Linux基本指令(上)
前言: 在之前我们已经简单了介绍了一下【Linux】,包括它的概念,由来啊等进行了讲解,接下来我们就将正式的踏入对其的学习!!! 本文目录👉操作系统的概念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文件怎么来?使用pipreqs第三方库requirements.txt文件使用requirements.txt生成项目的包依赖文件requirements.txt 在安装部署代码时或者使用别人的项目时,会需要安装项目的依赖包,…...
OpenClaw调试技巧:GLM-4.7-Flash任务执行日志分析与问题定位
OpenClaw调试技巧:GLM-4.7-Flash任务执行日志分析与问题定位 1. 为什么需要关注OpenClaw的调试日志 上周我在尝试用OpenClaw自动整理项目文档时,遇到了一个奇怪的现象:任务明明显示执行成功,但最终生成的Markdown文件却缺失了关…...
如何快速实现本地离线语音识别:面向Windows用户的完整解决方案
如何快速实现本地离线语音识别:面向Windows用户的完整解决方案 【免费下载链接】TMSpeech 腾讯会议摸鱼工具 项目地址: https://gitcode.com/gh_mirrors/tm/TMSpeech 还在为会议记录、视频字幕、语音笔记而烦恼吗?传统的语音识别工具要么需要网络…...
ncmdumpGUI:实现NCM格式自由转换的音频解决方案
ncmdumpGUI:实现NCM格式自由转换的音频解决方案 【免费下载链接】ncmdumpGUI C#版本网易云音乐ncm文件格式转换,Windows图形界面版本 项目地址: https://gitcode.com/gh_mirrors/nc/ncmdumpGUI 痛点剖析:NCM格式的技术民主化阻碍 格…...
Python 服务优雅停机实战:信号处理、资源收尾与 Kubernetes 滚动发布避坑指南
Python 服务优雅停机实战:信号处理、资源收尾与 Kubernetes 滚动发布避坑指南 客观来看,Python 作为“胶水语言”,以其简洁优雅的语法从 1991 年诞生至今,已深度渗透 Web 开发、数据科学、人工智能和自动化运维等领域。它改变了编…...
Wemod-Patcher:开源工具实现WeMod功能增强的完整方案
Wemod-Patcher:开源工具实现WeMod功能增强的完整方案 【免费下载链接】Wemod-Patcher WeMod patcher allows you to get some WeMod Pro features absolutely free 项目地址: https://gitcode.com/gh_mirrors/we/Wemod-Patcher 在游戏体验优化领域࿰…...
Phi-4-Reasoning-Vision代码实例:TextIteratorStreamer实现思考过程智能分隔
Phi-4-Reasoning-Vision代码实例:TextIteratorStreamer实现思考过程智能分隔 1. 项目概述 Phi-4-Reasoning-Vision是基于微软Phi-4-reasoning-vision-15B多模态大模型开发的高性能推理工具,专为双卡RTX 4090环境优化。该工具严格遵循官方SYSTEM PROMPT…...
Stable Diffusion XL 1.0艺术表现力:灵感画廊1024x1024超清水墨质感实测
Stable Diffusion XL 1.0艺术表现力:灵感画廊1024x1024超清水墨质感实测 1. 开篇:当AI遇见东方美学 想象一下,你坐在一间安静的书房里,窗外是细雨绵绵,桌面上铺着宣纸,手边是笔墨砚台。你想画一幅水墨山水…...
IEEE论文LaTeX排版技巧(十一)| 尾页双栏平衡优化实战指南
1. 为什么尾页双栏平衡如此重要? 当你熬夜改完论文准备提交时,有没有发现最后一页的两栏长度总是不对称?左边栏挤得满满当当,右边栏却空出一大截,这种视觉上的不平衡会直接影响评审专家对你论文的第一印象。我在审阅学…...
Qwen3-0.6B-FP8效果展示:用‘把这篇技术博客改写成适合小学生理解的版本’实测简化能力
Qwen3-0.6B-FP8效果展示:用‘把这篇技术博客改写成适合小学生理解的版本’实测简化能力 1. 引言:当大模型遇上“小学生”挑战 想象一下,你面前有一篇满是专业术语、复杂逻辑的技术文章,现在需要把它讲给一个小学三年级的孩子听&…...
SDMatte辅助软件测试:自动化验证图形界面元素的渲染效果
SDMatte辅助软件测试:自动化验证图形界面元素的渲染效果 1. 引言 在软件测试领域,图形用户界面(GUI)的验证一直是个耗时且容易出错的过程。传统的人工检查方式不仅效率低下,还难以保证测试覆盖率。想象一下,测试工程师需要手动检…...
