arrays - 更好的 int 数组之间的总和

Question

我有这个数组

int arr = new int[] { 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 
978, 978, 978, 978, 978, 978, 696, 696, 696, 696, 696, 696, 696, 696, 696, 696, 696, 696, 
696, 696, 696, 696, 696, 696, 696, 696, 678, 678, 678, 678, 678, 678, 678, 678, 678, 678, 
446, 446, 446, 446, 446, 446, 446, 446, 446, 446 };

20 elements 978
20 elements 696
10 elements 678
10 elements 446

我需要找到 sum 的最佳组合，直到 6000。

狐狸示例：

978 + 978 + 978 + 978 + 696 + 696 + 696 = 6000

这是一个最佳组合。

找到最佳组合后，我需要删除求和的元素以再次找到最佳和。

在这种情况下，我的数组将是：

16 elements 978
17 elements 696
10 elements 678
10 elements 446

那么，下一个更好的总和将是：

 978 + 978 + 978 + 978 + 696 + 696 + 696 = 6000

然后：

978 + 978 + 978 + 978 + 696 + 696 + 696 = 6000

然后 ：

978 + 978 + 978 + 978 + 696 + 696 + 696 = 6000

在这一刻，我的数组是：

4 elements 978
8 elements 696
10 elements 678
10 elements 446

现在，我最好的总结是：

696 + 696 + 696 + 696 + 696 + 696 + 696 + 678 + 446 = 5996

还有我的数组：

4 elements 978
1 elements 696
9 elements 678
9 elements 446

嗯......我需要做总和，直到我的数组为空。

有什么建议吗？

可以在 js、c# 或 vb 中。

Answer 1

这是我对您的任务的单次迭代的解决方案。我会及时找到“最佳匹配”组合，O(m * n)其中m目标数（在您的情况下为 6000），n 是数组中剩余的元素总数（初始迭代中为 53）。我的解决方案的内存复杂度将是O(m)

我将一个辅助符号：

• parent[m + 1]- 存储用于形成特定总和的最后一个数字。如果总和尚未达到，则值为 -1
• maxm- 之间的最大数量arr
• list<int> chosen- 为特定迭代选择的数字
• best根据您的定义，最好的金额

这是我的解决方案的伪代码

parents[i] = { -1 if i != 0; -2 otherwise} // distinguish the empty sum
for (i = 0; i < n; i++)
  for (j = m + maxm; j > 0; j--)
    if parents[j] == -1 && j - arr[i] >= 0 && arr[i] != -1
       parents[j] = i

// choose the best; choose only numbers with parents[i] != -1
for i = 0; i < m + maxm; i++
   if parents[m + i] != -1
      best = m + i
      break
   else if parents[m - i] != -1
      best = m - i
      break
while best != 0 
   chosen.add(best - parents[best])
   best = parents[best]

编辑best根据您的定义添加计算。

Answer 2

.. 这是我在 C# 中的代码：

Dictionary ex = new Dictionary<Integer,Short>();

ex.Add(978, 20); // 20 elements 978
ex.Add(696, 20); // 20 elements 696
ex.Add(678, 10); // 10 elements 678
ex.Add(446, 10); // 10 elements 446

使用它更省时，而不是所有元素的数组，然后不是每次都计算总和，而是预先计算总和：

class Ex
{
    Dictionary<Integer,Short> ex;
    long sum;

    public Ex ()
    {
        ex = new Dictionary<Integer,Short>();
        sum = 0;
    }

    public void add (int number, short frequency)
    {
        ex.Add(number, frequency);
        sum += (number * frequency);
    }

    public void remove (int number)
    {
        sum -= (number * ex.Get(number));
        ex.Remove(number);
    }

    public void increment (int number, short frequency)
    {
        ex.Set(number, ex.Get(number)+frequency);
        sum += (number * frequency);
    }

    public void subtract (int number, short frequency)
    {
        ex.Set(number, ex.Get(number)-frequency);
        sum -= (number * frequency);
    }

    public long getSum ()
    {
        return sum;
    }
}

希望这可以帮助 ..

Answer 3

好的，我不记得我是如何偶然发现这个话题的，但我想我已经设法找到了一种快速算法来解决这个问题。至少对于给定的数据。我的解决方案是在 JS 中，我感觉更舒服。它可以在不到 7 毫秒的时间内解决，但我相信如果需要更快，它可以简单地转码为 Haskell 或 C。

好的，首先以免看到解决方案...

function getSum(arr,sum){
  function getCombinations(arr){
    var len = arr.length,
       subs = Array(Math.pow(2,len)).fill();
    return subs.map((_,i) => { var j = -1,
    	                           k = i,
                                 res = [];
                               while (++j < len ) {
                                 k & 1 && res.push(arr[j]);
                                 k = k >> 1;
                               }
                               return res;
                             }).slice(1);
  }
  function getPossibles(a,t){
    var fo = a[0],
    maxTry = Math.min(Math.floor(t/fo.n),fo.c);

    return a.length > 1 ? Array(maxTry).fill()
                                       .map((_,i) => ({n:fo.n, c:maxTry-i}))
                                       .reduce((p,c) => (p.push(...getPossibles(a.slice(1),t-c.n*c.c).map(e => a.length > 2 ? [c,...e]
                                                                                                                            : [c,e])),p),[])
                        : [{n:fo.n, c: maxTry}];
  }
  var  hash = arr.reduce((p,c) => (p[c] ? p[c]++ : p[c] = 1,p),{}),
   condense = Object.keys(hash)
                    .reverse()
                    .map(k => ({n: k, c:hash[k]}));
     combos = getCombinations(condense);
  possibles = combos.reduce((p,c) => (c.length > 1 ? p.push(...getPossibles(c,sum))
                                                   : p.push(getPossibles(c,sum)),p),[]);
  return possibles.filter(p => p.reduce((s,o) => s += o.n*o.c,0) === sum)
                  .map(e => e.reduce((p,c) => p.concat(Array(c.c).fill(c.n)),[]));
}

var arr = [978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 696, 696, 696, 696, 696, 696, 696, 696 ,696, 696, 696, 696, 696, 696, 696, 696, 696, 696, 696, 696, 678, 678, 678, 678, 678, 678, 678, 678, 678, 678, 446, 446, 446, 446, 446, 446, 446, 446, 446, 446],
 result = [],
     ps = 0,
     pe = 0;
ps = performance.now();
result = getSum(arr,6000);
pe = performance.now();
console.log(result);
console.log("Done in:", pe-ps);

我试图使代码尽可能明确。我将尝试在这里逐步解释。

我们有一个函数来解决这个问题getSum()，其中我们有两个实用函数，分别是getCombinations()和getPossibles()。

一旦我们收到我们的值数组（arr）和目标（sum），我们首先在下面建立一个哈希表hash，结果是这样的；

{ '446': 10, '678': 10, '696': 20, '978': 20 }

显然，通过告诉我们哪个数字存在多少次，我们可以得到数组的映射。

然后我将数组重新映射为更简单的对象形式并将其存储condense为

[ { n: '978', c: 20 },
  { n: '696', c: 20 },
  { n: '678', c: 10 },
  { n: '446', c: 10 } ]

此时我们需要得到这些对象的组合，以便以后解决所有的可能性。对于这个任务，我们使用了getCombinations()效用函数。结果如下；

[ [ { n: '978', c: 20 } ],
  [ { n: '696', c: 20 } ],
  [ { n: '978', c: 20 }, { n: '696', c: 20 } ],
  [ { n: '678', c: 10 } ],
  [ { n: '978', c: 20 }, { n: '678', c: 10 } ],
  [ { n: '696', c: 20 }, { n: '678', c: 10 } ],
  [ { n: '978', c: 20 }, { n: '696', c: 20 }, { n: '678', c: 10 } ],
  [ { n: '446', c: 10 } ],
  [ { n: '978', c: 20 }, { n: '446', c: 10 } ],
  [ { n: '696', c: 20 }, { n: '446', c: 10 } ],
  [ { n: '978', c: 20 }, { n: '696', c: 20 }, { n: '446', c: 10 } ],
  [ { n: '678', c: 10 }, { n: '446', c: 10 } ],
  [ { n: '978', c: 20 }, { n: '678', c: 10 }, { n: '446', c: 10 } ],
  [ { n: '696', c: 20 }, { n: '678', c: 10 }, { n: '446', c: 10 } ],
  [ { n: '978', c: 20 },
    { n: '696', c: 20 },
    { n: '678', c: 10 },
    { n: '446', c: 10 } ] ]

所以现在我们知道我们将尝试什么。但我们必须巧妙地尝试。我们知道目标总和是 6000，我们不应该允许过多的计算。棘手的部分来了。我们有getPossibles()实用函数，它将只返回计数（c属性）值总和小于 6000 的对象。好吧，我受到了我的Array.prototype.cartesian()工具的影响，它工作得很好。

OkgetPossibles()将获取一个对象数组（压缩数据），并为我们提供总和小于 6000 的集合的可能组合。例如，对于[ { n: '978', c: 20 }, { n: '696', c: 20 }, { n: '678', c: 10 } ]我们将收到的组合；

[ [ { n: '978', c: 5 }, { n: '696', c: 1 }, { n: '678', c: 0 } ],
  [ { n: '978', c: 4 }, { n: '696', c: 3 }, { n: '678', c: 0 } ],
  [ { n: '978', c: 4 }, { n: '696', c: 2 }, { n: '678', c: 1 } ],
  [ { n: '978', c: 4 }, { n: '696', c: 1 }, { n: '678', c: 2 } ],
  [ { n: '978', c: 3 }, { n: '696', c: 4 }, { n: '678', c: 0 } ],
  [ { n: '978', c: 3 }, { n: '696', c: 3 }, { n: '678', c: 1 } ],
  [ { n: '978', c: 3 }, { n: '696', c: 2 }, { n: '678', c: 2 } ],
  [ { n: '978', c: 3 }, { n: '696', c: 1 }, { n: '678', c: 3 } ],
  [ { n: '978', c: 2 }, { n: '696', c: 5 }, { n: '678', c: 0 } ],
  [ { n: '978', c: 2 }, { n: '696', c: 4 }, { n: '678', c: 1 } ],
  [ { n: '978', c: 2 }, { n: '696', c: 3 }, { n: '678', c: 2 } ],
  [ { n: '978', c: 2 }, { n: '696', c: 2 }, { n: '678', c: 3 } ],
  [ { n: '978', c: 2 }, { n: '696', c: 1 }, { n: '678', c: 4 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 7 }, { n: '678', c: 0 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 6 }, { n: '678', c: 1 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 5 }, { n: '678', c: 2 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 4 }, { n: '678', c: 3 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 3 }, { n: '678', c: 4 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 2 }, { n: '678', c: 5 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 1 }, { n: '678', c: 6 } ] ]

嗯……一旦你手头有这些数据，那么减少你所拥有的就是一件简单的事情。所以只有最后一行；

possibles = combos.reduce((p,c) => (c.length > 1 ? p.push(...getPossibles(c,sum))
                                                 : p.push(getPossibles(c,sum)),p),[]);
                  .filter(p => p.reduce((s,o) => s += o.n*o.c,0) === sum)
                  .map(e => e.reduce((p,c) => p.concat(Array(c.c).fill(c.n)),[]));

是我们如何在 JS 中在不到 7 毫秒的时间内获得解决方案。