Минимальная разница

Question

я сталкивался с этим вопросом на этом сайте, который называется codility, но я не могу понять, как его решить, буду признателен за помощь

Учитывая массив A из n целых чисел и последовательность S из n элементов 1 или -1, мы определяем значение:

Предположим, что сумма нулевых элементов равна нулю. Написать функцию

int min_abs_sum(int[] A);

, чем для данного массива A из n целых чисел из диапазона [-100..100] вычисляется минимально возможное значение val (A, S) (для любой последовательности S с элементами 1 или -1). Можно предположить, что n <= 20000 </strong>.

Например, данный массив: а = {1,5,2, -2}

ваша функция должна вернуть 0, поскольку для последовательности S = ​​(- 1,1, -1,1) значение val (A, S) = 0.

Вот две ссылки для некоторых людей, результат не показывает решения, но показывает сложность их алгоритмов, первая ссылка показывает сложность, с которой должна работать программа, а вторая медленнее.

1-я ссылка 100% оценки

2-я ссылка 86% отметок

Answer 1

Это плохо сформулированная версия проблемы с разделами. Вы собираетесь разбить массив A на 2 группы, максимально приближенные к равным. Тот, с большей суммой вы будете назначать +1 в массиве S, а другая группа получит -1. Выберите решение проблемы с разделом и настройте его, чтобы получить ответ на этот вопрос. На самом деле это вариант разбиения, который ищет наилучшее возможное значение, а не 2 равных набора.

РЕДАКТИРОВАТЬ вот код Python, основанный на статье, написанной @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), умноженное на 100/2. Я использовал список вместо массива, что означает, что некоторые вещи будут быстрее, а некоторые медленнее, чем в статье. Возможно, что мин достигается путем суммирования первой половины чисел и вычитания второй половины - или чего-то подобного, что требует больших промежуточных сумм. Я использую список, а не массив, но размер все еще ограничен. Извините, я не занимаюсь Java.

Answer 2

Это в основном работает для разделения a на две части с суммами абсолютных значений двух частей, максимально близкими к равным.

Затем вы хотите умножить эти элементы на 1 или -1, чтобы сделать один раздел полностью отрицательным, а другой - положительным. Делая это, вы суммируете их, чтобы получить окончательный ответ.

С алгоритмической точки зрения, я полагаю, что шаг разделения почти наверняка является NP-полностью (на ум приходят такие фразы, как «сумма подмножеств» и «проблема разбиения»). С точки зрения программирования это довольно просто - исчерпывающе тестируйте возможности, пока не получите лучший. Пока количество элементов мало (до десятка или около того [править: так как это O (2 ^N , вы, вероятно, можете увеличить его до где-то в диапазоне 30-40), это будет достаточно быстро.

Я полагаю, что он должен быть пропорционален O (N!), Поэтому, если массив становится вообще большим, время, потраченное на него, быстро станет неразумным. Поскольку вы делитесь только на два набора и порядок внутри наборов не имеет значения, это O (2 ^N ) вместо O (N!). Это растет не так быстро, как O (N!), Но все же достаточно быстро, чтобы сделать большие наборы неразумными для обработки.

Я должен добавить, однако, что Codility, похоже, специализируется на проблемах, которые изначально могут показаться NP-завершенными, но на самом деле это не так - если вы пропустили любую деталь в своем описании, проблема может быть значительно проще.

Редактировать: перечитывая его, проблема может заключаться в том, что I игнорирует важную деталь: ограниченный диапазон. Я не уверен, как вы используете его не по назначению, но я уверен, что это крайне важно для выработки эффективного решения. Мое непосредственное предположение состоит в том, что это основано на чем-то похожем на изменение сортировки на основе сравнения на сортировку (иначе называемую). Хотя я не продумал это до мелочей ...

Edit2: Делая небольшой взгляд (и получая подсказку от @Moron), ограниченный диапазон важен, и мои мысли о том, как оно превращается в решение, были в целом правильными. @ Морон был достаточно любезен, чтобы указать на запись в Википедии для проблемы подмножества сумм, но я не нашел это особенно хорошо написанным. Немного осмотревшись, я обнаружил бумагу из Корнелла с объяснением, которое я нашел немного чище / более понятным.

Answer 3

Следующее Java-решение получит 100% в Codility.Мое решение основано на разделе «Разделение с дубликатами элементов» в статье, связанной @Jerry Coffin, но я также включил несколько дополнительных оптимизаций.

import java.util.Arrays;

class Solution {

    public int solution ( int[] A ) {

        int n=A.length,r=0,c=1,sum=0,mid=0;

        // Add all numbers, replace them with their absolute value, and sort them
        for(int i=0;i<n;i++) {
          A[i]=Math.abs(A[i]);
          sum+=A[i];
        }
        Arrays.sort(A); // This minimizes the speed of growth of r in the loop below and allows us to count duplicates while scanning the array
        mid=sum/2; // If the number is odd the result is rounded down (the best possible solution is 1 instead of 0).

        // Find the subset of numbers whose sum is closest to half the total sum    
        boolean[] bs=new boolean[mid+101]; // We only need to check sets that are equal or less than half the sum of the numbers (to avoid having to check the sum in the inner loop I sacrifice 100 booleans since 100 is the maximum value allowed)
        bs[0]=true; // The set with zero elements always adds to 0
        for(int i=0;i<n;i++){
          if( A[i]==0 ) continue;
          // Count duplicate entries
          if(i<n-1 && A[i]==A[i+1] ){
            c++;
            continue;
          } 
          // Scan the subset sum result array from right to left and add A[i] c times to existing subset sums
          for (int j = r; j >= 0; j--)
            if(bs[j] ){
              int m= Math.min(mid, j+A[i]*c );
              for(int k= j+A[i];k<=m && !bs[k];k+=A[i] ) bs[k]=true; // To avoid duplicate work when dealing with multiples of previous numbers the loop stops if we find an entry has already been set.
            }
          r=Math.min(mid, r+A[i]*c); // New rightmost subset sum can be no more than the mid point
          while(!bs[r]) r--; // Scan back to rightmost subset sum
          if(r==mid) break; // Found an optimal solution; no need to continue
          c=1;
    }
    return sum-2*r; // The rightmost subset sum that does not go over half the sum is the best solution, compute the difference of the complementary subsets (r and sum-r).
  }

}

Answer 4

def min_abs_sum(A):
    A[:] = sorted([ abs(i) for i in A if i != 0 ], reverse=True)
    s = sum(A)
    h = s / 2
    r = find_balance_iter(h, A)
    return abs(2*(h-r) - s)

def find_balance_iter(v, A):
    r = v
    n = len(A)
    for i in xrange(n):
        if i and A[i] == A[i-1]:
            continue
        for j in xrange(n-i-1):
            vv = v - A[i]
            rr = vv
            AA = A[i+j+1:]
            while True:
                if vv == 0 or vv in AA:
                    return 0
                if vv < 0 or not AA:
                    rr = vv
                    break
                if vv < AA[-1]:
                    rr = min(vv-AA[-1], rr, key=compare)
                    break
                vv -= AA[0]
                AA[:] = AA[1:]
            r = min(r, rr, key=compare)
    return r

def compare(a):
    return (abs(a), a)

Answer 5

Это может работать быстро:

maxvalue = 100

def solve(data):
    def mark_sum(s):
        # wrap sum around maxvalue
        if s >= maxvalue:
            s -= maxvalue * 2
        elif sum < -maxvalue:
            s += maxvalue * 2
        # mark sum
        if s >= 0:
            s_new_pos[s] = True
        else:
            s_new_neg[s + maxvalue] = True

    s_old_pos = [False] * maxvalue  # marks for sums [0..99]
    s_old_neg = [False] * maxvalue  # marks for sums [-100..-1]
    s_old_pos[0] = True  # seed array with zero sum for zero elements
    for n in data:
        s_new_pos = [False] * maxvalue
        s_new_neg = [False] * maxvalue
        for i in range(maxvalue):   # mark new possible sums
            if s_old_pos[i]:
                mark_sum(i + n)
                mark_sum(i - n)
            if s_old_neg[i]:
                mark_sum(i - 100 + n)
                mark_sum(i - 100 - n)
        s_old_pos = s_new_pos
        s_old_neg = s_new_neg
    for i in range(maxvalue):
        if s_old_pos[i]:
            return i
        if s_old_neg[-1 - i]:
            return abs(-1 - i)
    raise AssertionError('my bad')

Нет необходимости проверять все возможные суммы (до 1000000).Они могут быть просто обернуты вокруг max_value.Это заменяет n на max_value во временной сложности.

Все еще не уверены в правильности: (

Answer 6

Таким образом, цель состоит в том, чтобы максимально приблизиться к 0.

Моя первая мысль состояла в том, чтобы отсортировать массив в порядке убывания, а затем выполнить итерацию по списку, выполнив что-то вроде этого:

int total = 0;
foreach(int i in a)
{
    total = Math.Min(Math.Abs(total - i), Math.Abs(total + i));
}

, что будет работать для a={1,5,2,-2} (всего будетследующие 5,4,2,0)

Но я не уверен, что это работает во всех случаях.Я посмотрю на это немного больше, чем посмотрим, есть ли случай, для которого он не работает.

РЕДАКТИРОВАТЬ:

Хорошо, я думаю, грубая сила будет работать?

    public static int MinArray(int[] array)
    {
        int val = int.MaxValue;

        for (int i = 0; i < Math.Pow(2, array.Length); i++)
        {
            val = Math.Min(CalcMin(array, i), val);
        }

        return val;
    }

    private static int CalcMin(int[] array, int negs)
    {
        int ret = 0;

        for (int i = 0; i < array.Length; i++)
        {
            int neg = 1;

            if (negs != 0)
            {
                neg = negs % 2 == 1 ? -1 : 1;
                negs >>= 1;
            }
            ret += array[i] * neg;
        }

        return Math.Abs(ret);
    }

Итак, я делаю каждую итерацию S (которая вычисляется путем взятия двоичного числа i в MinArray) и находим мин таким образом.

СНебольшая модификация, вы также можете получить правильное значение для S (если это требование. Если нет, то выполнение этого требования может принести вам несколько очков на собеседовании?)