算法Day23 简单吃饭(0-1背包)

简单吃饭(0-1背包)

Description

在这里插入图片描述

Input

在这里插入图片描述

Output

在这里插入图片描述

Sample

在这里插入图片描述

代码

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int total = scanner.nextInt();int price[] = new int[n];int high[] = new int[n];for(int i =0;i<n;i++){price[i] = scanner.nextInt();high[i] = scanner.nextInt();}System.out.println(process(price,high,total));}public static int process(int price[],int high[],int prices){//总计happyint dp[][] = new int[price.length+1][prices+1];for(int i=1;i<=price.length;i++){for(int j=1;j<=prices;j++){dp[i][j]=dp[i-1][j];if(j>=price[i-1]){dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-price[i-1]]+high[i-1]);}}}return dp[price.length][prices];}
}

思路

使用动态规划,与完全吃饭类似
注意的是dp[i][j]=dp[i-1][j]
这样是保证选取的食物有序,对食物仅能选取0-1次

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Centos7、Mysql8.0 load_file函数返回为空的终极解决方法--暨selinux的深入理解

零、问题背景 最近想换房&#xff0c;为了方便自己对比感兴趣的房子&#xff0c;因此决定将目标房源的基本信息放在表里&#xff0c;特别是要一目了然的看到众多房子的各种图纸和照片&#xff0c;因此决定要在Mysql8.0.34数据库中以二进制形式保存图片&#xff08;抛开合理性和…

多人聊天UDP

服务端 package 多人聊天;import java.io.BufferedReader; import java.io.InputStream; import java.io.InputStreamReader; import java.io.OutputStream; import java.io.PrintStream; import java.net.ServerSocket; import java.net.Socket; import java.util.ArrayList;…

蓝桥杯日期问题

蓝桥杯其他真题点这里&#x1f448; 注意日期合法的判断 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;public class Main{static int[] days {0,31,28,31,30,31,30,31,31,30,31,30,31};static BufferedReader in new Buf…

TP5上传图片压缩尺寸

图片上传&#xff0c;最简单的就是&#xff0c; 方法一&#xff1a; 修改上传限制&#xff0c;不让上传大于多少多少的图片 改一下size即可&#xff0c;默认单位是B换算成M还需要除以两次1024 方法二&#xff1a; 对上传的图片进行缩放&#xff0c;此办法网上找了不少的代码…

了解c++11中的新增

一&#xff0c;统一的初始化列表 在引入c11后&#xff0c;我们得出计划都可以用初始化列表进行初始化。 C11 扩大了用大括号括起的列表 ( 初始化列表 ) 的使用范围&#xff0c;使其可用于所有的内置类型和用户自 定义的类型&#xff0c; 使用初始化列表时&#xff0c;可添加等…

JDK中lock锁的机制,其底层是一种无锁的架构实现的,公平锁和非公平锁

简述JDK中lock锁的机制&#xff0c;其底层是一种无锁的架构实现的&#xff0c;是否知道其是如何实现的 synchronized与lock lock是一个接口&#xff0c;而synchronized是在JVM层面实现的。synchronized释放锁有两种方式&#xff1a; 获取锁的线程执行完同步代码&#xff0c;…

androidstudio设置内存

androidstudio一直 scanning files to index&#xff0c;需要去设置内存&#xff1a; 操作如下&#xff1a;

在Mac上安装Windows应用程序的简便方法:CrossOver for Mac

对于许多Mac用户来说&#xff0c;有时候他们可能需要使用一些只有在Windows上才能找到的应用程序。以前&#xff0c;解决这个问题的方法是通过安装Windows虚拟机或使用双系统来在Mac上运行Windows应用程序。但这些方法需要额外的硬件资源和时间来配置&#xff0c;并且可能会导致…

MEME成风,为何比特币生态无法复刻以太坊生态的多样玩法?

铭文市场火了之后&#xff0c;很多人对 BTC L2 投入了过多的期许&#xff0c;认为 BTC 2 层会像以太坊 layer2 一样辉煌&#xff1f; 然而事实是&#xff0c;比特币生态的「成功」可能很长时间会停滞在「资产发行」叙事阶段&#xff0c;要复刻以太坊的生态多样玩法&#xff0c…

栈和队列OJ题

有效的括号 OJ链接 思路 要注意进行顺序匹配的时候&#xff0c;要让右括号和栈顶元素匹配&#xff0c;匹配了一个以后就要让栈顶元素出栈&#xff01;&#xff01; 在顺序匹配时&#xff0c;要用 *s ] && top ! [ 像这样的不等号&#xff0c;而不能用&#xff0c;因为…

12.4_黑马MybatisPlus笔记(下)

目录 11 12 thinking&#xff1a;关于Mybatis Plus中BaseMapper和IService&#xff1f; 13 ​编辑 thinking&#xff1a;CollUtil.isNotEmpty? 14 thinking&#xff1a;Collection、Collections、Collector、Collectors&#xff1f; thinking&#xff1a;groupBy&#…

前端打包环境配置步骤

获取node安装包并解压 获取node安装包 wget https://npmmirror.com/mirrors/node/v16.14.0/node-v16.14.0-linux-x64.tar.xz 解压 tar -xvf node-v16.14.0-linux-x64.tar.xz 创建软链接 sudo ln -s 此文件夹的绝对路径/bin/node /usr/local/bin/node&#xff0c;具体执行如下…

彻底搞懂零拷贝技术( DMA、PageCache)

DMA 直接内存访问&#xff08;Direct Memory Access&#xff09; 什么是DMA&#xff1f; 在进行数据传输的时候&#xff0c;数据搬运的工作全部交给 DMA 控制器&#xff0c;而 CPU 不再参与&#xff0c;可以去干别的事情。 传统I/O 在没有 DMA 技术前&#xff0c;全程数据…

AIGC之Image2Video(一)| Animate Anyone:从静态图像生成动态视频,可将任意图像角色动画化

近日&#xff0c;阿里发布了Animate Anyone&#xff0c;只需一张人物照片&#xff0c;结合骨骼动画&#xff0c;就能生成人体动画视频。 项目地址&#xff1a;https://humanaigc.github.io/animate-anyone/ 论文地址&#xff1a;https://arxiv.org/pdf/2311.17117.pdf Github…

YOLOv8 YoLov8l 模型输出及水果识别

&#x1f368; 本文为[&#x1f517;365天深度学习训练营学习记录博客 &#x1f366; 参考文章&#xff1a;365天深度学习训练营 &#x1f356; 原作者&#xff1a;[K同学啊 | 接辅导、项目定制] &#x1f680; 文章来源&#xff1a;[K同学的学习圈子](https://www.yuque.com/m…

Android app性能优化指南

Android应用性能优化指南 提高应用程序的性能以实现更流畅的用户体验和更高的可见度。 性能在任何应用程序的成功中发挥着重要的作用。为用户提供流畅无缝的体验应该是开发人员的重点。 应用程序大小 在用户开始使用我们的应用程序之前&#xff0c;他们需要下载应用程序并将…

TypeScript入门实战笔记 -- 开篇 为什么要选择 TypeScript ?

typescript 在线编辑器http://typescript.p2hp.com/play?#code/JYOwLgpgTgZghgYwgAgJIFUDO1Uhge2QG8AoZc5YAEwC5kQBXAWwCNoBuMikOJiOzGCigA5pwrI4ANzhg4UAPwChozgF8SmmAxAIwwfCGRYcefAAoADlHyXMdDNii4CASmJdyCQ5nwAbCAA6P3wRKxs7ABpkAHJrW0wY1xINEhNnM3MiSlpkAEZonj46GIBrROQ1…

C/C++之输入输出

文章目录 一.C语言的输入输出1.printfi. 输出整数ii. 浮点数iii.字符 & 字符串 2.scanfi.整数ii.浮点数iii. 字符 & 字符串 3.特殊用法i. * 的应用ii. %n 的应用iii. %[] 的应用 二.C中的输入输出1.couti. 缓冲区&#xff08;buffer&#xff09;ii. cout之格式化输出 2…

区块链optimism主网节点搭建

文章目录 官方参考资料编译环境搭建编译Optimism Monorepo编译op-geth 执行下载数据快照生成op-geth和op-node通信密钥op-geth执行脚本 op-node执行脚本 启动日志op-gethop-node 本文是按照官方参考资料基于源码的方式成功搭建optimism主网节点。 官方参考资料 源码&#xff1…

【设计模式-4.4】行为型——模板方法模式

说明&#xff1a;本文介绍设计模式中行为型设计模式中的&#xff0c;模板方法模式&#xff1b; 生存 模版方法模式是行为型设计模式&#xff0c;关注于对象的行为。在《秒懂设计模式》&#xff08;刘韬 著&#xff09;中举了一个例子&#xff0c;例如哺乳动物的生存技能&…