2

これはインタビューの質問です。与えられた整数配列から、その要素の合計の絶対値が最小になる部分列 (連続している必要はありません) を見つけます。

DPの問題のようです。

  • LetS1[i]は、a[i]その合計 > 0 およびabs (合計) が最小化される部分シーケンスです。

  • Letは、合計 < 0 でabs (合計) が最小化S2[i]される部分シーケンスです。a[i]

  • S1[i]if > 0 && < 0のすべてS1[j] + a[i]の最小値j < iS1[j] + a[i]a[i]

  • S2[i]if < 0 && > 0のすべてS2[j] + a[i]の最小値j < iS2[j] + a[i]a[i]

これS1[i]でS2[i]、すべてのインデックスについて、その要素の最小絶対値を持つサブシーケンスを簡単に見つけることができます。

それは理にかなっていますか？

4

3 に答える 3

2

空でないサブシーケンス間の最小絶対合計が必要だと仮定しています。(それ以外の場合、コメントに記載されているように、空のサブシーケンスの合計は 0 です。)

要素の順序は重要ではないため、質問は次のように尋ねます。要素の (複数) セットが与えられた場合、すべてのサブセット間の最小絶対合計はいくらですか。部分和問題がこの問題に還元されることは容易にわかります。サブセットの合計は NP 困難であるため、この問題も同様です。したがって、多項式時間アルゴリズムが間違っていることは間違いありません。それ以外の場合、P = NP。

実際、アルゴリズムの反例は入力シーケンス {-1, 2, -2} です。

部分和問題に対する標準的なアプローチを使用して、問題の疑似多項式時間アルゴリズムを取得できます。

于 2013-03-11T17:04:37.803 に答える
1

私はあなたの推論に従うことができればいいのですが、私は少し遅いです...また、あなたはDPを要求し、ここにHaskellが再びあります...しかし、これはあなたが言いたいことですか?

import Data.List (sortBy, subsequences)
import Data.Ord (comparing)

minValSub xs = 
  head $ sortBy (comparing snd) 
  $ map (\x -> (x, abs (sum x)) ) (filter (not . null) $ subsequences xs)


OUTPUT:
*Main> minValSub [1,2,3,-4,5]
([1,3,-4],0)
于 2013-03-11T18:35:51.017 に答える
1

空でない結果セットを想定しています。

整数のリストを S とします。その中で最小の絶対値を S[k] とします。S[K] == 0 の場合はそれを返します。それ以外の場合、目標は S[K] より小さい値を見つけることです。

SP（非負）とSNについて言及したように、整数を正と負の整数の2つのセットに分割します。ここで、SN 内の別の合計に S[K] 未満だけ近い SP 内の合計を見つけます。これは、SP と SN の要素を絶対値で別々に並べ替え、各リストに合計とヘッド ポインターを保持することで実行できます。詳細を入力できます。

これにより、S[K] よりも小さい値が得られる可能性があります。そうでない場合は、S[K] と報告されます。

例: S = {1, -4, 2, -8, 5, -7} k = 0, S[k] = 1

SP (ソート済み) = {1, 2, 5} SN (ソート済み) = {-4, -7, -8}

2 つの配列を同時にトラバースすると、いくつかの候補 {1,2} と {-4} が得られ、S[k] と同じ結果が得られます。しかし、{2,5} と {-7} は正味合計が 0 になる方が適切です。

于 2013-03-11T21:16:23.717 に答える