当前位置:首页 > Java技术 > 完美世界JAVA笔试题

完美世界JAVA笔试题

2022年08月04日 20:54:24Java技术2

年会游戏

时间限制:C/C++语言 1000MS;其他语言 3000MS
内存限制:C/C++语言 65536KB;其他语言 589824KB

题目描述:

公司年会设计了一个游戏,抽到号码的员工可以到舞台的桌子上带回总重量不超过固定重量的若干个奖品,桌子上的奖品数量是有限的,每个奖品上都标明了它的重量和价值,对于一个奖品它只能选择带走或者不带走,不能将它掰成几份带走部分,请设计实现一个算法计算当奖品数量、奖品价值、能带走的总重量取不同值时,员工能带走的最大价值是多少。

输入

输入奖品数量,每个奖品的价值和重量,能够带走的奖品重量限度

输入第一行:奖品数量

输入第二行:每个奖品的价值,通过空格分割

输入第三行:每个奖品的重量,通过空格分割

输入第四行:能够带走的奖品总重量限度

输出

员工能够带走的最大价值

 

样例输入

5

5000 4000 3000 500 200

5 4 6 3 1

10

样例输出

9200


package test;

import java.util.Scanner;

public class Demo {
    private static Scanner sc;
	private static int count = 0;
	private static int[] worths;
	private static int[] weights;

	public static void main(String[] args)  {
		sc = new Scanner(System.in);
                count = sc.nextInt();
                sc.nextLine();
		String worth = sc.nextLine();
		worths = stringArrayintArray(worth.trim().split(" "));
		String weight = sc.nextLine();
		weights = stringArrayintArray(weight.trim().split(" "));
		int remainWeight = sc.nextInt();
		System.out.print(getMostWorth(remainWeight, 0));
	}
	
	
	public static int getMostWorth(int remainWeight, int index){
		if(index < count){
			if(remainWeight>=weights[index]){
				int yes = worths[index] + getMostWorth(remainWeight-weights[index], index+1);
				int no = getMostWorth(remainWeight, index+1);
				return yes>no?yes:no;
			}else{
				return getMostWorth(remainWeight, index+1);
			}
		}
		return 0;
	}
	
	
	public static int[] stringArrayintArray(String[] strArray){
		int[] intArray = new int[strArray.length];
		for(int i=0;i<strArray.length;i++){
			intArray[i] = Integer.parseInt(strArray[i]);
		}
		return intArray;
	}

}

题目分析:典型的0-1背包问题(笔试时由于时间紧张,根本没时间看,好可惜,后面补上)问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。

爸爸去哪儿

时间限制:C/C++语言 1000MS;其他语言 3000MS
内存限制:C/C++语言 65536KB;其他语言 589824KB

题目描述:

小鱼儿和安吉一起去参加爸爸去哪儿,村长交给他们一项任务,是用老乡的水果去给爸爸兑换一个礼物,要求水果和礼物等价,不能多也不能少。假设老乡有n种水果,每种水果的数量不限,每种水果的价值不同。请帮小鱼儿和安吉计算出他们最少要和老乡要几个水果。如果无法兑换返回-1.

举例:

1.有3种水果,价值分别是5,2,3。礼物的价值是20.用4个5元的水果正好兑换,其他的兑换方法都要更多的水果,所以返回4

2.有两种水果,价值分别是5,3,礼物的价值是2.无法正好兑换,所以返回-1

输入

输入数据是一个数组和一个整数代表礼物价值

输出

对于每个测试实例,要求输出最少水果数

样例输入

5,2,3

20

样例输出

4

package test2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Test1 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String value = br.readLine().trim();
			String targetValue = br.readLine().trim();
			String[] str_values = value.split(" ");
			int[] values = parseIntArray(str_values);
			NormalQuikSort(values,0,values.length-1);
			System.out.print(getCount(values,Integer.parseInt(targetValue),0, 0));
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	private static int getCount(int[] values, int targetValue,int currentCount,int index) {
		int num = targetValue/values[index];
		int remain = targetValue%values[index];
		if(num > 0)
		{	int ret = -1;		
			while(num > 0 )
			{
				if(remain == 0)
					return num+currentCount;
				ret = getCount(values,(targetValue-values[index]*num),currentCount+num,index+1);
				if( ret != -1)
					return ret;
				num--;
			}
		}else if(num <= 0 && (index+1) < values.length)
			return getCount(values,targetValue,currentCount,index+1);
		return -1;
	}
	private static int[] parseIntArray(String[] str_values) {
		// TODO Auto-generated method stub
		int[] arr = new int[str_values.length];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(str_values[i]);
		}
		return arr;
	}
	public static void Swap(int[] arr,int m,int n)
	{
		int temp;
		temp = arr[m];
		arr[m]=arr[n];
		arr[n]=temp;
	}
	public static void NormalQuikSort(int[] arr,int p,int q)
	{
		if (p < q) {
			int i = Partition(arr,p,q);
			NormalQuikSort(arr,p,i-1);
			NormalQuikSort(arr,i+1,q);
		}
	}
	public static int Partition(int[] arr,int p,int q)
	{
		int x = arr[p];
		int i = p;
		for (int j = p+1; j <= q; j++) {
			if (arr[j] > x ) {
				i = i+1;
				Swap(arr,i,j);
			}
		}
		Swap(arr,p,i);
		return i;
	}	
}


思路:使用快排为将水果价值排序,从最大价值算起,通过递归,在满足一定的总价值情况下,保证所换得的水果数目最少

作者:u010996775
来源链接:https://blog.csdn.net/u010996775/article/details/68379072

版权声明:
1、JavaClub(https://www.javaclub.cn)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。


本文链接:https://www.javaclub.cn/java/17408.html

分享给朋友:

“完美世界JAVA笔试题” 的相关文章

什么是软件实施?软件实施前景几何?软件实施的面试题有那些?

事情是这样的,由于自己目前还没有对象,就想着在兰州找一份还不错的工作,于是投了一家在我的家乡还算不错的公司,对方却说有可能是软件实施岗位,于是趁机了解了一下, 什么是软件实施? 软件实施掌握的基础知识有哪些? 软件实施前景几何?...

并发编程|说完AQS,面试官为何不淡定了?

并发编程|说完AQS,面试官为何不淡定了?

你能说下什么是AQS AQS是队列同步器AbstractQueueSynchronizer的简写,它是用来构建锁和其他同步组件的基础框架,它定义了一个全局的int 型的state变量,通过内置的FIFO(先进先出)队列来完成资源竞...

Java集合---面试题

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考察的深度很深。这题经常出现在高级或中高级面试中,甚至会要求你实现...

JAVA面试精选【Java基础第一部分】

  这个系列面试题主要目的是帮助你拿轻松到offer,同时还能开个好价钱。只要能够搞明白这个系列的绝大多数题目,在面试过程中,你就能轻轻松松的把面试官给忽悠了。对于那些正打算找工作JAVA软件开发工作的童鞋们来说,当你看到这份题目的时候,你应该感动很幸运,因为,只要你把题目中...

蚂蚁金服测试开发的面试题【杭州多测师】【杭州多测师_王sir】

1、抽象类和Java当中的接口有什么区别 2、Java中空指针是怎么引起的? 3、Java的多线程是怎么实现的? 4、Java用的哪些框架? 5、Java中截图或者录屏用代码怎么实现的 6、自己有没有开发过什么小工具 7、自己搭建过什么关于Java的...

Java探针-Java Agent技术-阿里面试题

Java探针-Java Agent技术-阿里面试题

 Java探针参考:Java探针技术在应用安全领域的新突破     最近面试阿里,面试官先是问我类加载的流程,然后问了个问题,能否在加载类的时候,对字节码进行修改 我懵逼了,答曰不知道,面试官说可以的,使用Java探针技术,能够实现...

IOS面试题详解(二)..

IOS面试题详解(二)..

上一篇文章列出了共32道IOS面试题: http://www.cnblogs.com/fkdd/archive/2012/03/13/2394724.html 下面从第一题开始解答: 题目:1.Object-c的类可以多重继承么?可以实现多个接口么?Category是什么?...

面试官问:为什么你们项目要用消息队列?

面试官问:为什么你们项目要用消息队列?

同学们应该都会被问到过这个问题:你的系统为什么要用消息队列? 大家普遍回答:我入职前,系统里面就已经用了消息队列啊,然后就用了。 其实面试官就是想看看你有没有深入了解过消息队列,有没有认真思考过消息队列解决了哪些问题? ​ 这篇文章主要带大家解决以...

4.面试必问:线程池的原理是什么?

4.面试必问:线程池的原理是什么?

虽然线程给我们程序带来了更高的执行效率,但是线程不是创建的越多越好,那么线程创建的过多,会带来什么问题呢? 线程之间频繁的进行上下文切换,增加系统的负载 线程的创建和销毁本身也是非常消耗资源的 所以为了解决上面这个问题,让...

一文高效图解二叉树面试题

一文高效图解二叉树面试题

点击蓝色“码出高效面试的程序媛”关注我, 了解更多技术流行面试题 二叉树,搜索二叉树,是算法面试的必面题。聊聊面试点: 一、树 & 二叉树 树的组成为节点和边,节点用来储存元素。节点组成为根节点、父节点和子节点。 如图:树深 leng...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。