jjzjj

java - 从比预定义距离更近的数组中查找更高的值

coder 2024-03-14 原文

我有数组 a1 到 an，每个数组包含 m 个元素。我有另一个对称 n X n 矩阵 b 包含数组之间的距离。我想从每个数组 x1 到 xn 中选择一个元素，限制为以下约束。 (a1 是一个数组，x1 是取自 a1 的单个值)

  1. 对于每个 xi(原来是 aiu)和 xj(原来是 ajv>)，其中 i 与 j 不同，u 和 v 是原始数组索引，我们有 |u - v| <=>ij.
  2. x1 到 xn 的总和是所有可能的集合中的最大值。

一个例子

a1 = [1, 2, 3, 8, -1, -1, 0, -1]
a2 = [1, 2, 4, 0, -1, 1, 10, 11]

b  = |0, 2|
     |2, 0|

选择的值是 x1 = 8 和 x2 = 4。可以注意到我们没有从第二个中选择 10 或 11，因为最接近的可能它们中任何一个的值都仅为 0。

现在，当我只有两个数组时，我可以在 O(n2) 时间内在 java 中执行以下操作，我猜，并找到最大总和，即 12 在这种情况下。如何为 2 个以上的阵列实现更好的解决方案？

int[][] a = new int[][]{{1, 2, 3, 8, -1, -1, 1, -1}, {1, 2, 4, 0, -1, 1, 10, 11}};
int[][] b = new int[][]{{0, 2}, {2, 0}};
int maxVal = Integer.MIN_VALUE;
for (int i = 0; i < a[0].length; i++) {
    for (int j = Math.max(i - b[0][1], 0); j < Math.min(a[1].length, i + b[0][1]); j++) {
        maxVal = Math.max(maxVal, a[0][i] + a[1][j]);
    }
}
System.out.println("The max val: "+maxVal);

最佳答案

您不能在这里使用动态规划，因为没有最佳子结构:b_1n 条目可能会破坏从 x_1 到 x_{n-1} 的非常有值(value)的路径。所以通常很难避免指数时间。然而，对于一组合理限制选择的 b_ij，有一个简单的回溯方法应该具有合理的性能:

  1. 在每一步中，都会从一些 a_i 中选择一个值，但尚未从其他 a_i 中选择一个值。 (选择的数组不需要是列表的前缀，甚至不需要是连续的。)
  2. 如果对每个数组都做出了选择，则返回(从这个递归调用中)获得的分数。
  3. 考虑，对于每对所选数组和剩余数组，考虑到前者选择的距离限制，后者可供选择的索引区间。
  4. 将每个剩余数组的这些区间相交。如果任何路口为空，则拒绝这组建议的选择并回溯。
  5. 否则，选择具有最小 可用选项集的剩余数组。将每个选择添加到建议选择集中并递归。返回找到的最佳分数和为获得它所做的选择(如果有)，或者拒绝并回溯。

识别最受约束的数组对性能至关重要:它构成了一种模糊信念传播的形式，有效地修剪了与先前选择所必需的当前选择不兼容的 future 选择。根据您期望的输入类型，根据可实现的分数进行进一步的优先级排序/修剪可能有值(value)。

我的 35 行 Python 实现，给定一个 10x10 的小整数随机矩阵和一个常量 2 的 b_ij，在几秒钟内运行。 b_ij=3(每对数组最多允许 10 个值中的 7 个值!)花了大约一分钟。

关于java - 从比预定义距离更近的数组中查找更高的值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47815432/

预定javasubsection的arraysalgorithm

有关java - 从比预定义距离更近的数组中查找更高的值的更多相关文章

  1. ruby - Facter::Util::Uptime:Module 的未定义方法 get_uptime (NoMethodError) - 2

    我正在尝试设置一个puppet节点，但ruby​​gems似乎不正常。如果我通过它自己的二进制文件(/usr/lib/ruby/gems/1.8/gems/facter-1.5.8/bin/facter)在cli上运行facter，它工作正常，但如果我通过由ruby​​gems(/usr/bin/facter)安装的二进制文件，它抛出:/usr/lib/ruby/1.8/facter/uptime.rb:11:undefinedmethod`get_uptime'forFacter::Util::Uptime:Module(NoMethodError)from/usr/lib/ruby

  2. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  3. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  4. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  5. ruby-on-rails - Rails 3.2.1 中 ActionMailer 中的未定义方法 'default_content_type=' - 2

    我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他，以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时，出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer

  6. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  7. ruby-on-rails - form_for 中不在模型中的自定义字段 - 2

    我想向我的Controller传递一个参数，它是一个简单的复选框，但我不知道如何在模型的form_for中引入它，这是我的观点:{:id=>'go_finance'}do|f|%>Transferirde:para:Entrada:"input",:placeholder=>"Quantofoiganho?"%>Saída:"output",:placeholder=>"Quantofoigasto?"%>Nota:我想做一个额外的复选框，但我该怎么做，模型中没有一个对象，而是一个要检查的对象，以便在Controller中创建一个ifelse，如果没有检查，请帮助我，非常感谢,谢谢

  8. ruby - 主要 :Object when running build from sublime 的未定义方法 `require_relative' - 2

    我已经从我的命令行中获得了一切，所以我可以运行rubymyfile并且它可以正常工作。但是当我尝试从sublime中运行它时，我得到了undefinedmethod`require_relative'formain:Object有人知道我的sublime设置中缺少什么吗？我正在使用OSX并安装了rvm。 最佳答案 或者，您可以只使用“require”，它应该可以正常工作。我认为“require_relative”仅适用于ruby​​1.9+ 关于ruby-主要:Objectwhenrun

  9. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  10. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

随机推荐