小苯的01背包easy(枚举,位运算,思维推导)

2024-05-26 00:36

本文主要是介绍小苯的01背包easy(枚举,位运算,思维推导),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 题目描述
    • 输入格式
    • 输出格式
    • 样例输入1
    • 样例输出1
    • 样例输入2
    • 样例输出2
    • 提交链接
    • 提示
  • 解析
  • 参考代码

题目描述

小苯有一个容量为 k k k 的背包,现在有 n n n 个物品,每个物品有一个体积 v v v 和价值 w w w,他想知道在体积不超过 k k k 的前提下,他最多能装价值为多少的物品。

本问题中,物品的总体积定义为所装物品的体积的 &(按位与),总价值也定义为所装物品的价值的 &(按位与)。

(如果不选物品,则价值为 0,所占体积也为 0。)

输入格式

输入包含 n + 1 n+1 n+1 行。

第一行两个正整数 n , k ( 1 ≤ n ≤ 2 ∗ 1 0 3 , 0 ≤ k ≤ 2 ∗ 1 0 3 ) n,k(1 \leq n \leq 2*10^3,0 \leq k \leq 2 * 10^3) n,k(1n2103,0k2103)分别表示物品个数和背包容量。

接下来 n n n 行,每行两个正整数 v i , w i ( 0 ≤ v i , w i ( 0 ≤ v i , w i ≤ 2 ∗ 1 0 3 ) ) v_i,w_i(0 \leq v_i,w_i(0 \leq v_i,w_i \leq 2 * 10^3)) vi,wi(0vi,wi(0vi,wi2103)) ,表示每个物品的体积和价值。

输出格式

输出包含一行一个整数,表示能装的最大价值。

样例输入1

3 1
7 3
10 7
9 6

样例输出1

2

样例输入2

3 2
7 3
10 7
9 6

样例输出2

3

提交链接

https://hydro.ac/d/lp728/p/23

提示

样例解释 1 1 1
选择第一个和第三个物品。
体积为:7 & 9 = 1
价值为:3 & 6 = 2。
可以证明不存在比 2 2 2 更大的价值。

样例解释 2 2 2
选择第一个和第二个物品。

解析

& 操作的特点,越 & 越小。

现在需要找到最大价值, 设其为 a n s ans ans

v a l u e [ 1 ] value[1] value[1] & v a l u e [ 2 ] value[2] value[2] & … = a n s ans ans,可以得到: a n s ans ans & v a l u e [ i ] value[i] value[i] = a n s ans ans ( a n s ans ans 在任意一位的 1 1 1, 每个 v a l u e value value 在对应位上都有)

体积是选的越多越可行, 所以可以枚举答案。

然后按 ans & value[i] = ans 这个条件,选出所有物品

计算出这些物品的总体积, 如果满足容量 k k k 限制, 则找到一个可行解。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 9;
int n , k , v[maxn] , w[maxn] , mx;
int main()
{cin >> n >> k;for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];    //体积  价值for(int s = 2000; s >= 0; s--)  //枚举答案  答案不会超过最大的wi{int weight = (1 << 20) - 1; //按位与的初始条件 for(int i = 1; i <= n; i++){if((s & w[i]) == s)  //可以选的物品weight = weight & v[i];  //体积按位与}if(weight <= k){mx = s;break;}    }cout << mx;return 0;
}

这篇关于小苯的01背包easy(枚举,位运算,思维推导)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1003058

相关文章

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C

Java 枚举的基本使用方法及实际使用场景

《Java枚举的基本使用方法及实际使用场景》枚举是Java中一种特殊的类,用于定义一组固定的常量,枚举类型提供了更好的类型安全性和可读性,适用于需要定义一组有限且固定的值的场景,本文给大家介绍Jav... 目录一、什么是枚举?二、枚举的基本使用方法定义枚举三、实际使用场景代替常量状态机四、更多用法1.实现接

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算(标量与矩阵)、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元

使用easy connect之后,maven无法使用,原来需要配置-Djava.net.preferIPv4Stack=true问题

《使用easyconnect之后,maven无法使用,原来需要配置-Djava.net.preferIPv4Stack=true问题》:本文主要介绍使用easyconnect之后,maven无法... 目录使用easGWowCy connect之后,maven无法使用,原来需要配置-DJava.net.pr

Python位移操作和位运算的实现示例

《Python位移操作和位运算的实现示例》本文主要介绍了Python位移操作和位运算的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 位移操作1.1 左移操作 (<<)1.2 右移操作 (>>)注意事项:2. 位运算2.1

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

SpringBoot集成图片验证码框架easy-captcha的详细过程

《SpringBoot集成图片验证码框架easy-captcha的详细过程》本文介绍了如何将Easy-Captcha框架集成到SpringBoot项目中,实现图片验证码功能,Easy-Captcha是... 目录SpringBoot集成图片验证码框架easy-captcha一、引言二、依赖三、代码1. Ea

SpringBoot整合easy-es的详细过程

《SpringBoot整合easy-es的详细过程》本文介绍了EasyES,一个基于Elasticsearch的ORM框架,旨在简化开发流程并提高效率,EasyES支持SpringBoot框架,并提供... 目录一、easy-es简介二、实现基于Spring Boot框架的应用程序代码1.添加相关依赖2.添

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi