最小差集 [英] Minimum set difference

问题描述

我碰到这个网站名为codility这个问题，但我真的不能弄清楚如何解决它，将AP preciate帮助

i came across this question on this website called codility, but i cant really figure out how to solve it, would appreciate the help

由于n个整数数组A，和n个元素的序列S 1或-1我们定义的值：

Given an array A of n integers, and the sequence S of n elements 1 or -1 we define the value:

假定的零元素的总和等于零。 写一个函数

Assume the sum of zero elements is equal zero. Write a function

int min_abs_sum(int[] A);

比给定的n个整数的从范围[-100..100]的数组A计算val的可能的最低值（A，S）（与元件1或为任何序列S -1）。你可以假设的 N'LT;。= 20000

例如给定的数组： A = {1,5,2，-2}

For example given array: a={1,5,2,-2}

你的函数应该返回0，因为对序列S =（ - 1,1，-1,1）的VAL（A，S）= 0

your function should return 0, since for sequence S=(-1,1,-1,1) the val(A,S)=0.

下面是两个链路有些民族造成的，它不显示出解决方案，但它确实表明了它们的算法的复杂性，所述第一连杆示出了在该程序应运行的复杂性，而第二个较慢。

Here are two links for some peoples result, it doesnt show the solution but it does show the complexity of their algorithms, the first link shows the complexity at which the program should run and the second one is slower.

第一环节100％马克

第二个环节86％的标记

推荐答案

这是措辞不当版的分区问题。您将数组A分成2组接近等于越好。在一个具有较大的总和，你会在S阵列中分配+1，另一组将获得-1。选择一个解决分区的问题，并调整它的答案回到这一个。实际上它是分区的变体，旨在相对于2个相等组可能的最佳值。

This is poorly worded version of the partition problem. You are going to split the array A into 2 groups as close to equal as possible. The one with the larger sum you'll be assigning +1 in the S array, and the other group will get -1. Pick a solution to the partition problem and adjust it to return an answer to this one. Actually it's the variant of partition that seeks the best possible value as opposed to 2 equal sets.

修改这里是基于@Jerry棺材挂纸一些Python code

EDIT here is some python code based on the paper linked by @Jerry Coffin

def min_abs_sum(A):
vals = []
for x in A:
    for v in vals:
        n = v+x
        if (abs(n)<=1000000) and (n not in vals): vals.append(n)
        n = v-x
        if (abs(n)<=1000000) and (n not in vals): vals.append(n)
    if (x not in vals): vals.append(x)
    if (-x not in vals): vals.append(-x)
return (min([abs(x) for x in vals]))

一百万价值的一半，20000（以A MAX数）乘以100/2。我用一个列表，而不是一个数组，这意味着有些东西会更快一些比他们做的纸要慢。可以设想，最小是通过对所述第一数目的一半，并减去下半场取得 - 或类似的东西，需要大中间和。我用一个列表，而不是一个数组，但尺寸仍然为界。对不起，我不这样做的Java。

The one million value is half of 20000 (max numbers in A) times 100/2. I've used a list instead of an array, which means some things will be faster and some slower than what they do in the paper. It is conceivable that the min is achieved by summing the first half of the numbers and subtracting the second half - or something like that which requires large intermediate sums. I'm using a list rather than an array, but the size is still bounded. Sorry, I don't do Java.

这篇关于最小差集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！