我进行了在线编码测试,问题描述如下。我无法完成问题,但确实对如何提出潜在解决方案发表了一些意见。我想知道解决这个问题的最佳方法。我遇到的主要问题是将给定的输入拆分为字符串,并找到合适的集合将其放入。以下是问题。
您想向您的朋友发送包含不同物品的包裹。
您放入包装中的每件物品都具有诸如索引号,重量和成本之类的参数。
包装有重量限制。
您的目标是确定要放入包装中的物品,以使总重量小于或等于包装限制,并且总成本尽可能大。
如果有多个相同价格的包裹,您最好发送重量较轻的包裹。
这是背包问题的一个变体。
输入:
您的程序应从标准输入读取行。每行包含一个包装可以承受的重量(在冒号之前)和需要选择的物品清单。每件物品都用括号括起来,第一个数字是物品的索引号,第二个数字是重量,第三个数字是成本。
任何包裹可承受的最大重量为<= 100.
您最多可能需要选择15种东西。
任何东西的最大重量和最大成本是<= 100.
输出:
对于每组事物,生成一个放入包装中的事物列表(它们的索引号以逗号分隔)。如果没有任何物品适合包装,请打印连字符(-).
测试1
输入81 : (1,53.38,$45) (2,88.62,$98) (3,78.48,$3) (4,72.30,$76) (5,30.18,$9) (6,46.34,$48)
预期输出4
测试2
Test Input 75 : (1,85.31,$29) (2,14.55,$74) (3,3.98,$16) (4,26.24,$55) (5,63.69,$52) (6,76.25,$75) (7,60.02,$74) (8,93.18,$35) (9,89.95,$78)
预期输出2,7
参考方案
您最多可能需要选择15种东西。因此您可以组合2 ^ 15 = 32,768。这样你就可以
检查每个组合,找出哪个组合符合要求。
例子:有3(1,2,3)件事。
然后您可以选择:(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)。
现在需要查找符合要求的组合。
这是解决方案:
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
String res[] = s.replaceAll("[^0-9.]+",";").split(";");
double target = Integer.parseInt(res[0]);
int n = (res.length-1) / 3;
int[] Index = new int[20];
double[] P = new double[20];
double[] W = new double[20];
int jj = 0;
for(int i = 1; i < res.length; i +=3){
Index[jj] = Integer.parseInt(res[i]);
W[jj] = Double.parseDouble(res[i+1]);
P[jj++] = Double.parseDouble(res[i+2]);
}
double result = 0;
int track = 0;
double resSum = 0;
for(int i =0; i< (1<<n); i++){
double sum = 0;
double weight = 0;
for(int j=0; j < n; j++){
if(((1<<j)&i) > 0){
sum+= P[j];
weight+=W[j];
}
}
if(weight <= target){
if(sum > resSum){
result = weight;
track = i;
resSum = sum;
}else if(sum == resSum && weight < result){
result = weight;
track = i;
}
}
}
jj = 0;
for(int i = 0; i < n; i++){
if(((1<<i)&track) > 0){
if(jj > 0){
System.out.print(",");
}
jj = 1;
System.out.print(Index[i]);
}
}
if(track == 0){
System.out.println("-");
}else {
System.out.println();
}
}
Java Double Object与其他Number类型对象的初始化 - java在Double object documentation中,它只有两个构造函数,一个构造函数使用一个双精度值,另一个构造函数使用一个字符串值。但是,我只是发现,如果我们使用其他Number类型的对象对其进行初始化,它也将起作用。例如,以下代码将起作用:Integer i = Integer.valueOf(10); Double d1 = new Doubl…
Java中的“ <<”运算符 - java最喜欢的语句来自Java的Character类:(1 << Character.PARAGRAPH_SEPARATOR)) >> type PARAGRAPH_SEPARATOR是字节,type是整数。这句话中的操作员,他们做什么?如何以及在哪里可以使用这些运算符?这是oracles java.lang.Character文档。该类中…
Java:正则表达式模式匹配器是否有大小限制? - java我的模式类似于OR:“word1 | word2 | word3”我大约有800个字。可能有问题吗? 参考方案 您仅受记忆和理智的限制。 :)
Java:线程池如何将线程映射到可运行对象 - java试图绕过Java并发问题,并且很难理解线程池,线程以及它们正在执行的可运行“任务”之间的关系。如果我创建一个有10个线程的线程池,那么我是否必须将相同的任务传递给池中的每个线程,或者池化的线程实际上只是与任务无关的“工人无人机”可用于执行任何任务?无论哪种方式,Executor / ExecutorService如何将正确的任务分配给正确的线程? 参考方案 …
JAVA:字节码和二进制有什么区别? - javajava字节代码(已编译的语言,也称为目标代码)与机器代码(当前计算机的本机代码)之间有什么区别?我读过一些书,他们将字节码称为二进制指令,但我不知道为什么。 参考方案 字节码是独立于平台的,在Windows中运行的编译器编译的字节码仍将在linux / unix / mac中运行。机器代码是特定于平台的,如果在Windows x86中编译,则它将仅在Win…