私はこの問題に悩まされ、誰かが私を助けることができるかどうか疑問に思っていました： x軸{n_1、x_2、... x_n}にn個の家があります。 x軸上の場所は、家と場所の間の距離の最小合計を与えます。中央の位置の動的プログラミング
これはもちろん些細なことですが、O（n）時にそれを実行できる必要があり、動的アルゴリズムに固執しています。
編集：明らかに、DPアルゴリズムである必要はありませんでした。私が言ったように、混乱のために申し訳ありません、と応答に感謝します。
私は中央値の発見が合理的にうまくいくことを知っていますが、私は動的計画法を合理的によく知っていますが、私はDPとして合理的に解釈できる中央値発見アルゴリズムは知らない。
xがソートされていて、正解がわからない場合は、DP-ishのサブ問題として、指定されたインデックスの右と左の部分和を計算することができました。最適解は、右部分和と左部分和の合計を最小にします。
もちろん、私は「Yを使ってXを解決する」という問題を強く嫌う。特にYが実際には合わないときはそうだ。 "Xを解くと、Yを使うことを検討したいかもしれない"という問題は、はるかに良い形の問題です。
この問題は、特にDPを使用して解決するとは言いませんが、解決したいということを強く示唆しています。私はおそらくちょうど別の方法でそれを行うでしょう。私の考えを再確認していただきありがとうございます。 – NominSim
この問題を解決すると、{x i}の中央値が得られます。
メジアンを見つけるためのよく知られた線形時間アルゴリズムがあります。たとえば、Wikipediaを参照してください。
ええ、正解は答えではなく、可能な答えの1つですが、私は信用を得るために動的アルゴリズムを必要としていると信じています。私は空白です。 – NominSim
@GordonSimpson：単純な方程式を設定し、それが機能するかどうかを調べることをお勧めします。そうでない場合は、ここに投稿してください。あなたは、質問をする人が最初に自分の試みを示すとき、私たちがそれを愛していることを知っています。 –
中央値は本当に答えですか？私は平均が答えだと思ったでしょう。 {1,2,9}を考慮する。中央値からの距離の合計は、（1-2）+（2-2）+（9-2）= 6である。平均からの距離の合計は（1-4）+（2-4）+（9-4）= 0です。 （定義上は常にゼロに等しい）おそらく私は真剣に質問を誤解している。 – emory
私はあなたの質問が意味をなさないと思います...あなたがどこにいても（家の間の）どこにいても、あなたは他のすべての家にあなたの距離を加えます - それは同じ番号ですあなたは... – Randy
@Randy：そうではありません。 '{1,3,5}'を考えてみましょう。あなたの議論によって、 '2'は問題を解決するでしょうが、それはしません（' 3'が良いです）。 – NPE
はい - ありがとう、これは実際には計算の中心的な質問です。 – Randy