как вы можете найти длину самого длинного подмножества (множества мощности) с суммой, равной k, с наименьшей временной сложностью?

Учитывая массив целых чисел, я пытаюсь найти самое длинное подмножество (powerset) с суммой, равной k, используя возможную временную сложность аренды. например если inputArr= [1, 2, 8, 1, 1, 7] и k = 10, то на выходе должно быть 4, поскольку самое длинное подмножество с суммой, равной 10, равно [1, 1, 1, 7].

Редактировать: я мог забыть важную деталь; все элементы массива положительные и ненулевые.

Я использовал этот алгоритм, который нашел на geeksforgeeks: https://www.geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java/

Код работает нормально, но единственная проблема, которая у меня есть, это время выполнения. Я должен отправить это онлайн, и когда я отправляю его, выполнение прекращается из-за тайм-аута.

    int maxSubLength=0;
    for (int i = 1; i < (1<<n); i++)   //n is the length of inputArr
    {
        int sum=0, length=0;

        for (int j = 0; j < n; j++)
          if ((i & (1 << j)) > 0)
          {
                sum+=inputArr[j];
                length++;
                if (sum>k)
                   break;
          }  

        if (sum==k)
            maxSubLength=Math.max(maxSubLength, length);
    }

Есть ли более быстрый алгоритм? Пробовал рекурсивно - не помогло.


java algorithm subset powerset
person Jim    schedule 15.10.2019    source источник
comment
Не существует быстрого способа сгенерировать все подмножества большого набора, потому что набор размера n имеет 2ⁿ надмножества. Не могли бы вы опубликовать полный текст проблемы, которую вы пытаетесь решить, включая любые ограничения на размер набора и/или его значения?   -  person ruakh    schedule 15.10.2019
comment
@ruakh Возможно, я забыл важную деталь; все элементы массива положительные и ненулевые. Вот полный текст задачи: Дан массив положительных n ненулевых целых чисел, найти длину самого длинного подмножества целых чисел, сумма которых равна k. и 1‹=n‹=1000, 1‹=k‹=2000.... Для большого значения n приведенный выше код вызовет проблему переполнения. Но я позаботился об этом, используя BigInteger, я просто не хотел слишком усложнять этот вопрос.   -  person Jim    schedule 15.10.2019
comment
Другими словами, до какой временной сложности в большой нотации O вам нужно добраться?   -  person Josh W.    schedule 15.10.2019
comment
@ДжошВ. Я действительно не уверен. В задаче это не указано, и я понятия не имею, какова наилучшая временная сложность, в которой эта проблема может быть решена.   -  person Jim    schedule 15.10.2019
comment
Кажется, это сумма подмножества с дополнительным требованием найти максимально возможное подмножество, которое суммируется с заданным. Ее можно решить, слегка изменив алгоритм суммы подмножества, и его время выполнения, безусловно, лучше, чем вычисление всех подмножества.   -  person jrook    schedule 15.10.2019

Ответы (1)


arrow_upward
4
arrow_downward

Мы можем решить эту проблему с помощью динамического программирования в O(n*k) времени и O(k) пространстве. Код JavaScript:

function f(A, K){
  let m = new Array(K + 1).fill(0)
    
  for (let a of A){
    for (let k=K; k>=a; k--)
      if (m[k - a])
        m[k] = Math.max(m[k], 1 + m[k - a])

    m[a] = Math.max(m[a], 1)
  }
  
  return m[K]
}

var A = [1, 2, 8, 1, 1, 7]
var K = 10

console.log(f(A, K))

person גלעד ברקן    schedule 15.10.2019
comment
Большое спасибо, дружище! Это действительно помогло мне! - person Jim; 15.10.2019