当前位置: 首页 > 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轮播图去除两侧阴影及线框的方法,本文通过示例代码给大家介绍的非常详细…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...