Java实现 蓝桥杯VIP 算法训练 装箱问题
2023-09-14 08:58:17 时间
题目描述
有一个箱子容量为V(正整数0≤V≤20000),同时有n个物品(0<n≤30,每个物品有一个体积(正整数)。
要求nn个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
输入输出格式
输入格式:
1个整数,表示箱子容量
1个整数,表示有n个物品
接下来n行,分别表示这n个物品的各自体积
输出格式:
1个整数,表示箱子剩余空间。
输入输出样例
输入样例#1:
24
6
8
3
12
7
9
7
输出样例#1:
0
这里先介绍最经典的动态规划
下面还有一个简化版的
import java.util.Scanner;
public class zhuangxiangwenti {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int v = sc.nextInt();
int n = sc.nextInt();
int [] num = new int [n+1];
for (int i = 1; i < num.length; i++) {
num[i]=sc.nextInt();
}
int [] [] dp = new int[n+1][v+1];
int min = Integer.MAX_VALUE;
for (int i = 1; i < n+1; i++) {
for (int j = 1; j <v+1; j++) {
if(j>=num[i]){
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-num[i]]+num[i]);
}
else{
dp[i][j]=dp[i-1][j];
}
}
min = Math.min(min, v-dp[i][v]);
}
System.out.println(min);
}
}
import java.util.Scanner;
public class zhuangxiangwenti2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int w = sc.nextInt();
int n = sc.nextInt();
int[] ff = new int[n];
for (int i = 0; i < ff.length; i++) {
ff[i] = sc.nextInt();
}
int[] t = new int[w + 1];
for (int i = 0; i < n; i++) {
for (int j = w; j >= 0; j--) {
if (j >= ff[i]) {
t[j] = Math.max(t[j], t[j - ff[i]] + ff[i]);
}
}
}
System.out.println(w - t[w]);
}
}
相关文章
- Java爱心代码_java怎么敲入代码
- java queue toarray_Java PriorityBlockingQueue toArray()用法及代码示例
- java线程池的面试题_献给准备面试的你,Java线程and线程池面试题小结「建议收藏」
- java map 二维数组_Java二维数组实现简单Map
- java数组的声明_Java数组定义常用方法[通俗易懂]
- Java中级面试题及答案整理「建议收藏」
- 选择排序-Java「建议收藏」
- Java编程语言简单常用的输入输出格式
- java冒泡排序经典代码_Java 8大经典排序算法(含源代码),必须收藏!
- MySQL字段类型如何转为java_Java JDBC中,MySQL字段类型到JAVA类型的转换
- java 随机数算法_Java随机数算法原理与实现方法实例详解
- java的栈内存和堆内存_Java本地方法栈
- java softreference_Java引用总结–StrongReference、SoftReference、WeakReference、PhantomReference…[通俗易懂]
- Java字符串转集合_java集合转数组
- Java截取字符串方法_java通过split截取字符串
- java创建线程池的几种方式_Java中的线程池
- Java方法重载_java入门方法的使用
- 让你亲眼看见java对象内存大小(基于64位操作系统)
- Java学习笔记之八JavaBean中布尔类型使用注意事项详解编程语言
- java中static关键字详解编程语言
- 注册MySQL,让你的Java技能更上一层楼(java注册mysql)
- 代码Linux下编写Java代码的指南(linux编写java)
- Java编程操作Oracle数据库(java操作oracle)
- Java轻松使用Redis实现数据高效存储(java使用redis)
- 版本配置Linux系统的默认Java版本(linux默认java)
- 键值解决Java中Redis键值对过期问题(redisjava过期)
- 实现使用Redis与Java实现过期数据清理(redisjava过期)
- 时间Java程序中Redis配置缓存过期时间(redisjava过期)
- 国内首本系统讲解Java异步编程的书籍-java异步编程实战
- java单例模式使用详解