7

假设我有一个M元素数组，所有数字，负数或正数或零。

谁能建议一种算法N从数组中选择元素，使这些N元素的总和是最小的可能正数？

以这个数组为例：

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

现在我必须选择任何 5 个元素，使它们的总和是可能的最小正数。

4

6 回答 6

7

公式

对于i = 1, ..., M：

  • 让a_i成为i您的候选人名单中的第 th 个数字
  • 让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}

您可以将“开箱即用”的整数程序求解器应用于此问题，以找到具有可控精度的最优解或次优解。

资源

于 2013-06-28T19:37:28.963 回答
0

我想Kadane 的算法可以解决问题，虽然它是为了最大和，但我也实现了它来找到最小和，虽然现在找不到代码。

于 2013-06-27T17:18:21.840 回答
0

让初始数组已经被短路，或者我想即使它没有被短路也会起作用..
N -> 数组 M 的长度
-> 元素 req。
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

于 2013-06-27T19:12:21.440 回答
0

这是 Haskell 中的一些次优，（就像我的许多想法一样）可能会得到进一步和更好的优化。它是这样的：

  1. 对数组进行排序（我通过尝试升序和降序得到了有趣的结果）
  2. BN = 数组的前 N ​​个元素
  3. B (i)，因为 i > N = 最佳候选；其中（假设整数）如果它们都小于 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

如果你想找到最好的解决方案，你可以简单地使用蛮力，即。尝试所有可能的数字组合。

像这种非常快速和肮脏的算法：

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 回答
-2

假设：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;
   }
 }
于 2013-06-27T17:26:58.493 回答