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

AcWing 11：背包问题求方案数 ← 0-1背包

news 来源：原创 2025/8/9 9:08:38

【题目来源】
https://www.acwing.com/problem/content/11/

【题目描述】
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最优选法的方案数。注意答案可能很大，请输出答案模 10^9+7 的结果。

【输入格式】
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi，wi，用空格隔开，分别表示第 i 件物品的体积和价值。

【输出格式】
输出一个整数，表示方案数模 10^9+7 的结果。

【数据范围】
0<N,V≤1000 
0<vi,wi≤1000

【输入样例】
4 5
1 2
2 4
3 4
4 6

【输出样例】
2

【算法分析】
设 f[i] 为背包容积为 i 时的最佳方案的总价值，cnt[i] 为背包容积为 i 时总价值为最佳的方案数。
由于背包里什么也不装也是一种方案，故初始化所有的 cnt{i] 为 1。
如果装新物品的方案总价值更大，那么用 f[j-vol]+val 来更新 f[j]，用 cnt[j-vol] 更新 cnt[j]。
如果总价值相等，那么最大价值的方案数就多了 cnt[j-vol] 种。

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int MOD=1e9+7;
const int N=1e3+5;
int f[N],cnt[N];int main() {int n,v;cin>>n>>v;for(int i=0; i<=v; i++) cnt[i]=1;for(int i=1; i<=n; i++) {int vol,val;cin>>vol>>val;for(int j=v; j>=vol; j--) {int t=f[j-vol]+val;if(t>f[j]) {f[j]=t;cnt[j]=cnt[j-vol];} else if(t==f[j]) {cnt[j]=(cnt[j]+cnt[j-vol])%MOD;}}}cout<<cnt[v]<<endl;return 0;
}/*
in:
4 5
1 2
2 4
3 4
4 6out:
2
*/




【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/147326357
https://blog.csdn.net/hnjzsyjyj/article/details/147333181
https://www.acwing.com/solution/content/3999/


 

相关文章：

AcWing 11：背包问题求方案数 ← 0-1背包

【题目来源】 https://www.acwing.com/problem/content/11/ 【题目描述】 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi&#xff0c;价值是 wi。 求解将哪些物品装入背包&#xff0c;可使这些物品的总体积不超过背包容量&#xff0c;且总…...

编程日记 2025/8/9 9:08:38

Redis增删改查

### 进入redis控制台 redis-cli --raw #加上raw,防止中文乱码### 增 127.0.0.1:6379> LPUSH list0 "hello" #增加一个list 1 127.0.0.1:6379> LRANGE list0 0 -1 #查看list hello### 删 127.0.0.1:6379> DEL list0 #删除list 1 127.0.0.1:6379> LRANG…...

编程日记 2025/8/10 8:17:01

多道程序和多任务操作系统区别

多道程序 vs. 多道任务&#xff1a;对比分析 ✅ 共同点 方面共同特征核心机制都依赖于进程/任务切换执行需求实现多个程序或任务"并发"执行系统支持都需要操作系统的支持&#xff08;如调度算法、内存管理&#xff09;本质目标提高资源利用率&#xff08;CPU不空转…...

编程日记 2025/8/10 8:10:09

【MySQL】MySQL建立索引不知道注意什么？

基本原则&#xff1a; 1.选择性原则&#xff1a; 选择高选择性的列建立索引(该列有大量不同的值) 2.适度原则&#xff1a;不是越多越好&#xff0c;每个索引都会增加写入开销 列选择注意事项&#xff1a; 1.常用查询条件列&#xff1a;WHERE字句中频繁使用的列 2.连接操作列…...

编程日记 2025/8/10 8:15:27

区块链木材业务服务平台：商贸物流新变革

区块链木材业务服务平台&#xff1a;商贸物流新变革 在全球商贸物流行业不断发展的当下&#xff0c;木材贸易作为其中重要的一环&#xff0c;面临着诸多挑战。区块链木材业务服务平台的出现&#xff0c;为木材商贸物流领域带来了全新的解决方案&#xff0c;正逐步引领行业走向…...

编程日记 2025/8/10 8:15:01

【AI提示词】经济学家

提示说明 经济学家致力于提供深入的经济分析和预测&#xff0c;帮助用户理解经济趋势、政策影响以及市场动态。他们通过专业的经济模型和数据分析&#xff0c;为用户在投资、决策等方面提供指导。 提示词 # 角色 经济学家## 注意 1. 经济学家专家需要具备深入分析经济现象的…...

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

C++用于保留浮点数的两位小数，使用宏定义方法（可兼容低版本Visual Studio）

文章目录 一、 描述二、 样例二、 结果输出 一、 描述 这个宏定义&#xff08;可放入.h头文件里&#xff09;使用基本的数学运算&#xff0c;几乎兼容所有版本的VS&#xff0c;以下可对正数做四舍五入&#xff1a; #define ROUND_TO_TWO(x) ( (floor((x) * 100 0.5) / 100) …...

编程日记 2025/8/10 8:15:01

kimi+deepseek制作PPT

文章目录 KIMI简介一、基本信息二、核心特点三、服务理念 Deepseek简介PPT关键词提示 KIMI简介 KIMI官网&#xff1a;Kimi - 会推理解析&#xff0c;能深度思考的AI助手 一、基本信息 名称 &#xff1a;KIMI开发团队 &#xff1a;月之暗面科技有限公司上线时间 &#xff1a;…...

编程日记 2025/8/10 8:15:27

Linux-进度条小程序

1. 回车和换行的差异 在输出文本时&#xff0c;回车和换行符的作用是非常不同的。了解它们的行为有助于我们控制输出的方式。 回车&#xff08;\r&#xff09;&#xff1a;回车符将光标移到当前行的开头&#xff0c;但并不会自动换行。它的作用是覆盖当前行的内容。 换行&…...

编程日记 2025/8/4 14:51:00

Day2—3：前端项目uniapp壁纸实战

接下来我们做一个专题精选 <view class"theme"><common-title><template #name>专题精选</template><template #custom><navigator url"" class"more">More</navigator></template></common…...

编程日记 2025/7/30 17:31:07

什么是超类实体和派生属性

在数据库设计&#xff08;尤其是实体-关系模型&#xff08;ER模型&#xff09;&#xff09;和面向对象建模中&#xff0c;超类实体和派生属性是两个重要的概念&#xff0c;分别用于描述实体间的继承关系和属性的动态计算特性。以下是它们的详细解释和对比&#xff1a; 一、超类…...

编程日记 2025/8/9 5:24:22

性能比拼: Elixir vs Go(第二轮)

本内容是对知名性能评测博主 Anton Putra Elixir vs Go (Golang) Performance Benchmark (Round 2) 内容的翻译与整理, 有适当删减, 相关指标和结论以原作为准 这是第二轮关于 Elixir 和 Go 的对比测试。我收到了一份来自 Elixir 创作者的 Pull Request &#xff0c;并且我认为…...

编程日记 2025/8/10 8:15:28

微信、抖音、小红书emoji符号大全

1、Emoji 日常符号 &#x1f463;&#x1f440;&#x1f441;️&#x1f444;&#x1f48b;&#x1f442;&#x1f9bb;&#x1f443;&#x1f445;&#x1f9e0;&#x1fac0;&#x1fac1;&#x1f9b7;&#x1f9b4;&#x1f4aa;&#x1f9be;&#x1f9bf;&#x1f9b5;&a…...

编程日记 2025/8/10 8:15:28

【大模型】 LangChain框架 -LangChain实现问答系统

LangChain 介绍与使用方法 1. 什么是 LangChain&#xff1f;2. LangChain 的主要功能3. 如何使用 LangChain&#xff1f;3.1 环境准备3.2 基本使用示例3.2.1 简单的问答系统3.2.2 结合外部工具 3.3 高级用法 4. 常见问题及解决方法4.1 安装问题4.2 运行问题4.3 性能问题 5. 实战…...

编程日记 2025/8/6 12:42:16

k8s安装kubeadm

使用kubeadm安装部署k8s集群 目前生产部署Kubernetes 集群主要有两种方式&#xff1a; kubeadm Kubeadm 是一个K8s 部署工具&#xff0c;提供kubeadm init 和kubeadm join&#xff0c;用于快速部署Kubernetes 集群。 官方地址&#xff1a;https://kubernetes.io/docs/refer…...

编程日记 2025/8/10 2:20:13

五、小白如何用Pygame制作一款跑酷类游戏（主角跳跃和滑行动作的实现）

五、小白如何用Pygame制作一款跑酷类游戏&#xff08;主角跳跃和滑行动作的实现&#xff09; 文章目录 五、小白如何用Pygame制作一款跑酷类游戏&#xff08;主角跳跃和滑行动作的实现&#xff09;前言一、添加主角的跳跃和滑行图片素材二、代码部分1.在走路状态时按下按键发生…...

编程日记 2025/8/10 8:12:38

LLM MCP模型上下文协议快速入门（for Java）

什么是MCP Model Control Protocol&#xff08;MCP&#xff09;是由AI研究机构Anthropic在2023年第二季度首次提出的新型协议规范&#xff0c;旨在解决大语言模型LLM应用中的上下文管理难题。作为LLM交互领域的创新标准&#xff0c;MCP协议在发布后短短一年内已进行了多次更新…...

编程日记 2025/8/10 8:13:04

CTF--秋名山车神

一、原网页&#xff1a; 二、步骤&#xff1a; 1.尝试用计算器计算&#xff1a; 计算器溢出&#xff0c;无法正常计算 2.使用python计算&#xff1a; 得出计算结果为&#xff1a;1864710043732437134701060769 3.多次刷新页面&#xff1a; 发现变量为value&#xff0c;要用pos…...

编程日记 2025/8/9 20:20:02

Windows桌面图标变白的解决方案

一、问题原因 桌面图标变白通常是由于系统图标缓存文件&#xff08;IconCache.db&#xff09;损坏或系统图表示现异常导致。图标缓存是Windows用于存储应用程序和文件夹图标图像的临时文件&#xff0c;当该文件损坏或系统未正确更新缓存时&#xff0c;图标会因无法加载原始图像…...

编程日记 2025/8/10 8:11:36

Linux学习——信号量

1.头文件-semaphore.h 2.信号量类型 sem_t sem; 加强版的互斥锁&#xff0c;是并行的 3.主要函数 初始化信号量 sem_init(sem_t *sem,int pshared,unsigned int value); 第一个参数 信号量类型 第二个参数 0-线程同步 1-进程同步 …...

编程日记 2025/8/10 8:06:31

蓝桥杯 蜗牛 动态规划

16.蜗牛 - 蓝桥云课https://www.lanqiao.cn/problems/4985/learning/?page1&first_category_id1&second_category_id3&sortdifficulty&asc1&tags%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92,%E9%80%92%E6%8E%A8,01%E8%83%8C%E5%8C%85,%E5%8C%BA%E9%97%B4DP,%E6…...

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

FiftyOne 管理数据

FiftyOne 管理数据 下载安装FiftyOne https://docs.voxel51.com/ 下载 coco-2017 使用 FiftyOne 查看 import fiftyone as fo import fiftyone.zoo as foz# 自定义路径 - 修改这些变量以匹配你的环境 image_path /media/wmx/ws3/AI/data/coco2017/train2017 annotations_…...

编程日记 2025/8/10 8:12:37

解决echarts饼图label显示不全的问题

解决办法 添加如下配置&#xff1a; labelLayout: {hideOverlap: false},...

编程日记 2025/8/10 2:41:11

2000-2017年各省城市天然气供气总量数据

2000-2017年各省城市天然气供气总量数据 1、时间&#xff1a;2000-2017年 2、来源&#xff1a;国家统计局、能源年鉴 3、指标&#xff1a;行政区划代码、城市、年份、城市天然气供气总量 4、范围&#xff1a;31省 5、指标说明&#xff1a;城市天然气供气总量是指在一定时间…...

编程日记 2025/7/30 16:31:25

Linux教程-常用命令系列二

文章目录 1. 系统管理常用命令1. useradd - 创建用户账户功能基本用法常用选项示例 2. passwd - 管理用户密码功能基本用法常用选项示例 3. kill - 终止进程功能基本用法常用信号示例 4. date - 显示和设置系统时间功能基本用法常用选项时间格式示例 5. bc - 高精度计算器功能基…...

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

苍穹外卖（菜品管理）

菜品管理 公共字段自动填充 实现思路 代码开发 自定义注解 AutoFill 自定义切面 AutoFillAspect 完善自定义切面 AutoFillAspect 的 autoFill 方法 在Mapper接口的方法上加入 AutoFill 注解 将业务层为公共字段赋值的代码注释掉 功能测试 新增菜品 需求分析和…...

编程日记 2025/8/8 14:00:29

Cril 截取字段-生成hostname

有些event 是不规则，需要用regular express 来加工一下, 下面说一下sample 数据: 2021-10-26 17:00:12 PDT sample log data from host eagle1 2021-10-26 17:00:12 PDT sample log data from host eagle2 2021-10-26 17:00:12 PDT sample log data from host eagle3 2021…...

编程日记 2025/7/30 17:30:41

免费将AI生成图像放大4倍的方法

有些人不需要任何高级工具和花哨的技巧；他们只需要一种简单的方法来提升图像分辨率而不损失任何质量 — 今天，我们将学习如何做到这一点。 生成AI图像最大的问题之一是什么？最终结果通常分辨率非常低。 这会导致很多不同的问题，特别是对于那些想要在内容或项目中使用这些…...

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

Map和Set相关练习

目录 1、只出现一次的数字 2、宝石与石头 3、坏键盘打字 4、复制带随机指针的链表 5、大量数据去重 6、大量数据重复次数 7、前K个高频单词 1、只出现一次的数字 oj&#xff1a;136. 只出现一次的数字 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 1. 使用…...

编程日记 2025/8/3 7:26:59

移动自动化测试-appium

app自动化介绍 工具说明 主流工具 app自动化执行原理 app类型&#xff08;技术&#xff09; 环境搭建 所需环境 JDKandroid-sdkappium模拟器 1、JDK安装 说明&#xff1a;为什么要安装JDK&#xff1f; 安卓应用或开发工具是使用JAVA语言开发&#xff0c;必须使用jdk。…...

编程日记 2025/8/6 19:20:12

一个项目中多个Composer的使用方法

composer是依赖管理工具。 有时我们会在一个项目中使用到多个composer&#xff0c;且每个版本不同。 前提&#xff1a;例如项目xyz根目录vendor中存在阿里云的对应代码。我现在需要再composer腾讯云短信发送的SDK。 1、随便找个位置新建文件夹&#xff0c;存储腾讯云短信发送…...

编程日记 2025/8/6 4:32:11

Qt项目实现对西门子PLC的读写操作（snap7）——C++

实际项目中需要用到对西门子PLC进行通讯&#xff0c;故进行记录&#xff0c;方便后续回顾复习 实现功能&#xff1a; ①PLC连接与断开 ②往PLC指定位置读写操作&#xff08;bit、real、string&#xff09; PLC中的real相当于C中的float&#xff0c;4字节&#xff0c;32bit 1&…...

编程日记 2025/8/4 10:44:59

Python字典深度解析：高效键值对数据管理指南

一、字典核心概念解析 1. 字典定义与特征 字典&#xff08;Dictionary&#xff09;是Python中​​基于哈希表实现​​的无序可变容器&#xff0c;通过键值对存储数据&#xff0c;具有以下核心特性&#xff1a; ​​键值对结构​​&#xff1a;{key: value}形式存储数据​​快…...

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

Java虚拟机面试题：垃圾收集（下）

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;精通Java编…...

编程日记 2025/8/8 14:25:10

9 C 语言变量详解：声明与定于、初始化与赋值、printf 输出与 scanf 输入、关键字、标识符命名规范

1 初识变量 1.1 变量的意义 在程序设计中&#xff0c;变量是程序中不可或缺的组成单位&#xff0c;最基本的存储单元。它如同现实生活中的容器&#xff0c;用于临时或长期保存各种类型的数据&#xff0c;为程序提供灵活的数据操作能力。 以选购手机为例&#xff0c;手机的各项…...

编程日记 2025/8/4 11:38:36

释放 Mac 存储空间：Ollama 模型迁移到外接 NVMe 磁盘

目录 背景一、准备工作1. 确认外接 NVMe 已挂载2. 创建模型目录 二、迁移已有模型数据&#xff08;可选&#xff09;三、配置模型目录1. 设置环境变量2. 使用软链接&#xff08;强烈推荐&#xff09; 四、测试是否成功 背景 在本地运行 Ollama 时&#xff0c;模型数据默认保存…...

编程日记 2025/7/30 17:30:27

spring-batch批处理框架(1)

学习链接 SpringBatch高效批处理框架详解及实战演练 spring-batch批处理框架(1) spring-batch批处理框架(2) spring batch官方文档 spring batch官方示例代码 - github 文章目录 学习链接一、课程目标课程目标课程内容前置知识适合人群 二、Spring Batch简介2.1 何为批处理…...

编程日记 2025/8/3 13:43:13

MCP系列：权限管理与隐私保护

前言 随着模型上下文协议（MCP）的广泛应用，安全性问题也逐步突显。在前几篇文章中，我们已经探讨了MCP的基本概念、技术架构、实践应用以及工具调用机制。本篇文章将聚焦于MCP的安全性考量，包括权限管理、隐私保护以及风险缓解策略。 对于企业和开发者而言，了解如何保障M…...

编程日记 2025/8/7 12:10:18

【25软考网工笔记】第二章（7）多路复用技术

目录 一、多路复用技术 1. 频分复用FDM 1&#xff09;频分复用的基本概念 2&#xff09;频分复用与相关技术 3&#xff09;注意事项与扩展 2. 时分复用 1&#xff09;同步时分复用 2&#xff09;统计时分复用 3&#xff09;同步时分复用与统计时分复用的对比 4&#…...

编程日记 2025/8/7 1:51:22

任意文字+即梦3.0的海报设计Prompt

即梦3.0版本发布后&#xff0c;对文字的呈现能力得到了极大的提升&#xff0c;网上也出现了各种文章教大家怎么写提示词。 但是你有没有发现一个问题&#xff0c;好的提示词是需要艺术细胞的&#xff0c;只有那些浸淫设计领域的专家总结的提示词才算上乘。 就像是给你一个主题…...

编程日记 2025/8/8 14:00:29

自动化测试相关协议深度剖析及A2A、MCP协议自动化测试应用展望

一、不同协议底层逻辑关联分析 1. OPENAPI协议 OPENAPI 协议核心在于定义 API 的规范结构&#xff0c;它使用 YAML 或 JSON 格式来描述 API 的端点、请求参数、响应格式等信息。其底层逻辑是构建一个清晰、标准化的 API 描述文档&#xff0c;方便不同的客户端和服务端进行对接…...

编程日记 2025/8/6 8:42:46

零基础上手Python数据分析 (18)：Matplotlib 基础绘图 - 让数据“开口说话”

写在前面 —— 告别枯燥数字，拥抱可视化力量，掌握 Matplotlib 绘图基础 欢迎来到 “高效数据分析实战指南：Python零基础入门” 专栏！ 经过前面 Pandas 模块的学习和实战演练，我们已经掌握了使用 Python 和 Pandas 进行数据处理、清洗、整合、分析的核心技能。 我们能够从…...

编程日记 2025/8/6 17:44:52

[特殊字符] AI 大模型的 Prompt Engineering 原理：从基础到源码实践

&#x1f31f; 引言&#xff1a;Prompt Engineering - AI 大模型的"魔法咒语" 在 AI 大模型蓬勃发展的当下&#xff0c;它们展现出令人惊叹的语言处理能力&#xff0c;从文本生成到智能问答&#xff0c;从机器翻译到代码编写&#xff0c;几乎涵盖了自然语言处理的各…...

编程日记 2025/8/6 1:33:14

C++ 基于多设计模式下的同步异步⽇志系统-1准备工作

一.项目介绍 项⽬介绍 本项⽬主要实现⼀个⽇志系统&#xff0c; 其主要⽀持以下功能: • ⽀持多级别⽇志消息 • ⽀持同步⽇志和异步⽇志 • ⽀持可靠写⼊⽇志到控制台、⽂件以及滚动⽂件中 • ⽀持多线程程序并发写⽇志 • ⽀持扩展不同的⽇志落地⽬标地 二.日志系统的三种实现…...

编程日记 2025/8/4 9:30:46

c# MES生产进度看板，报警看板 热流道行业可用实时看生产进度

MES生产进度看板&#xff0c;报警看板 热流道行业可用实时看生产进度 背景 本软件是给宁波热流道行业客户开发的生产电子看板软件系统 功能 1.录入工艺流程图&#xff08;途程图&#xff09;由多个站别组成。可以手动设置每个工艺站点完成百分比。 2.可以看生成到哪个工…...

编程日记 2025/8/4 6:27:32

C语言学习之预处理指令

目录 预定义符号 #define的应用 #define定义常量 #define定义宏 带有副作用的宏参数 宏替换的规则 函数和宏定义的区别 #和## #运算符 ##运算符 命名约定 #undef ​编辑 命令行定义 条件编译 头文件包含 头文件被包含的方式 1.本地头文件包含 2.库文件包含 …...

编程日记 2025/7/30 19:41:00

腾讯wxg企业微信 后端开发一面

UDP安全吗&#xff0c;怎么修改让其安全&#xff1f; packet header QUIC FrameHeader TCP的三个窗口 滑动 发送 拥塞&#xff0c; 怎么用UDP使用类似的功能 怎么确认消息是否收到? TCP的拥塞控制是怎么样的 HTTPS的握手流程 MySQL为什么用B树 红黑树等结构也能在叶子节点实现…...

编程日记 2025/8/9 22:26:16

【Hot100】 73. 矩阵置零

目录 引言矩阵置零我的解题优化优化思路分步解决思路为什么必须按照这个顺序处理&#xff1f;完整示例演示总结 &#x1f64b;‍♂️ 作者&#xff1a;海码007&#x1f4dc; 专栏&#xff1a;算法专栏&#x1f4a5; 标题&#xff1a;【Hot100】 73. 矩阵置零❣️ 寄语&#xff…...

编程日记 2025/7/30 19:40:56

c++_csp-j算法 (2)

目录 BFS搜索(广度优先搜索) 讲解 BFS搜索算法原理 BFS搜索算法实现 BFS搜索算法的应用 例题（1） P1032 [NOIP 2002 提高组] 字串变换 例题（2） P1443 马的遍历 BFS搜索(广度优先搜索) 讲解 BFS搜索算法原理 广度优先搜索（BFS）算法是一种图的搜索算法，用于遍历…...

编程日记 2025/8/4 11:51:21

学习笔记: Mach-O 文件

“结构决定性质,性质决定用途”。如果不了解结构,是很难真正理解的。 通过一个示例的可执行文件了解Mach-O文件的结构 Mach-O基本结构 Header: &#xff1a;文件类型、目标架构类型等Load Commands&#xff1a;描述文件在虚拟内存中的逻辑结构、布局Data: 在Load commands中…...

编程日记 2025/8/5 20:40:14