Подпоследовательность минимальной длины с положительной суммой <= K

Question

Обратный вопрос:

Максимальная длина подпоследовательности с положительной суммой <= K на самом деле стандартная задача 01 рюкзак. </p>

Решение для него довольно простое:

int solve(const vector<int> &A, int K) {
    int dp[A.size()+1][K+1];
    int i, j;

    // Base Cases
    for(i=0; i<= K; i++)
        dp[0][i] = 0;
    for(i=0; i<= A.size(); i++)
        dp[i][0] = 0;


    for(i=1; i <= A.size(); i++)
    {
        for(j=1; j<= K; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(A[i-1] <= j)
                dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-A[i-1]]);
        }
    }
    return dp[A.size()][K]

Мне трудно думать, как подпоследовательность минимальной длины с суммой <= K </em> может быть реализована в том же духе.

Пример:

A = [14, 10, 4]
K = 14
Minimum Length Subsequence = 14
Maximum Length Subsequence = 10, 4 (Arrived from Knapsack)

Это, конечно, не так просто, как просто изменить макс на мин, так как тогда ответ всегда должен быть базовым. Что заставляет меня задуматься: нужно ли настраивать базовый вариант? Я застрял здесь и мне нужен толчок.

Есть идеи, как решить эту проблему?

Answer 1

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

{value: 14, components: [4, 10]}  

Если вы не знакомы с Javascript, массивы ведут себя больше как ассоциативные массивы или словари со строковыми ключами (поэтому необходимо преобразование Number), и for in выполняет итерации только по элементам, имеющим значение, если массив редкий Также slice и concat создают копию массива.

function minSub(array, target) {
    var sieve = [[]];
    for (var i in array) {
        var temp = [];
        for (var j in sieve) {
            var val = Number(j) + array[i];
            if (!sieve[val] || sieve[val].length > sieve[j].length + 1) {
                temp[val] = sieve[j].concat([array[i]]);
            }
        }
        for (var j in temp) {
            if (Number(j) <= target) {
                sieve[j] = temp[j].slice();
            }
        }
    }
    var max = 0;
    for (var j in sieve) {
        if (Number(j) > max) {
            max = Number(j);
        }
    }
    return sieve[max];
}

console.log(minSub([4, 10, 14], 14));
console.log(minSub([0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0], 8));

Обратите внимание, что, вопреки тому, что я предложил в комментарии, сортировка ввода в порядке убывания не гарантирует, что самая простая комбинация для формирования значения будет найдена первой; вам нужно проверять количество компонентов всякий раз, когда вы встречаете значение, уже присутствующее в сите; например с вводом:

{8, 4, 3, 2, 1}

Вы найдете комбинацию:

{value: 9, components: [4, 3, 2]}

до нахождения:

{value: 9, components: [8, 1]}

Answer 2

Я думаю, что это соответствует тому, что вы ищете. Мы должны быть более осторожны, чем при формулировке максимальной подпоследовательности, при проверке возможности получения суммы. В этой формулировке dp[i][j] является наименьшей подпоследовательностью, суммирующей до j, с учетом элементов до A[i] (поэтому i не является длиной подпоследовательности).

Код JavaScript (только слегка проверенный):

function solve(A, K) {
  let i,j;

  let dp = new Array(length);

  for (i=0; i<A.length; i++)
    dp[i] = new Array(K + 1);

  // Base Cases
  for(i=0; i<A.length; i++)
    dp[i][0] = 0;

  for (i=0; i<A.length; i++){
    // Exact match
    if (A[i] == K)
      return 1;

    // We can reach this sum with only one element
    if (A[i] < K)
      dp[i][A[i]] = 1;
    
    // There are no previously achieved sums
    if (i == 0)
      continue;
    
    for (j=1; j<=K; j++){
      dp[i][j] = dp[i][j] || dp[i - 1][j];

      if (A[i] <= j){
        dp[i][j] = Math.min(
          dp[i][j] || Infinity,
          1 + (dp[i - 1][j - A[i]] || Infinity)
        );
      }
    }
  }
  
  for (i=K; i>=0; i--)
    if (![undefined, Infinity].includes(dp[A.length - 1][i]))
      return dp[A.length - 1][i];
}

console.log(solve([1,2,3,4,5,6,7,8,9,10], 11));
console.log(solve([14,10,4], 14));
console.log(solve([0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0], 8));
console.log(solve([7,7,2,3],15))

Answer 3

Замените суммы заказанными парами (sum, length). А теперь примените предыдущий алгоритм, который вы знаете. Порядок лексикографический, по сумме, затем по длине. Вы пытаетесь приблизиться к (target_sum, 0).

Самая близкая «сумма» теперь будет самой короткой подпоследовательностью с минимальной положительной разницей.