问平等地把食物分给穷人！
EN

Code Golf用户

提问于 2014-12-05 06:27:56

回答 1查看 652关注 0票数 8

问题

经历了一次可怕的预演事故后，你作为斯克鲁奇McDuck重生了一天。为了最大限度地利用这种情况，你决定把食物送给穷人。因为你也是数学家，所以你把食物存储在向量v(1,2,3)中。

你想给每个家庭大致相同的食物。为了简单起见，每个家庭都有n成员。其任务是编写代码，将向量v拆分为长度为n的行，其中每一行具有相同数量的“食物”。

平等由标准差来衡量；每行的和(每个家庭收到的食物)与平均值有多大的不同。

输入

输入应该是整数n和向量v，v的长度不必被n整除；如果是这样，则为零。

示例

v = (4, 9, 3, 6, 19, 6, 9, 20, 9, 12, 19, 13, 7, 15)
n = 3

应该回来

 4     6    19
 9     9    13
 3    20     7
 6     9    15
19    12     0

每一行的和为29,31,30,30,31，因此对于n = 2，标准偏差为0.748331。

输出

代码应该输出标准偏差。您也可以打印矩阵，但这不是必需的。

评分

胜利者的判断不是根据最短的代码，而是根据标准偏差之和，给定测试向量和n = 2、3和23。例如：

Score = your_func(2, foodvec) + your_func(3, foodvec) + your_func(23, foodvec)

使用下面的向量测试http://pastebin.com/ybAYGHns和测试n=2,3,23。最后的分数是这三项测验的总和。这个载体有点大，因为史克鲁奇省下了很多食物。

optimized-output

code-challenge

arithmetic

回答 1

Code Golf用户

发布于 2014-12-06 12:14:21

Python3使用PyPy: 6.368014 + 0.701679 + 0.486916 = 7.556608

N=2

最优

有1000个数字，所以我们想把食物分发给500个家庭。如果食物载体被分类(food[1] >= food[2] >= ... >= food[500])，那么通过给第一个家庭food[1]和food[500]、第二个家庭food[2]和food[499]、第三个家庭food[3]和food[498]、.

我想出了一个很简单的证据。基本上，我扩展了std的产品，删除了每个食物分区中出现的术语，并证明了结果是最小的。如果有人想要更详细的解释，那就好好问我。

N> 2的

逼近我不认为，对于n> 2，有一种快速的寻找最优解的方法。我从一个启发式的解决方案开始。我把食物按顺序(降序)分发给到目前为止食物最低的家庭(只分配给那些收到的食物少于n件的家庭)。之后，我改进了解决方案，在一对家庭之间交换了1种食物。我使用食物最低的`N`家庭和到目前为止食物最多的`N`家庭。在所有可能的交换之后，我选择最佳的交换，并递归地调用本地搜索。 `N`值越大，std值越低(但运行时间也越长)。我使用了`N = 20`，当我找不到交换时，我再次尝试使用`N = 100`。PyPy在不到8分钟内完成了所有3个测试用例。

码

def findSmallestStd(food, n):
    food.sort(reverse=True)
    while len(food) % n:
        food.append(0)
    family_count = len(food) // n

    if n == 2: # optimal
        return list(zip(food[:len(food)//2], reversed(food[len(food)//2:])))
    else: # heuristic approach
        partition = [[] for _ in range(family_count)]
        for food_item in sorted(food, reverse=True):
            partition.sort(key=lambda f: sum(f) if len(f) < n else float('inf'))
            partition[0].append(food_item)
        return local_search(partition, calc_std(partition))

def local_search(partition, best_std, N = 20):
    # find indices with smallest and largest sum
    families1 = nsmallest(N, partition, key=sum)
    families2 = nlargest(N, partition, key=sum)
    best_improved_swap = None

    for family1, family2 in product(families1, families2):
        for index1, index2 in product(range(len(family1)), range(len(family2))):
            family1[index1], family2[index2] = family2[index2], family1[index1]
            std = calc_std(partition)
            if std < best_std:
                best_std = std
                best_improved_swap = (family1, family2, index1, index2)
            family1[index1], family2[index2] = family2[index2], family1[index1]

    if best_improved_swap:
        family1, family2, index1, index2 = best_improved_swap
        family1[index1], family2[index2] = family2[index2], family1[index1]
        partition = local_search(partition, best_std)
    elif N < 100:
        return local_search(partition, best_std, 100)
    return partition