Предположим, у меня есть массив из M элементов, все числа, отрицательные, положительные или нулевые.
Может ли кто-нибудь предложить алгоритм выбора N элементов из массива, чтобы сумма этих N элементов была наименьшим возможным положительным числом?
Возьмите этот массив, например:
-1000,-700,-400,-200,-100,-50,10,100,300,600,800,1200
Теперь мне нужно выбрать любые 5 элементов так, чтобы их сумма была наименьшим возможным положительным числом.
Для 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}
Вы можете применить к этой задаче целочисленный программный решатель «из коробки», чтобы найти оптимальное решение или субоптимальное решение с контролируемой точностью.
Если вы хотите найти наилучшее возможное решение, вы можете просто использовать грубую силу, т.е. попробуйте все возможные комбинации пяти чисел.
Что-то вроде этого очень быстрого и грязного алгоритма:
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;
}
Это действительно быстрый и грязный алгоритм, его можно сделать более элегантно. Я могу предоставить более чистый алгоритм, например. используя рекурсию.
Это также может быть дополнительно оптимизировано. Например. вы можете удалить похожие числа из списка ввода в качестве первого шага.
Пусть исходный массив уже закорочен, или я думаю, что это будет работать, даже если он не закорочен..
N -> Длина массива
M -> Требуется элемент.
R[] -> Ответ
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
Я полагаю, что алгоритм Кадане поможет, хотя он рассчитан на максимальную сумму но я также реализовал его, чтобы найти минимальную сумму, хотя сейчас не могу найти код.
Вот что-то неоптимальное в Haskell, которое (как и многие из моих идей), вероятно, можно было бы еще лучше оптимизировать. Это выглядит примерно так:
Обратите внимание, что для той части массива, где числа отрицательные (в случае сортировки по возрастанию) или положительные (в случае сортировки по убыванию), шаг 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)
Предположение: M - исходный массив
песудокод
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;
}
}
