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

完全背包问题(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 种物品&#xff0c;第 i 种物品的体积是 ci​&#xff0c;价值是 wi​。 每种物品的数量都是无限的&#xff0c;可以选择任意数量放入背包。 现有容量为 V 的背包&#xff0c;请你放入若干物品&#xff0c;使总体积不超过 V&#xff0c;并且总价值尽可…...

综合性练习(验证码案例)

目录 一、需求 二、准备工作 三、约定前后端交互接口 1、需求分析 2、接口定义 四、Hutool工具介绍 1、引入依赖 2、测试使用Hutool生成验证码 五、实现服务器端代码 代码解读&#xff1a; 六、调整前端页面代码 七、运行测试 随着安全性的要求越来越高&#xff0c…...

实用的Chrome命令 帮你打开Chrome浏览器的隐藏功能

前言 Chrome作为主力浏览器&#xff0c;支持相当丰富的第三方扩展&#xff0c;其实浏览器本身也内置了大量实用的命令。许多实用的功能并没有直接显示在Chrome的菜单上。在这篇文章中&#xff0c;我们将介绍几个实用的chrome:// commands。 通过下面整理的 Chrome 命令&#x…...

Linux提权--定时任务--打包配合 SUID(本地)文件权限配置不当(WEB+本地)

免责声明:本文仅做技术交流与学习... 目录 定时任务 打包配合 SUID-本地 原理: 背景: 操作演示: 分析: 实战发现: 定时任务 文件权限配置不当-WEB&本地 操作演示: 定时任务 打包配合 SUID-本地 原理: 提权通过获取计划任务执行文件信息进行提权 . 1、相对路径和…...

CSS-盒子模型

盒子模型的重要组成部分 内容区域content&#xff1a;width , height 内边距&#xff1a;内边框和内容区域的距离Padding边框线&#xff1a;Border外边距&#xff1a;Margin Border (边框线) 属性&#xff1a;Border 属性值&#xff1a;边框线粗细px 线条样式 颜色(不区分…...

WPF之页的使用

1,Page介绍。 Page直接从FrameworkElement中派生出来&#xff0c;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 中&#xff0c;控制器&#xff08;Controller&#xff09;是用于处理请求、执行逻辑操作并返回响应的类。以下是在 ThinkPHP 5 中创建和使用控制器的基本方法&#xff1a; 1. 创建控制器 在 ThinkPHP 5 中&#xff0c;控制器通常位于 application/index/contro…...

[Linux] 常用服务器命令(持续更新)

文件操作 # 显示文件系统的磁盘空间使用情况 df -h全局查找文件 find / -type f -iname "java"find / -name libncurses*拷贝整个文件夹 cp -r /home/a/ /home/b/ 解压&#xff0c;撤销解压 撤销zip解压 zipinfo -1 path/xx.zip | xargs rm -rf 撤销tar解压 tar …...

编译官方原版的openwrt并加入第三方软件包

最近又重新编译了最新的官方原版openwrt-2305&#xff08;2024.3.22&#xff09;&#xff0c;此处记录一下以待日后参考。 目录 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+论文+讲解+售后

随着网络科技的不断发展以及人们经济水平的逐步提高&#xff0c;网络技术如今已成为人们生活中不可缺少的一部分&#xff0c;而微信小程序是通过计算机技术&#xff0c;针对用户需求开发与设计&#xff0c;该技术尤其在各行业领域发挥了巨大的作用&#xff0c;有效地促进了灵活…...

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服务(由于内部错误,服务器无法处理该请求。)

由于内部错误&#xff0c;服务器无法处理该请求。有关该错误的详细信息&#xff0c;请打开服务器上的 IncludeExceptionDetailInFaults (从 ServiceBehaviorAttribute 或从 <serviceDebug> 配置行为)以便将异常信息发送回客户端&#xff0c;或打开对每个 Microsoft .NET …...

利用github pages建立Serverless个人博客

利用github pages建立Serverless个人博客 概述 使用github pages&#xff0c;可以在github上部署静态网站。利用这个功能&#xff0c;可以很方便地实现个人博客的发布托管。 比如我的个人博客&#xff1a;Buttering’s Blog 对应代码仓库&#xff1a;buttering/EasyBlog: 自…...

Spring Boot 集成 sa-token 实践教程

Spring Boot 集成 sa-token 实践教程 sa-token 是一个轻量级且功能强大的权限认证框架&#xff0c;它基于Java语言&#xff0c;专为Java开发者设计&#xff0c;以简化权限管理的复杂性。在Spring Boot项目中集成sa-token&#xff0c;可以快速实现会话管理、权限控制等功能。本文…...

CSS:盒子模型

目录 ▐ box—model概述 ▐ 盒子的组成 ▐ 内容区 ▐ 内边距 ▐ 边框 ▐ 外边距 ▐ 清除浏览器默认样式 ▐ box—model概述 • CSS处理网页时&#xff0c;它认为每个标签都包含在一个不可见的盒子里. • 如果把所有的标签都想象成盒子&#xff0c;那么我们对网…...

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…...

环形链表(判断链表中是否有环)的讲解

一&#xff1a;题目 二&#xff1a;思路讲解 1&#xff1a;采用快慢指针的方法&#xff0c;一个fast指针一次移动两个节点&#xff0c;一个slow指针一次移动一个节点。 2&#xff1a;两个指针从头指针开始往后遍历&#xff0c;如果fast指针或者fast->next 有一个为空&…...

NLP(14)--文本匹配任务

前言 仅记录学习过程&#xff0c;有问题欢迎讨论 步骤&#xff1a; * 1. 输入问题 * 2. 匹配问题库&#xff08;基础资源,FAQ&#xff09; * 3. 返回答案文本匹配算法&#xff1a; 编辑距离算法(缺点) 字符之间没有语义相似度; 受无关词/停用词影响大; 受语序影响大 Jaccar…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...