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

代码随想录Day42 | 01背包问题| 416. 分割等和子集

01背包问题(Acwing)

        

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入格式

第一行两个整数,N,V,,用空格隔开,分别表示物品数量和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数,表示最大价值。

代码(二维):

         

#include<bits/stdc++.h>
using namespace std;
const int N = 1100;
int n,v;
int v1[N];
int w[N];int f[N][N];int main()
{cin >> n>>v;for (int i = 1; i <= n; i ++ ){cin>>v1[i];cin>>w[i];}for(int i=1;i<=n;i++){for(int j=0;j<=v;j++){for(int k=0;k<=1;k++){   //每件物品最多取几次,k就设定为几次if(j>=k*v1[i])    //能装下k个该物品f[i][j]=max(f[i][j],f[i-1][j-k*v1[i]]+k*w[i]);}}}cout<<f[n][v];
}

   代码(一维):

#include<bits/stdc++.h>
using namespace std;
const int N = 1100;
int n,v;
int v1[N];
int w[N];int f[N];int main()
{cin >> n>>v;for (int i = 1; i <= n; i ++ ){cin>>v1[i];cin>>w[i];}for(int i=1;i<=n;i++){for(int j=v;j>=0;j--){   //一维数组存储需要倒序,防止被“污染”for(int k=0;k<=1;k++){   //每件物品最多取几次,k就设定为几次if(j>=k*v1[i])    //能装下k个该物品f[j]=max(f[j],f[j-k*v1[i]]+k*w[i]);}}}cout<<f[v];
}

        我编写的是通用的模板,如果每件物品限定了使用次数的时候,修改k的限制即可。

416. 分割等和子集

class Solution {
public:bool canPartition(vector<int>& nums) {int sum=0;int n=nums.size();for(int i=0;i<n;i++){sum+=nums[i];}if(sum%2==1) return false;int target = sum/2;int f[20010]={0};for(int i=0;i<nums.size();i++){for(int j=target;j>=nums[i];j--){f[j] = max(f[j],f[j-nums[i]]+nums[i]);}}if(f[target]==target) return true;else return false;}
};

        

相关文章:

代码随想录Day42 | 01背包问题| 416. 分割等和子集

01背包问题&#xff08;Acwing&#xff09; 有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi&#xff0c;价值是 wi。 求解将哪些物品装入背包&#xff0c;可使这些物品的总体积不超过背包容量&#xff0c;且总价值最大。 输出最大价值。 输入…...

UML六大关系总结

UML六大关系有&#xff1a;继承、关系、聚合、组合、实现、依赖。分为通过图和代码总结这些关系。 1、继承 继承&#xff08;Inheritance&#xff09;&#xff1a;表示类之间的继承关系&#xff0c;子类继承父类的属性和方法&#xff0c;并可以添加自己的扩展。 继承&#x…...

ElementUI基本介绍及登录注册案例演示

目录 前言 一.简介 二.优缺点 三.Element完成登录注册 1. 环境配置及前端演示 1.1 安装Element-UI模块 1.2 安装axios和qs(发送get请求和post请求) 1.3 导入依赖 2 页面布局 2.1组件与界面 3.方法实现功能数据交互 3.1 通过方法进行页面跳转 3.2 axios发送get请求 …...

Python爬虫-某网酒店评论数据

前言 本文是该专栏的第6篇,后面会持续分享python爬虫案例干货,记得关注。 本文以某网的酒店数据为例,采集对应酒店的评论数据。具体思路和方法跟着笔者直接往下看正文详细内容。(附带完整代码) 注意:本文的案例“数据集”,选用的是本专栏上一篇“Python爬虫-某网酒店数…...

C# Onnx Yolov8 Detect 水果识别

效果 项目 代码 using Microsoft.ML.OnnxRuntime; using Microsoft.ML.OnnxRuntime.Tensors; using OpenCvSharp; using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System…...

测试网页调用本地可执行程序(续1:解析参数中的中文编码)

学习测试网页调用本地可执行程序还遗留一个问题&#xff0c;即网页中调用带中文参数的命令时&#xff0c;本地可执行程序接收到的参数字符串里的中文都转换成了编码模式&#xff0c;看起来如下所示&#xff1a; <a href TestPageCall:-a你好>启动测试程序</a><…...

C++入门知识

Hello&#xff0c;今天我们分享一些关于C入门的知识&#xff0c;看完至少让你为后面的类和对象有一定的基础&#xff0c;所以在讲类和对象的时候&#xff0c;我们需要来了解一些关于C入门的知识。 什么是C C语言是结构化和模块化的语言&#xff0c;适合处理较小规模的程序。对…...

spring和springmvc常用注解

1.Spring常用注解&#xff1a; 1&#xff09;Repository将DAO类声明为Bean 2&#xff09;Service用于修饰service层的组件 3&#xff09;Controller通常作用在控制层&#xff0c;将在Spring MVC中使用 4&#xff09;Component是一个泛化的概念&#xff0c;仅仅表示spring中的一…...

【Java】Java生成PDF工具类

Java生成PDF工具类 一、介绍 Java生成PDF工具类是一个非常实用的工具类&#xff0c;可以帮助我们以程序化的方式生成PDF文件。通过该工具类&#xff0c;我们可以向PDF文件中添加文字、图片、表格等多种内容&#xff0c;并且可以进行格式化和样式设置。Java生成PDF工具类常用于…...

STL map,插入和查找的一些注意事项

01、前言&#xff08;废话&#xff09; C 的 std::map 容器中插入键值对主要有myMap(std::make_pair(key value)) &#xff0c;它们的区别你了解吗&#xff1f; auto it myMap,find(key) 和 auto value myMap[key] 都可以用于在 C 的 std::map 容器中查找键对应的值&#xff…...

基于springboot+vue的客户关系管理系统(前后端分离)

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容&#xff1a;毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 项目介绍…...

【Java 基础篇】Java Stream 流详解

Java Stream&#xff08;流&#xff09;是Java 8引入的一个强大的新特性&#xff0c;用于处理集合数据。它提供了一种更简洁、更灵活的方式来操作数据&#xff0c;可以大大提高代码的可读性和可维护性。本文将详细介绍Java Stream流的概念、用法和一些常见操作。 什么是Stream…...

题解:ABC321A - 321-like Checker

题解&#xff1a;ABC321A - 321-like Checker 题目 链接&#xff1a;Atcoder。 链接&#xff1a;洛谷。 难度 算法难度&#xff1a;C。 思维难度&#xff1a;C。 调码难度&#xff1a;C。 综合评价&#xff1a;见洛谷链接。 算法 模拟。 思路 输入n后从后往前依次抽…...

Zig实现Hello World

1. 什么是zig 先列出一段官方的介绍: Zig is a general-purpose programming language and toolchain for maintaining robust, optimal, and reusable software. 大概意思就是说&#xff1a; Zig是一种通用编程语言和工具链&#xff0c;用于维护健壮、最佳和可重用的软件。 官…...

Vue3+element-plus切换标签页时数据保留问题

记录一次切换标签页缓存失效问题&#xff0c;注册路由时name不一致可能会导致缓存失效...

前端教程-TypeScript

官网 TypeScript官网 TypeScript中文官网 视频教程 尚硅谷TypeScript教程&#xff08;李立超老师TS新课&#xff09;...

代码随想录算法训练营 动态规划part06

一、完全背包 卡哥的总结&#xff0c;还挺全代码随想录 (programmercarl.com) 二、零钱兑换 II 518. 零钱兑换 II - 力扣&#xff08;LeetCode&#xff09; 被选物品之间不需要满足特定关系&#xff0c;只需要选择物品&#xff0c;以达到「全局最优」或者「特定状态」即可。 …...

能跑通的mmdet3d版本

能跑通的mmdet3d版本 1.0版本 2.0版本 注意&#xff1a;mmdet和mmdet3d简单地运行 pip install -v -e . 将会安装最低运行要求的版本。不要pip install -r requirements.txt安装依赖项&#xff0c;否则依赖库版本不对。 运行mmdet3d时&#xff0c;注释掉以上代码。...

SD-MTSP:萤火虫算法(FA)求解单仓库多旅行商问题MATLAB(可更改数据集,旅行商的数量和起点)

一、萤火虫算法&#xff08;FA&#xff09;简介 萤火虫算法(Firefly Algorithm&#xff0c;FA)是Yang等人于2009年提出的一种仿生优化算法。 参考文献&#xff1a;田梦楚, 薄煜明, 陈志敏, et al. 萤火虫算法智能优化粒子滤波[J]. 自动化学报, 2016, 42(001):89-97. 二、单仓…...

bootstrapv4轮播图去除两侧阴影及线框的方法

文章目录 前言一、前提条件&#xff1a;二、bootstrap文档组件展示与实际应用1.官方文档展示如下&#xff1a;没有阴影2.实际应用情况如下&#xff1a; 三、解决方案 前言 这篇文章主要介绍了bootstrapv4轮播图去除两侧阴影及线框的方法,本文通过示例代码给大家介绍的非常详细…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

前端开发者常用网站

Can I use网站&#xff1a;一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use&#xff1a;Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站&#xff1a;MDN JavaScript权威网站&#xff1a;JavaScript | MDN...

大数据驱动企业决策智能化的路径与实践

&#x1f4dd;个人主页&#x1f339;&#xff1a;慌ZHANG-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、引言&#xff1a;数据驱动的企业竞争力重构 在这个瞬息万变的商业时代&#xff0c;“快者胜”的竞争逻辑愈发明显。企业如何在复杂环…...