平衡等大小的数组

如果我理解您的需求正确，一种快速而近似正确的解决方案是：

1. 对原始数组进行排序
2. 分配新数组大小为原始数组的一半。如果原始数组长度为奇数，则决定哪个新数组获取额外的元素。
3. 从左到右（或从右到左）遍历原始数组。将奇数索引元素放在一个新的数组中，将偶数索引元素放在另一个新的数组中。

关键是对原始数组进行排序，如果您的要求允许，在地方进行排序；否则，创建一个新的“原始”数组，其中包含实际原始数组的排序副本。

如果 N 相当大，且数字的分布相当均匀（例如没有向一端或另一端倾斜的大偏差），那么此解决方案将非常接近理想解决方案。

如果您真的需要平均值尽可能接近，即使数字存在较大偏差，我能想到的唯一方法是尝试每个排列并保留平均差最小的排列。

local function some_magic(V)
   assert(#V % 2 == 0 and #V > 0)
   table.sort(V)
   local S = {[-1] = math.huge, [0] = 0}
   for i = 1, #V do
      S[i] = S[i-1] + V[i]
   end
   local half_sum = math.floor(S[#V] / 2)
   local half_len = #V / 2
   local m = 2^math.ceil(math.log(half_len+1)/math.log(2))
   local P = {[0] = 0}
   for idx = #V, 1, -1 do
      local v, P2 = V[idx], {}
      for k in pairs(P) do
         if math.floor(k/m) + v + S[half_len - k%m - 1] <= half_sum then
            P2[k + v*m + 1] = idx
         end
      end
      for k, v in pairs(P2) do
         P[k] = P[k] or v
      end
   end
   local k = 0
   for next_k in pairs(P) do
      if next_k > k and next_k%m == half_len then
         k = next_k
      end
   end
   local A, B, prev_idx = {}, {}, 0
   repeat
      local idx = P[k]
      for i = prev_idx + 1, idx - 1 do
         table.insert(B, V[i])
      end
      table.insert(A, V[idx])
      prev_idx = idx
      k = k - V[idx]*m - 1
   until k == 0
   for i = prev_idx + 1, #V do
      table.insert(B, V[i])
   end
   return A, B
end

local values = {4, 4, 7, 8, 10, 15}
print('values: '..table.concat(values, ','))
local a, b = some_magic(values)
print('a: '..table.concat(a, ','))
print('b: '..table.concat(b, ','))

------------- Output: ------------
values: 4,4,7,8,10,15
a: 4,4,15
b: 7,8,10

local function some_magic(V)
   assert(#V % 2 == 0 and #V > 0)  -- 确保输入是偶数个正整数
   table.sort(V)  -- 排序
   local S = {[-1] = math.huge, [0] = 0}  -- S 列表用于保存 V 的前缀和
   for i = 1, #V do
      S[i] = S[i-1] + V[i]
   end
   local half_sum = math.floor(S[#V] / 2)  -- half_sum 是整个列表的一半之和
   local half_len = #V / 2  -- half_len 是整个列表的一半长度
   local m = 2^math.ceil(math.log(half_len+1)/math.log(2))  -- m 是一个 2 的幂，大于等于 half_len+1
   local P = {[0] = 0}  -- P 表示一个从 S 中选出的整数子集
   for idx = #V, 1, -1 do
      local v, P2 = V[idx], {}
      for k in pairs(P) do
         if math.floor(k/m) + v + S[half_len - k%m - 1] <= half_sum then  -- 迭代更新 P
            P2[k + v*m + 1] = idx
         end
      end
      for k, v in pairs(P2) do
         P[k] = P[k] or v
      end
   end
   local k = 0
   for next_k in pairs(P) do  -- 在 P 中找到恰好等于 half_len 的 k
      if next_k > k and next_k%m == half_len then
         k = next_k
      end
   end
   local A, B, prev_idx = {}, {}, 0
   repeat
      local idx = P[k]
      for i = prev_idx + 1, idx - 1 do  -- 将这个中间值的左边部分填充到列表 A 中，右边部分填充到 B 中
         table.insert(B, V[i])
      end
      table.insert(A, V[idx])
      prev_idx = idx
      k = k - V[idx]*m - 1
   until k == 0
   for i = prev_idx + 1, #V do
      table.insert(B, V[i])
   end
   return A, B
end

local values = {4, 4, 7, 8, 10, 15}  -- 原始列表
print('values: '..table.concat(values, ','))
local a, b = some_magic(values)  -- 把原始列表分为两个部分
print('a: '..table.concat(a, ','))
print('b: '..table.concat(b, ','))

------------- 输出: ------------
values: 4,4,7,8,10,15
a: 4,4,15
b: 7,8,10