完全背包问题(c++)
完全背包问题
当前有 N 种物品,第 i 种物品的体积是 ci,价值是 wi。
每种物品的数量都是无限的,可以选择任意数量放入背包。
现有容量为 V 的背包,请你放入若干物品,使总体积不超过 V,并且总价值尽可能大。

解析
虽然物品个数是无限的,但是实际上,由于背包容量有上限,每个物品最多选取的个数也是有限制的,这样可以转换成多重背包问题,进而可以转换成 01 背包问题。
可以用多重背包的思想来解决完全背包。
for (int i = 1; i <= N; i++) {for (int j = 0; j <= V; j++) {for (int k = 0; k * c[i] <= j; k++) {dp[i][j] = max(dp[i - 1][j - c[i] * k] + w[i] * k, dp[i][j]);}}
}
时间效率优化
我们可以注意到
dp[i][v]=max(dp[i−1][v],dp[i−1][v−ci]+wi,dp[i−1][v−ci×2]+wi×2…)
而
dp[i][v−ci]=max(dp[i−1][v−ci],dp[i−1][v−ci×2]+wi,dp[i−1][v−ci×3]+wi×2…)
也就是说,我们完全可以用 dp[i][v−ci] 的信息去更新 dp[i][v],而不用去多此一举去枚举 k 了,转移可以直接变成如下:
dp[i][v]=max(dp[i−1][v],dp[i][v−ci]+w[i])
for (int i = 1; i <= n; i++) {for (int j = 0; j <= v; j++) {if (j >= c[i]) {dp[i][j] = max(dp[i][j - c[i]] + w[i], dp[i - 1][j]);} else {dp[i][j] = dp[i - 1][j];}}
}
完整代码
#include <iostream>
#include <cstring>
using namespace std;int dp[21][1010];
int w[21], c[21];int main() {int N, V;cin >> N >> V;for (int i = 1; i <= N; i++) {cin >> w[i] >> c[i];}for(int i = 1; i <= N; i++){for(int j = 0; j <= V; j++){if(j >= c[i]) {dp[i][j] = max(dp[i][j - c[i]] + w[i], dp[i - 1][j]);}else {dp[i][j] = dp[i-1][j];}}}cout << dp[N][V] << endl;return 0;
}
相关文章:
完全背包问题(c++)
完全背包问题 当前有 N 种物品,第 i 种物品的体积是 ci,价值是 wi。 每种物品的数量都是无限的,可以选择任意数量放入背包。 现有容量为 V 的背包,请你放入若干物品,使总体积不超过 V,并且总价值尽可…...
综合性练习(验证码案例)
目录 一、需求 二、准备工作 三、约定前后端交互接口 1、需求分析 2、接口定义 四、Hutool工具介绍 1、引入依赖 2、测试使用Hutool生成验证码 五、实现服务器端代码 代码解读: 六、调整前端页面代码 七、运行测试 随着安全性的要求越来越高,…...
实用的Chrome命令 帮你打开Chrome浏览器的隐藏功能
前言 Chrome作为主力浏览器,支持相当丰富的第三方扩展,其实浏览器本身也内置了大量实用的命令。许多实用的功能并没有直接显示在Chrome的菜单上。在这篇文章中,我们将介绍几个实用的chrome:// commands。 通过下面整理的 Chrome 命令&#x…...
Linux提权--定时任务--打包配合 SUID(本地)文件权限配置不当(WEB+本地)
免责声明:本文仅做技术交流与学习... 目录 定时任务 打包配合 SUID-本地 原理: 背景: 操作演示: 分析: 实战发现: 定时任务 文件权限配置不当-WEB&本地 操作演示: 定时任务 打包配合 SUID-本地 原理: 提权通过获取计划任务执行文件信息进行提权 . 1、相对路径和…...
CSS-盒子模型
盒子模型的重要组成部分 内容区域content:width , height 内边距:内边框和内容区域的距离Padding边框线:Border外边距:Margin Border (边框线) 属性:Border 属性值:边框线粗细px 线条样式 颜色(不区分…...
WPF之页的使用
1,Page介绍。 Page直接从FrameworkElement中派生出来,WIndow从ContentControl中派生。 [Localizability(LocalizationCategory.Ignore)]public class Window : ContentControl, IWindowService{....} [ContentProperty("Content")]public class Page : Fr…...
【FFmpeg】Filter 过滤器 ② ( 裁剪过滤器 Crop Filter | 裁剪过滤器语法 | 裁剪过滤器内置变量 | 裁剪过滤器常用用法 )
文章目录 一、裁剪过滤器1、裁剪过滤器简介2、裁剪过滤器语法3、裁剪过滤器内置变量4、裁剪过滤器示例5、裁剪过滤器应用6、裁剪过滤器图示 二、裁剪过滤器常用用法1、裁剪指定像素的视频区域2、裁剪视频区域中心正方形 - 默认裁剪3、裁剪视频区域中心正方形 - 手动计算4、裁剪…...
thinkphp5 中控制器的创建和使用方法
在 ThinkPHP 5 中,控制器(Controller)是用于处理请求、执行逻辑操作并返回响应的类。以下是在 ThinkPHP 5 中创建和使用控制器的基本方法: 1. 创建控制器 在 ThinkPHP 5 中,控制器通常位于 application/index/contro…...
[Linux] 常用服务器命令(持续更新)
文件操作 # 显示文件系统的磁盘空间使用情况 df -h全局查找文件 find / -type f -iname "java"find / -name libncurses*拷贝整个文件夹 cp -r /home/a/ /home/b/ 解压,撤销解压 撤销zip解压 zipinfo -1 path/xx.zip | xargs rm -rf 撤销tar解压 tar …...
编译官方原版的openwrt并加入第三方软件包
最近又重新编译了最新的官方原版openwrt-2305(2024.3.22),此处记录一下以待日后参考。 目录 1.源码下载 1.1 通过官网直接下载 1.2 映射github加速下载 1.2.1 使用github账号fork源码 1.2.2 创建gitee账号映射github openwrt 2.编译准…...
PC适配移动端
**手机端适配** 媒体查询 组件统一样式 媒体查询写四套样式 手机 屏幕宽小于768px 平板 屏幕宽 大于等于768px 小于992px 桌面显示器 屏幕宽大于等于992px 小于1200px 大屏幕 屏幕宽大于等于1200px **页面整体及页面内容** 页面看是需要主PC还是主移动端 主移动端的话…...
springboot+vue+mybatis灵活就业服务平台+PPT+论文+讲解+售后
随着网络科技的不断发展以及人们经济水平的逐步提高,网络技术如今已成为人们生活中不可缺少的一部分,而微信小程序是通过计算机技术,针对用户需求开发与设计,该技术尤其在各行业领域发挥了巨大的作用,有效地促进了灵活…...
Android 13 系统自定义安全水印
效果 源码实现 frameworks/base/services/core/java/com/android/server/am/ActivityManagerService.java public final void showSafeModeOverlay() {View v LayoutInflater.from(mContext).inflate(com.android.internal.R.layout.safe_mode, null);WindowManager.Layout…...
C# WCF服务(由于内部错误,服务器无法处理该请求。)
由于内部错误,服务器无法处理该请求。有关该错误的详细信息,请打开服务器上的 IncludeExceptionDetailInFaults (从 ServiceBehaviorAttribute 或从 <serviceDebug> 配置行为)以便将异常信息发送回客户端,或打开对每个 Microsoft .NET …...
利用github pages建立Serverless个人博客
利用github pages建立Serverless个人博客 概述 使用github pages,可以在github上部署静态网站。利用这个功能,可以很方便地实现个人博客的发布托管。 比如我的个人博客:Buttering’s Blog 对应代码仓库:buttering/EasyBlog: 自…...
Spring Boot 集成 sa-token 实践教程
Spring Boot 集成 sa-token 实践教程 sa-token 是一个轻量级且功能强大的权限认证框架,它基于Java语言,专为Java开发者设计,以简化权限管理的复杂性。在Spring Boot项目中集成sa-token,可以快速实现会话管理、权限控制等功能。本文…...
CSS:盒子模型
目录 ▐ box—model概述 ▐ 盒子的组成 ▐ 内容区 ▐ 内边距 ▐ 边框 ▐ 外边距 ▐ 清除浏览器默认样式 ▐ box—model概述 • CSS处理网页时,它认为每个标签都包含在一个不可见的盒子里. • 如果把所有的标签都想象成盒子,那么我们对网…...
django中的cookie与session
获取cookie request.COOKIE.GET 使用cookie response.set-cookie views.py from django.http import HttpResponse from django.shortcuts import render# Create your views here. def cookie_test(request):r HttpResponse("hello world")r.set_cookie(lan, py…...
环形链表(判断链表中是否有环)的讲解
一:题目 二:思路讲解 1:采用快慢指针的方法,一个fast指针一次移动两个节点,一个slow指针一次移动一个节点。 2:两个指针从头指针开始往后遍历,如果fast指针或者fast->next 有一个为空&…...
NLP(14)--文本匹配任务
前言 仅记录学习过程,有问题欢迎讨论 步骤: * 1. 输入问题 * 2. 匹配问题库(基础资源,FAQ) * 3. 返回答案文本匹配算法: 编辑距离算法(缺点) 字符之间没有语义相似度; 受无关词/停用词影响大; 受语序影响大 Jaccar…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
