jjzjj

javascript - 理解餐 table 最佳座位算法的问题

coder 2024-05-16 原文

我正在通读一个问题并试图解决这个问题。

You've invited N people over for dinner. Let's say 4.

You have a circular dinner table and you wish to seat everyone around it. Unfortunately, not all of your friends are friends with each other, but you'd like to seat everyone optimally so that as many people as possible are seated next to people they consider friends and not enemies.

You've charted everyone's friendships and hatreds in a matrix of size NxN and represented friendships with the integer 1, hatreds with -1, and sheer indifference with 0.

[[ 0, 1, 1, 1, 1],    ← yes you like all your friends
 [-1, 0, 1,-1, 0],
 [-1, 1, 0, 1, 0],
 [ 1, 1, 1, 0,-1],
 [ 1, 0, 0,-1, 0]]

问题:

-> Write a Javascript method that computes an optimal seating arrangement as an Array, e.g. [0,4,2,1,3], for a given input matrix. (assuming indexes 0 and N-1 are seated adjacently). What is the time complexity for the solution? Add thoughts on possible optimizations.

我试过手动解决这个问题，但是我不明白给定输入矩阵的问题示例 [0,4,2,1,3]。

有人可以启发我吗？

他/她是怎么想出 [0,4,2,1,3] 的？

谢谢，非常感谢您的宝贵时间。

最佳答案

How did he/she come up with [0,4,2,1,3]?

该排列肯定不是示例输入的正确答案(参见下面的推理)，所以我认为 Emma上面的评论是正确的:问题陈述只是展示了“作为阵列的座位安排”应该是什么样子一般，而不是具体展示最佳座位示例输入的安排。

至于为什么我说 [0,4,2,1,3] 肯定不是您给出的示例的正确答案。 . .我不完全理解我们如何决定一种排列是否优于另一种排列，但很明显 [0,4,1,2,3] 无论如何都更好。对于 [0,4,2,1,3] 和 [0,4,1,2,3]，第一个人(0)喜欢两个邻居；第二个人(4)对两个邻居都是中立的；第三和第五个人(前者为 2 和 3，后者为 1 和 3)各喜欢一个邻居，对另一个保持中立。两种排列之间的唯一区别是，在 [0,4,2,1,3] 中，第四个人 (1) 对一个邻居保持中立并且不喜欢另一个，而在 [0, 4,1,2,3]，第四个人 (2) 对一个邻居保持中立，喜欢另一个。所以后者显然更胜一筹，无论我们认为增加喜欢更重要还是减少不喜欢更重要。

关于javascript - 理解餐 table 最佳座位算法的问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54508726/

javascript座位sectionblockquote中立algorithmdata-structures

有关javascript - 理解餐 table 最佳座位算法的问题的更多相关文章

  1. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

    很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

  2. ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2

    我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

  3. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  4. ruby - 通过 rvm 升级 ruby​​gems 的问题 - 2

    尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub

  5. ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2

    我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search

  6. ruby - Fast-stemmer 安装问题 - 2

    由于fast-stemmer的问题，我很难安装我想要的任何ruby​​gem。我把我得到的错误放在下面。Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingfast-stemmer:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcreatingMakefilemake"DESTDIR="cleanmake"DESTDIR=

  7. ruby - 安装 Ruby 时遇到问题(无法下载资源 "readline--patch") - 2

    当我尝试安装Ruby时遇到此错误。我试过查看this和this但无济于事➜~brewinstallrubyWarning:YouareusingOSX10.12.Wedonotprovidesupportforthispre-releaseversion.Youmayencounterbuildfailuresorotherbreakages.Pleasecreatepull-requestsinsteadoffilingissues.==>Installingdependenciesforruby:readline,libyaml,makedepend==>Installingrub

  8. ruby-on-rails - Prawn PDF : I need to generate nested tables - 2

    我需要一个表，其中行实际上是2行表，一个嵌套表是..我怎样才能在Prawn中做到这一点？也许我需要延期..但哪一个？ 最佳答案 现在支持子表:Prawn::Document.generate("subtable.pdf")do|pdf|subtable=pdf.make_table([["sub"],["table"]])pdf.table([[subtable,"original"]])end 关于ruby-on-rails-PrawnPDF:Ineedtogeneratenested

  9. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  10. ruby-on-rails - 简单的 Ruby on Rails 问题——如何将评论附加到用户和文章？ - 2

    我意识到这可能是一个非常基本的问题，但我现在已经花了几天时间回过头来解决这个问题，但出于某种原因，Google就是没有帮助我。(我认为部分问题在于我是一个初学者，我不知道该问什么......)我也看过O'Reilly的RubyCookbook和RailsAPI，但我仍然停留在这个问题上.我找到了一些关于多态关系的信息，但它似乎不是我需要的(尽管如果我错了请告诉我)。我正在尝试调整MichaelHartl'stutorial创建一个包含用户、文章和评论的博客应用程序(不使用脚手架)。我希望评论既属于用户又属于文章。我的主要问题是:我不知道如何将当前文章的ID放入评论Controller。

随机推荐