Выберите комбинацию элементов из массива, сумма которых наименьшее возможное положительное число

Question

Предположим, у меня есть массив из M элементов, всех чисел, отрицательный или положительный или нулевой.

Может ли кто-нибудь предложить алгоритм для выбора элементов из массива N, так что сумма этих элементов N является наименьшим возможным положительным числом?

Возьмите этот массив, например:

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

Теперь я должен выбрать любые 5 элементов, таких, что их сумма является наименьшим возможным положительным числом.

Answer 1

Я полагаю, что Kadane’s Algorithm выполнит трюк, хотя это для максимальной суммы, но я также внедрил его, чтобы найти минимальную сумму, хотя не могу найти код прямо сейчас.

Answer 2

Предположение: М исходный массив

Pesudocode

S = sort(M); 
R = []; 
sum = 0; 
for(i=0, i < length(S); i++){ 
    sum = sum + S[i]; 
    if(sum < 1){ 
    R.push(S[i]); 
    }else{ 
    return R; 
    } 
} 

Answer 3

Если вы хотите, чтобы найти наилучшее решение, вы можете просто использовать грубую силу ИЭ. попробуйте все возможные комбинации номеров чисел.

Что-то вроде этого очень быстрый и грязный алгоритм:

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; 
} 

Это действительно быстрый и грязный алгоритм, это может быть сделано более элегантно. Я могу предоставить более чистый алгоритм, например. используя рекурсию.

Его также можно оптимизировать. Например. вы можете удалить аналогичные номера из списка ввода в качестве первого шага.

Answer 4

Пусть начальный массив замкнуть уже, или я предполагаю, что это будет работать, даже если оно не замкнуто ..
N -> Длина массива
M -> Элемент REQ.
R [] -> Ответ
ТЕМП [] -> Для расчетов
минисуммной -> минисуммной
А [] -> Начальный вход

Все вышеуказанные переменные определены глобально

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

Answer 5

В Haskell есть что-то неподходящее, которое (как и многие мои идеи), вероятно, может быть более совершенным и оптимизированным.Это идет что-то вроде этого:

1. Сортировка массива (я получил интересные результаты, пытаясь как восходящие и нисходящие)
2. BN = первые N элементов массива
3. B (I), при г> N = лучший кандидат; где (предполагая целые числа), если они меньше 1, кандидаты сравниваются по абсолютной величине их сумм; если они равны 1 или более, по их сумме; и если только один кандидат больше 0, то выбран этот кандидат. Если сумма кандидата равна 1, верните этот кандидат в качестве ответа. Кандидатами являются:
       B (i-1), B (i-1) [2,3,4..N] ++ массив [i], B (i-1) [1,3,4 ..N] ++ array [i] ... B (i-1) [1,2..N-1] ++ array [i]
       B (i-2) [2,3, 4..N] ++ array [i], B (i-2) [1,3,4..N] ++ [i] ... B (i-2) [1,2..N -1] ++ массив [I]
       ...
       В (Н) [2,3,4..N] ++ массив [I], В (Н) [1,3, 4..N] ++ array [i] ... B (N) [1,2..N-1] ++ array [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) 

Answer 6

Формулирование

Для i = 1, ..., M:

• Пусть a_i быть i й номер в списке кандидатов
• Пусть x_i обозначать, является ли i й номер включен в набор N выбранных номеров

Затем вы хотите, чтобы решить следующие задачи целочисленного программирования.

minimize: sum(a_i * x_i) 
with respect to: x_i 
subject to: 
    (1) sum(a_i * x_i) >= 0 
    (2) sum(x_i) = N 
    (3) x_i in {0, 1} 

Вы можете применить целую программу решатель «из коробки» к этой проблеме, чтобы найти оптимальное решение или неоптимальное решение с контролируемой точностью.

Ресурсы

• Integer programming
• Explanation of branch-and-bound integer program solver