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

Question

Противоположный вопрос:

Подпоследовательность максимальной длины с положительной суммой<= K на самом деле является стандартной задачей 01 ранца.

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

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 может быть реализована в том же духе.

Пример:

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

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

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

Answer 1

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

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

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

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

{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]}