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

动态规划入门之01背包变形嗑药

P1802 5 倍经验日 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

嗑药固然可耻,但是能让你快速变强   --鲁迅

手动滑稽,话归正题

动态规划之背包入门01背包模板_爱莉我老婆的博客-CSDN博客

这是01背包的模板,没看的可以去看看。

我们把药品总量看成一个背包,我们把打败每一人的药品消耗看成体积,那么就是说我们把这个物品装进背包会产生一个价值,不装进背包也会产生一个价值。那么我们在01背包的基础上改进,可以写出如下状态转移方程

for(c=1;c<=a;c++) {String[] bStrings=br1.readLine().split(" ");int e=Integer.parseInt(bStrings[0]);//输入打输时的价值(即装不进背包的价值)int f=Integer.parseInt(bStrings[1]);//(装进背包的价值)int g=Integer.parseInt(bStrings[2]);//物品所占的空间	for(d=b;d>=0;d--) {//枚举体积,由于我们采用一维压缩,所以倒序保证物品之多会被选择一件if(d>=g) {//体积达到,从不装第c个物品前c-1个物品里边选取放到容积为d的背包dp[d]=Math.max(dp[d]+e, dp[d-g]+f);//选择第c个物品,}else {dp[d]=dp[d]+e;//体积不够直接装装不了的价值}}
}

完整代码:


import java.awt.FontFormatException;
import java.io.BufferedReader; 
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.AnnotatedWildcardType;
import java.math.BigInteger;
import java.net.DatagramPacket;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Spliterator.OfPrimitive;
import java.util.function.IntToDoubleFunction;
import java.util.function.LongBinaryOperator;
import java.util.TreeMap;
import java.util.TreeSet;
import javax.management.relation.InvalidRelationTypeException;
import javax.print.attribute.standard.JobMessageFromOperator;
import javax.print.attribute.standard.JobPriority;
import javax.swing.plaf.ColorChooserUI;
import javax.swing.table.TableModel;
import javax.swing.text.TabSet;
import javax.xml.crypto.dsig.spec.DigestMethodParameterSpec;
public class Main {public static void main(String[] args) throws IOException  {
Scanner sc=new Scanner(System.in);
BufferedReader br1=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1=new PrintWriter(System.out);
String[] aStrings=br1.readLine().split(" ");
int a=Integer.parseInt(aStrings[0]);
int b=Integer.parseInt(aStrings[1]);
dp=new long[b+1];int c,d;
for(c=1;c<=a;c++) {String[] bStrings=br1.readLine().split(" ");int e=Integer.parseInt(bStrings[0]);int f=Integer.parseInt(bStrings[1]);int g=Integer.parseInt(bStrings[2]);	for(d=b;d>=0;d--) {if(d>=g) {dp[d]=Math.max(dp[d]+e, dp[d-g]+f);}else {dp[d]=dp[d]+e;}}
}
System.out.println(5*dp[b]);}public static long[] dp;}

此题必须开long

相关文章:

动态规划入门之01背包变形嗑药

P1802 5 倍经验日 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 嗑药固然可耻&#xff0c;但是能让你快速变强 --鲁迅 手动滑稽&#xff0c;话归正题 动态规划之背包入门01背包模板_爱莉我老婆的博客-CSDN博客 这是01背包的模板&#xff0c;没看的可以去看看。 我们把…...

数据结构——栈和队列OJ题

栈和队列小提升&#xff01; 前言一、用队列实现栈队列接口实现&#xff08;1&#xff09;栈的接口定义&#xff08;2&#xff09;栈的初始化&#xff08;3&#xff09;入栈函数的定义&#xff08;4&#xff09;出栈函数的定义&#xff08;5&#xff09;查找栈顶元素&#xff0…...

同态排序算法

参考文献&#xff1a; [Batcher68] Batcher K E. Sorting networks and their applications[C]//Proceedings of the April 30–May 2, 1968, spring joint computer conference. 1968: 307-314. [SV11] Smart, N.P., Vercauteren, F.: Fully homomorphic SIMD operations. IA…...

“深入探索JVM内部机制:解析Java虚拟机的工作原理“

标题&#xff1a;深入探索JVM内部机制&#xff1a;解析Java虚拟机的工作原理 摘要&#xff1a;本文将介绍Java虚拟机&#xff08;JVM&#xff09;的工作原理&#xff0c;包括类加载、内存管理、垃圾回收和字节码执行等方面。通过深入理解JVM的内部机制&#xff0c;开发人员可以…...

为应用程序接入阿里云CDN优化网站访问速度

文章目录 1.KodCloud云盘系统接入CDN之前的效果2.配置KodCloud云盘接入CDN加速器2.1.添加CDN域名2.2.配置域名信息2.3.CDN推荐配置设置2.4.CDN加速器配置完成 3.配置云解析DNS增加CDN域名的解析4.为CDN加速器配置HTTPS5.验证网站是否接入CDN6.访问应用程序观察请求速度7.观察CD…...

索引设计规范

索引是帮助数据库高效获取数据的数据结构。索引是加速查询的常用技术手段。在设计索引时&#xff0c;要遵循索引设计规范&#xff0c;避免不必要的踩坑。 【推荐】索引存储结构推荐BTREE InnoDB和MyISAM存储引擎表&#xff0c;索引类型必须为BTRER&#xff0c;MEMORY表可以根…...

Appium 2安装与使用java对Android进行自动化测试

文章目录 1、Appium 2.1安装1.1、系统要求1.2、安装Appium2.1服务1.3、安装UiAutomator2驱动1.4、安装Android SDK platform tools1.5、下载OpenJDK 2、Android自动代码例子2.1、安装Android自动化测试元素定位工具Appium Inspector2.2、编写android app自动化测试代码和使用ex…...

小程序运营方式有哪些?如何构建小程序运营框架?

​如今&#xff0c;每个企业基本都做过至少一个小程序&#xff0c;但由于小程序本身不具备流量、也很少有自然流量&#xff0c;因此并不是每个企业都懂如何运营小程序。想了解小程序运营方式方法有哪些&#xff1f; 在正式运营小程序前&#xff0c;了解小程序的功能与企业实际经…...

【golang】for语句和switch语句

使用携带range子句的for语句时需要注意哪些细节&#xff1f; numbers1 : []int{1, 2, 3, 4, 5, 6} for i : range numbers1 {if i 3 {numbers1[i] | i} } fmt.Println(numbers1)这段代码执行后会打印出什么内容&#xff1f; 答案&#xff1a;[1 2 3 7 5 6] 当for语句被执行…...

三、数据库索引

1、索引介绍 索引是一种用于快速查询和检索数据的数据结构&#xff0c;其本质可以看成是一种排序好的数据结构。 常见的索引结构有&#xff1a;B数&#xff0c;B树&#xff0c;Hash和红黑树等。在MySQL中&#xff0c;无论是 InnoDB还是MyISAM&#xff0c;都使用了B树作为索引…...

长时间带什么耳机最舒服,分享长时间佩戴舒服的耳机推荐

时代在进步&#xff0c;科技在不断革新。近年来&#xff0c;一种崭新的耳机——骨传导耳机&#xff0c;如火如荼地进驻耳机市场&#xff0c;引起一阵热潮。不论是平日里的工作出勤还是运动时的挥洒汗水&#xff0c;相比传统耳机&#xff0c;骨传导耳机无疑更加贴合现代生活的需…...

Yolov8小目标检测(1)

💡💡💡本文目标:通过原始基于yolov8的红外弱小目标检测,训练得到初版模型,进行问题点分析; 💡💡💡Yolo小目标检测,独家首发创新(原创),适用于Yolov5、Yolov7、Yolov8等各个Yolo系列,专栏文章提供每一步步骤和源码,带你轻松实现小目标检测涨点 💡💡…...

GPS定位漂移问题分析

有很多种因素会影响到GPS的准确率&#xff0c;以下是一个GPS误差引入简表&#xff1a; l 卫星时钟误差&#xff1a;0-1.5米 l 卫星轨道误差&#xff1a;1-5米 l 电离层引入的误差&#xff1a;0-30米 l 大气层引入的误差&#xff1a;0-30米 l 接收机…...

前端简介(HTML+CSS+JS)

学习Django过程中遇到一些前端相关的内容&#xff0c;于是整理了一下相关概念。 前端开发是创建WEB页面或APP等前端界面呈现给用户的过程。 如果只是想要入门前端&#xff0c;只要学习网页三剑客(HTML、CSS、JavaScript)即可。 如果把网页比喻成一个房子&#xff0c;HTML就是…...

List与String数组互转

一.List 转为 String 数组 1.使用toArray方法 public static void main(String[] args) {List<String> list Lists.newArrayList("1","2","3");// Java6以前版本String[] str1 list.toArray(new String[list.size()]);// Java6以后版本…...

MySQL中的数据类型

文章目录 1 常见的数据类型2 整数类型2.1 属性 M2.2 属性 UNSIGNED2.3 属性 ZEROFILL2.4 整数类型的适用场景 3 浮点类型4 定点类型5 位类型6 日期与时间类型6.1 YEAR 类型6.2 DATE 类型6.3 TIME 类型6.4 DATETIME 类型6.5 TIMESTAMP 类型 1 常见的数据类型 类型类型分类整数类…...

python多任务

​ 一、多任务 1.1 概念 多任务就是指&#xff1a;同一时间能执行多个任务。比方我们的电脑能一边QQ聊天&#xff0c;一边写论文&#xff0c;还能听歌。 1.2 多任务的优势&#xff1a; 多任务的最大好处是 充分利用CPU资源&#xff0c;提高程序的执行效率。 1.3 多任务的两种表…...

c语言 - inline关键字(内联函数)

概念 在编程中&#xff0c;inline是一个关键字&#xff0c;用于修饰函数。inline函数是一种对编译器的提示&#xff0c;表示这个函数在编译时应该进行内联展开。 内联展开是指将函数的代码插入到调用该函数的地方&#xff0c;而不是通过函数调用的方式执行。这样可以减少函数调…...

如何在Ubuntu 18.04上安装PHP 7.4并搭建本地开发环境

引言 PHP是一种流行的服务器脚本语言&#xff0c;用于创建动态和交互式web页面。开始使用你选择的语言是学习编程的第一步。 本教程将指导您在Ubuntu上安装PHP 7.4&#xff0c;并通过命令行设置本地编程环境。您还将安装依赖管理器Composer&#xff0c;并通过运行脚本来测试您…...

狭义相对论

文章目录 一、为什么光速不变&#xff1f;二、为什么爱因斯坦坚信“相对性原理”三、逻辑和数学显威力&#xff0c;狭义相对论时空变换&#xff08;洛伦兹变换&#xff09;推导四、新时空变换带来的新时空观1、有关相对论时间的“傻问题”2、关于相对论的“怪问题”3、关于“双…...

沉浸式翻译扩展常见问题解决方案

沉浸式翻译扩展常见问题解决方案 【免费下载链接】immersive-translate 沉浸式双语网页翻译扩展 , 支持输入框翻译&#xff0c; 鼠标悬停翻译&#xff0c; PDF, Epub, 字幕文件, TXT 文件翻译 - Immersive Dual Web Page Translation Extension 项目地址: https://gitcode.c…...

Phi-4-reasoning-vision-15B快速上手:使用Postman完成图像问答API全流程调试

Phi-4-reasoning-vision-15B快速上手&#xff1a;使用Postman完成图像问答API全流程调试 1. 引言&#xff1a;认识视觉推理模型 Phi-4-reasoning-vision-15B是微软推出的新一代视觉多模态推理模型&#xff0c;它能像人类一样理解图片内容并进行智能问答。想象一下&#xff0c…...

终极指南:如何快速构建响应式React网格布局

终极指南&#xff1a;如何快速构建响应式React网格布局 【免费下载链接】react-grid-layout A draggable and resizable grid layout with responsive breakpoints, for React. 项目地址: https://gitcode.com/gh_mirrors/re/react-grid-layout React网格布局&#xff0…...

3个技巧让Poppins字体为你的设计项目增添国际范儿

3个技巧让Poppins字体为你的设计项目增添国际范儿 【免费下载链接】Poppins Poppins, a Devanagari Latin family for Google Fonts. 项目地址: https://gitcode.com/gh_mirrors/po/Poppins 还在为多语言项目找不到统一风格的字体而烦恼吗&#xff1f;Poppins这款现代几…...

LoRA训练助手入门解析:为什么权重排序对LoRA训练效果影响显著

LoRA训练助手入门解析&#xff1a;为什么权重排序对LoRA训练效果影响显著 1. 认识LoRA训练助手 如果你正在尝试训练自己的AI绘画模型&#xff0c;可能会遇到一个常见问题&#xff1a;为什么同样的图片&#xff0c;用不同的标签训练出来的效果差距那么大&#xff1f;这就是我们…...

使用Chandra构建数学建模助手:美赛备战全攻略

使用Chandra构建数学建模助手&#xff1a;美赛备战全攻略 1. 引言 数学建模竞赛就像一场智力马拉松&#xff0c;需要在有限时间内解决复杂问题。每年美赛期间&#xff0c;无数团队熬夜奋战&#xff0c;只为找到最优解决方案。但现实往往是&#xff1a;选题纠结、算法选择困难…...

Phi-3-mini-4k-instruct-gguf多场景:覆盖个人提效、团队协作、客户支持全链路

Phi-3-mini-4k-instruct-gguf多场景&#xff1a;覆盖个人提效、团队协作、客户支持全链路 1. 认识Phi-3-mini-4k-instruct-gguf Phi-3-mini-4k-instruct-gguf是微软Phi-3系列中的轻量级文本生成模型GGUF版本。这个开箱即用的工具特别适合处理日常工作中的文本任务&#xff0c…...

RTX 3090环境下的BEVFusion实战部署:从源码编译到多模态训练调优

1. RTX 3090环境准备与BEVFusion适配 在RTX 3090上部署BEVFusion最大的挑战就是硬件与软件版本的兼容性问题。官方推荐的环境是CUDA 9.2和PyTorch 1.3.1&#xff0c;但这对于RTX 3090来说完全不适用——30系显卡需要CUDA 11才能发挥全部性能。我刚开始尝试直接按照官方文档安装…...

Wan2.1视频生成小白必看:避开这些坑,让你的视频生成一次成功

Wan2.1视频生成小白必看&#xff1a;避开这些坑&#xff0c;让你的视频生成一次成功 1. 为什么你的视频生成总是失败&#xff1f; 很多新手第一次使用Wan2.1视频生成模型时&#xff0c;都会遇到各种问题&#xff1a;生成的视频模糊不清、内容与描述不符、甚至直接失败。这通常…...

AIVideo效果对比展示:不同参数下的视频生成质量评测

AIVideo效果对比展示&#xff1a;不同参数下的视频生成质量评测 1. 开场白&#xff1a;参数设置对视频效果的影响 你有没有遇到过这样的情况&#xff1a;用AI生成视频时&#xff0c;明明输入的内容一样&#xff0c;但出来的效果却天差地别&#xff1f;有时候画面模糊不清&…...