7

要素の配列M、すべての数値、負または正またはゼロがあるとします。

Nこれらの要素の合計がN可能な限り最小の正の数になるように、配列から要素を選択するアルゴリズムを提案できる人はいますか?

たとえば、次の配列を使用します。

-1000,-700,-400,-200,-100,-50,10,100,300,600,800,1200

ここで、合計が可能な限り最小の正の数になるように、任意の 5 つの要素を選択する必要があります。

4

6 に答える 6

0

これは Haskell で最適化されていないものですが、(私のアイデアの多くと同様に) おそらくさらに最適化され、より適切に最適化される可能性があります。次のようになります。

  1. 配列をソートします（昇順と降順の両方を試してみると興味深い結果が得られました）
  2. BN = 配列の最初の N 要素
  3. B (i)、i > N = 最良の候補。ここで、(整数を仮定して) 両方とも 1 未満の場合、候補は合計の絶対値によって比較されます。両方とも 1 以上の場合は、それらの合計。1 つの候補のみが 0 より大きい場合、その候補が選択されます。候補の合計が 1 の場合、その候補を回答として返します。候補は:
      B (i-1), B (i-1)[2,3,4..N] ++ 配列 [i], B (i-1)[1,3,4..N] ++ 配列 [i]...B (i-1)[1,2..N-1] ++ 配列 [i]
      B (i-2)[2,3,4..N] ++ 配列[i], B (i-2)[1,3,4..N] ++ 配列 [i]...B (i-2)[1,2..N-1] ++ 配列 [i] ]
      ...
      B (N)[2,3,4..N] ++ 配列 [i], B (N)[1,3,4..N] ++ 配列 [i]...B ( N)[1,2..N-1] ++ 配列 [i]

数値が負 (昇順ソートの場合) または正 (降順ソートの場合) である配列の部分については、ステップ 3 を計算なしですぐに実行できることに注意してください。

出力：

*Main> least 5 "desc" [-1000,-700,-400,-200,-100,-50,10,100,300,600,800,1200]
(10,[-1000,600,300,100,10])
(0.02 secs, 1106836 bytes)

*Main> least 5 "asc" [-1000,-700,-400,-200,-100,-50,10,100,300,600,800,1200]
(50,[300,100,-200,-100,-50])
(0.02 secs, 1097492 bytes)

*Main> main -- 10000 random numbers ranging from -100000 to 100000
(1,[-106,4,-40,74,69])
(1.77 secs, 108964888 bytes)

コード：

import Data.Map (fromList, insert, (!))
import Data.List (minimumBy,tails,sort)
import Control.Monad.Random hiding (fromList)

array = [-1000,-700,-400,-200,-100,-50,10,100,300,600,800,1200]

least n rev arr = comb (fromList listStart) [fst (last listStart) + 1..m]
 where
  m = length arr
  r = if rev == "asc" then False else True
  sorted = (if r then reverse else id) (sort arr)
  listStart = if null lStart 
                 then [(n,(sum $ take n sorted,take n sorted))] 
                 else lStart
  lStart = zip [n..] 
         . takeWhile (all (if r then (>0) else (<0)) . snd) 
         . foldr (\a b -> let c = take n (drop a sorted) in (sum c,c) : b) [] 
         $ [0..]
  s = fromList (zip [1..] sorted)
  comb list [] = list ! m
  comb list (i:is)
    | fst (list ! (i-1)) == 1 = list ! (i-1)
    | otherwise              = comb updatedMap is 
   where updatedMap = insert i bestCandidate list 
         bestCandidate = comb' (list!(i - 1)) [i - 1,i - 2..n] where
           comb' best []     = best
           comb' best (j:js)
             | fst best == 1 = best
             | otherwise     =    
                 let s' = map (\x -> (sum x,x))
                        . (take n . map (take (n - 1)) . tails . cycle) 
                        $ snd (list!j)
                     t = s!i
                     candidate = minimumBy compare' (map (add t) s')
                 in comb' (minimumBy compare' [candidate,best]) js
  add x y@(a,b) = (x + a,x:b)
  compare' a@(a',_) b@(b',_) 
    | a' < 1    = if b' < 1 then compare (abs a') (abs b') else GT
    | otherwise = if b' < 1 then LT else compare a' b'

rnd :: (RandomGen g) => Rand g Int
rnd = getRandomR (-100000,100000)

main = do
  values <- evalRandIO (sequence (replicate (10000) rnd))
  putStrLn (show $ least 5 "desc" values)
于 2013-06-28T16:57:18.307 に答える
0

最初の配列をすでにショートさせてください。そうしないと、ショートしていなくても機能すると思います..
N -> 配列の長さ
M -> 要素が必要です。
R[] -> Answer
TEMP[] -> 計算
用 minSum -> minSum
A[] -> 初期入力

上記の変数はすべてグローバルに定義されています

int find(int A[],int start,int left)
{
    if(left=0)
    {
        //sum elements in TEMP[] and save it as curSum
        if(curSum<minSum)
        {
        minSum=curSum;
        //assign elements from TEMP[] to R[] (i.e. our answer)      
        }
    }

    for(i=start;i<=(N-left);i++)
    {
        if(left==M)
            curSum=0;
        TEMP[left-1]=A[i];
        find(A[],i+1,left-1);
    }
}

// 急いで作成したので、エラーが発生している可能性があります..

ideone の作業ソリューション: http://ideone.com/YN8PeW

于 2013-06-27T19:12:21.440 に答える
0

Kadaneのアルゴリズムがうまくいくと思いますが、それは最大の合計のためですが、最小の合計を見つけるためにも実装しましたが、今はコードを見つけることができません。

于 2013-06-27T17:18:21.840 に答える
0

可能な限り最善の解決策を見つけたい場合は、単純にブルートフォースを使用できます。考えられるすべての数字の組み合わせを試してください。

この非常に迅速で汚いアルゴリズムのようなもの:

public List<Integer> findLeastPositivSum(List<Integer> numbers) {
    List<Integer> result;
    Integer resultSum;
    List<Integer> subresult, subresult2, subresult3, subresult4, subresult5;
    for (int i = 0; i < numbers.size() - 4; i++) {
        subresult = new ArrayList<Integer>();
        subresult.add(numbers.get(i));
        for (int j = i + 1; j < numbers.size() - 3; j++) {
            subresult2 = new ArrayList<Integer>(subresult);
            subresult2.add(j);
            for (int k = j + 1; k < numbers.size() - 2; k++) {
                subresult3 = new ArrayList<Integer>(subresult2);
                subresult3.add(k);
                for (int l = k + 1; l < numbers.size() - 1; l++) {
                    subresult4 = new ArrayList<Integer>(subresult3);
                    subresult4.add(k);
                    for (int m = l + 1; m < numbers.size(); m++) {
                        subresult5 = new ArrayList<Integer>(subresult4);
                        subresult5.add(k);
                        Integer subresultSum = sum(subresult5);
                        if (subresultSum > 0) {
                            if (result == null || resultSum > subresultSum) {
                                result = subresult;
                            }
                        }
                    }
                }
            }
        }
    }
    return result;
}

public Integer sum(List<Integer> list) {
    Integer result = 0;
    for (Integer integer : list) {
        result += integer;
    }
    return result;
}

これは非常に高速で汚れたアルゴリズムであり、よりエレガントに実行できます。再帰を使用するなど、よりクリーンなアルゴリズムを提供できます。

さらに最適化することもできます。たとえば、最初のステップとして入力リストから同様の番号を削除できます。

于 2013-06-27T19:06:11.433 に答える