Подсчитать все подмножества массива, где наибольшее число является суммой оставшихся чисел

Question

Я боролся с уровнем 3 испытания Греплина. Для тех, кто не знаком, вот проблема:

вы должны найти все подмножества массива, где наибольшее число является суммой оставшихся чисел. Например, для ввода:

(1, 2, 3, 4, 6)

подмножества будут

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

Вот список номеров, которые вы должны запустите ваш код Пароль является количество подмножеств. В приведенном выше случае ответ будет 4.

3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99

Мне удалось зашифровать решение, которое строит все 4 миллиона плюс комбинации из 22 чисел, а затем протестировать их все, что даст мне правильный ответ. Проблема в том, что для этого требуется более 40 минут. При поиске в Интернете кажется, что несколько человек смогли написать алгоритм, чтобы получить ответ на этот вопрос менее чем за секунду. Может ли кто-нибудь объяснить в псевдокоде лучший способ решения этой проблемы, чем вычислительно дорогой метод грубой силы? Это сводит меня с ума!

Answer 1

Хитрость в том, что вам нужно только отслеживать количество способов сделать что-то. Так как числа отсортированы и положительны, это довольно легко. Вот эффективное решение. (Это занимает менее 0,03 с на моем ноутбуке.)

#! /usr/bin/python

numbers = [
    3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56,
    59, 61, 70, 73, 78, 81, 92, 95, 97, 99]

max_number = max(numbers)
counts = {0: 1}
answer = 0
for number in numbers:
    if number in counts:
        answer += counts[number]
    prev = [(s,c) for (s, c) in counts.iteritems()]
    for (s, c) in prev:
        val = s+number;
        if max_number < val:
            continue
        if val not in counts:
            counts[val] = c
        else:
            counts[val] += c
print answer

Answer 2

Мы знаем, что значения ненулевые и растут монотонно слева направо.

Идея состоит в том, чтобы перечислить возможные суммы (любой порядок, слева направо в порядке), а затем перечислить подмножества вслева от этого значения , потому что значения справа не могут участвовать (они могут сделать сумму слишком большой).Нам не нужно создавать экземпляр набора;так же, как мы рассматриваем каждое значение, посмотрим, как если влияет на сумму.Он может быть либо слишком большим (просто игнорировать это значение, не может быть в наборе), либо правильным (его последний член в наборе), либо слишком маленьким, и в этот момент он может или не может быть в наборе.

[Эта проблема заставила меня играть с Python впервые.Fun.]

Вот код Python;в соответствии с Cprofile.run это занимает 0,00772 секунды на моем ноутбуке P8700 2,54 ГГц.

values = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99]

def count():
   # sort(values) # force strictly increasing order
   last_value=-1
   duplicates=0
   totalsets=0
   for sum_value in values: # enumerate sum values
      if last_value==sum_value: duplicates+=1
      last_value=sum_value
      totalsets+=ways_to_sum(sum_value,0) # faster, uses monotonicity of values
   return totalsets-len(values)+duplicates

def ways_to_sum(sum,member_index):
   value=values[member_index]
   if sum<value:
      return 0
   if sum>value:
      return ways_to_sum(sum-value,member_index+1)+ways_to_sum(sum,member_index+1)
   return 1

Полученный счетчик равен 179. (Соответствует результату другого автора).

РЕДАКТИРОВАТЬ: way_to_sumможет быть частично реализован с использованием цикла хвостовой рекурсии:

def ways_to_sum(sum,member_index):
   c=0
   while True:
      value=values[member_index]
      if sum<value: return c
      if sum==value: return c+1
      member_index+=1
      c+=ways_to_sum(sum-value,member_index)

Это займет 0,005804 секунды для запуска: -} Тот же ответ.

Answer 3

Это работает менее чем за 5 мс (питон).Он использует вариант динамического программирования, называемый запоминанием рекурсии.Функция go вычисляет количество подмножеств первых элементов p+1, которые в сумме составляют target.Поскольку список отсортирован, достаточно вызвать функцию один раз для каждого элемента (как target) и суммировать результаты:

startTime = datetime.now()
li = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99]
memo = {}
def go(p, target):
    if (p, target) not in memo:
        if p == 0:
            if target == li[0]:
                memo[(p,target)] = 1
            else:
                memo[(p,target)] = 0
        else:
            c = 0       
            if li[p] == target: c = 1
            elif li[p] < target: c = go(p-1,target-li[p])
            c += go(p-1, target)
            memo[(p,target)] = c
    return memo[(p,target)]

ans = 0
for p in range(1, len(li)):
    ans += go(p-1, li[p])

print(ans)
print(datetime.now()-startTime)

Answer 4

Это работает

public class A {

  static int[] a = {3,4,9,14,15,19,28,37,47,50,54,56,59,61,70,73,78,81,92,95,97,99};

  public static void main(String[] args) {
    List<Integer> b = new ArrayList<Integer>();

    int count = 0;
    for (int i = 0; i < a.length; i++) {
        System.out.println(b);
        for (Integer t:b) {
        if(a[i]==t)
        {
        System.out.println(a[i]);
            count++;
            }
        }

        int size = b.size();
        for (int j = 0; j < size; j++) {
        if(b.get(j) + a[i] <=99)
            b.add(b.get(j) + a[i]);
        }
            b.add(a[i]);
    }

    System.out.println(count);

  }
}

псевдокод (с пояснениями):

1. сохранить следующие переменные

   i.) «Количество» подмножеств до настоящего времени

   ii.) Массив b, содержащий суммы всех возможных подмножеств

   2. Выполните итерацию по массиву (скажем, а). для каждого элемента a [i]

   i.) Пройти массив b и подсчитать количество вхождений a [i]. добавьте это к 'count'

   ii.) Пройти массив b и для каждого элемента b [j] .add (a [i] + b [j]) к b, потому что это возможная сумма подмножеств. (если a [i] + b [j]> max элемент в a, вы можете игнорировать его добавление)

   iii.) Добавить [i] к b.

3. У нас есть счет:)

Answer 5

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

Вместо того, чтобы выполнять итерацию по входному массиву и искать суммы, соответствующие каждому значению, гораздо эффективнее рассчитать все возможные СООТВЕТСТВУЮЩИЕ суммы только один раз, а затем посмотреть, какие из этих сумм появятся в исходном входном массиве. («Соответствующая» сумма - любая сумма подмножества <= максимальное значение в массиве.) </p>

Второй подход выполняется примерно в 6 раз быстрее - обычно миллисекунды, а не центсекунды - просто потому, что он вызывает рекурсивную функцию поиска суммы примерно в 1/6 раз!

Код для этого подхода и полное объяснение можно найти в этом репозитории github (он написан на PHP, потому что это было то, к чему призывал человек, который дал мне этот вызов):

https://github.com/misterrobinson/greplinsubsets

Answer 6

public class Solution {

   public static void main(String arg[]) {
    int[] array = { 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61,
        70, 73, 78, 81, 92, 95, 97, 99 };
    int N = array.length;
    System.out.println(N);
    int count = 0;
    for (int i = 1; i < 1 << N; i++) {
        int sum = 0;
        int max = 0;
        for (int j = 0; j < N; j++) {
        if (((i >> j) & 1) == 1) {
            sum += array[j];
            max = array[j];
        }
        }
        if (sum == 2 * max)
        count++;
    }
    System.out.println(count);
    }

    public static boolean isP(int N) {
    for (int i = 3; i <= (int) Math.sqrt(1.0 * N); i++) {
        if (N % i == 0) {
        System.out.println(i);
        // return false;
        }
    }
    return true;
    }
}

Надеюсь, это поможет, но не просто копируйте и вставляйте.

Answer 7

Я использовал класс генератора комбинации в Java, доступный здесь:

http://www.merriampark.com/comb.htm

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