2

反问：

正和 <= 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]

我很难考虑如何以相同的方式实现sum <= K 的最小长度子序列。

例子：

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

它当然不像将最大值更改为最小值那样简单，因为答案始终是基本情况。这让我想到，我们是否需要调整基本情况？我被困在这里，需要一些推动。

关于如何解决这个问题的任何想法？

4

3 回答 3

1

用有序对替换总和(sum, length)。现在应用您知道的先前算法。顺序是按字典顺序排列的，按总和然后按长度。你正试图接近(target_sum, 0)。

现在最接近的“总和”将是具有最小正差的最短子序列。

于 2018-09-06T20:31:15.953 回答
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]}
于 2018-09-06T22:18:28.903 回答
1

我认为这与您正在寻找的内容一致。在检查是否可以达到总和时，我们必须比您制定最大子序列时更加小心。在这个公式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))

于 2018-09-07T10:13:16.093 回答