| 查看: 1912 | 回复: 7 | ||
[求助]
【求助】一个关于顺序调度的问题
|
|
假设有一个球在横轴的原点，给定n个可正可负的数字，其代表球在横坐标的走向及距离，正为向右走，负为向左走，每个数字只能走一次。每一次走 动都记录下球离原点的距离D1,D2,...,Dn（距离是非负的）。想找到一种方法，根据给定的数字对球的走向进行控制，使得D1,D2,...Dn之和最小。 例如：有三个数字，（-3，-1，6），选择顺序为（-1，-3，6），这样距离之和为1+4+2=7最短，而顺序（-1，6，-3）的距离之和为1+5+2 = 8； 我的想法是在选取球的走向顺序时，每次都使球尽量靠近原点，就如同上面例子的（-1，-3，6），第一次选取1，使得离原点最近，然后再选取-3，使得距离为4（如果选取6的话则为5），最后选取6。这是一种贪心法，不知道这个方法是不是能得到问题的最优解。 希望有大神能够帮忙看看我的这种方法在数字个数较多的情况下能不能得到最优解，如果能的话，如何证明这个结论。如果不能的话，有没有其他的方法，或者说这类问题有没有相关学科的书籍推荐（小弟非数学专业，不太清楚这类问题属于数学的哪个分支，有点无从下手，所以在这里发帖求助） |
回复此楼» 猜你喜欢
有多少人是今天查系统知道结果的？
已经有17人回复
-
国自然面上复盘~欢迎讨论
已经有6人回复
-
售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急
已经有4人回复
-
售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急
已经有4人回复
-
基金不中，共勉
已经有5人回复
-
看板上这么多中的，有点像50人群里49个人都是骗子的那种感觉……
已经有3人回复
-
我不理解！
已经有23人回复
-
2026年的国家社科基金项目通讯评审的新规则与新动向、新挑战
已经有10人回复
-
系统查不到
已经有10人回复
-
怎么查啊
已经有5人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 基团的优先保护顺序问题
已经有6人回复
- MS6.0-for-linux在REHL下安装的问题
已经有21人回复
- 测量材料的光吸收谱时，光路顺序问题
已经有6人回复
- 有关高效液相自身对照法中样品和1%对照品的进样顺序问题
已经有16人回复
- 关于Troque提交任务需要用qrun才能运行的讨论
已经有16人回复
- 求助文章第一作者和第二作者顺序的修改问题
已经有10人回复
- 有关液相出峰顺序的问题
已经有12人回复
- torque + maui 的设置问题
已经有14人回复
- 关于java多线程啊~
已经有4人回复
- 合成中加料顺序的问题
已经有4人回复
- 【求助】气相色谱出峰顺序问题，急急急
已经有14人回复
- 【求助】热处理与冷加工的顺序问题
已经有16人回复
pippi6
铁杆木虫 (著名写手)
工程和科学数值计算咨询
- 数学EPI: 6
- 应助: 413 (硕士)
- 贵宾: 0.002
- 金币: 7116.5
- 散金: 15
- 红花: 63
- 帖子: 1639
- 在线: 798.9小时
- 虫号: 2469437
- 注册: 2013-05-14
- 专业: 计算数学与科学工程计算
2楼2013-07-09 05:17:40
pippi6
铁杆木虫 (著名写手)
工程和科学数值计算咨询
- 数学EPI: 6
- 应助: 413 (硕士)
- 贵宾: 0.002
- 金币: 7116.5
- 散金: 15
- 红花: 63
- 帖子: 1639
- 在线: 798.9小时
- 虫号: 2469437
- 注册: 2013-05-14
- 专业: 计算数学与科学工程计算
3楼2013-07-09 05:29:21
4楼2013-07-09 10:35:12
5楼2013-07-09 10:45:13
pippi6
铁杆木虫 (著名写手)
工程和科学数值计算咨询
- 数学EPI: 6
- 应助: 413 (硕士)
- 贵宾: 0.002
- 金币: 7116.5
- 散金: 15
- 红花: 63
- 帖子: 1639
- 在线: 798.9小时
- 虫号: 2469437
- 注册: 2013-05-14
- 专业: 计算数学与科学工程计算
6楼2013-07-09 11:02:15
7楼2013-07-09 11:10:39
8楼2013-07-09 13:20:39
投票:
