Java实现 蓝桥杯 算法提高 01背包
2023-09-14 08:58:17 时间
算法提高 01背包
时间限制:1.0s 内存限制:256.0MB
问题描述
给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
输入格式
输入的第一行包含两个整数n, m,分别表示物品的个数和背包能装重量。
以后N行每行两个数Wi和Vi,表示物品的重量和价值
输出格式
输出1行,包含一个整数,表示最大价值。
样例输入
3 5
2 3
3 5
4 7
样例输出
8
数据规模和约定
1<=N<=200,M<=5000.
import java.util.Scanner;
public class beibao {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int n = sc.nextInt();
int m=sc.nextInt();
int [] w = new int [n+1];
int [] v = new int [n+1];
for (int i = 1; i < n+1; i++) {
w[i]=sc.nextInt();
v[i]=sc.nextInt();
}
sc.close();
int [] [] dp = new int [n+1][m+1];
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=m; j++) {
if(j-w[i]>=0){
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
else{
dp[i][j]=dp[i-1][j];
}
}
}
System.out.println(dp[n][m]);
}
}
相关文章
- java helloworld源代码_Java Hello World源代码剖析
- Contest1620 – 2020-2021-2学期《Java Web 系统开发》:java基础:字符串
- java 实现 按位异或_Java 按位异或的性质及其妙用
- java locale 中国_Java描述语言、国家和地理的类——Locale
- java 异步调用接口_Java接口异步调用[通俗易懂]
- java public interface_Java 接口interface的基础[通俗易懂]
- java axis_Java 使用Axis实现WebService实例
- uint32 java_关于Java的int和C的uint32之间的转换
- java notifyall_Java Thread notifyAll()方法[通俗易懂]
- Java算法大全_java贪心算法几个经典例子
- java 递归方法卡住_递归算法怎么理解
- Java算法面试题
- 从java到JavaScript(2):对比Java/Go/Swift/Rust看Dart
- 一种求离散数学传递闭包的算法java实现详解编程语言
- java 实现的Boyer-Moore(BM)算法详解编程语言
- Java数据结构学习笔记之三Java数据结构与算法之队列(Queue)实现详解编程语言
- 技巧Linux环境下提高Java编译效率的技巧(linux下java编译)
- 服务器快速搭建Linux Java服务器,实现互联网应用(linux搭建java)
- 在Linux环境下轻松搭建Java开发环境(linux下搭建java)
- Linux环境中如何顺利执行Java程序?(linux下执行java)
- Java实现MySQL数据插入(java插入mysql)
- 实现高并发:Java利用Redis秒杀成功(java秒杀redis)
- 使用Java连接SQL Server数据库,轻松实现数据交互(java连sqlserver)
- 基于Linux操作系统上实现 Java 编程(linux r java)
- Oracle数据库中运行Java程序的简易指南(oracle中写java)
- 利用Redis锁实现Java程序并发控制(redis锁java实现)
- JAVA算法起步之插入排序实例
- javascript中实现兼容JAVA的hashCode算法代码分享