Minimum length subsequence with positive sum <= K

Question

The opposite question:

Maximum length subsequence with positive-sum <= K is in fact the standard 01 Knapsack problem.

The solution for it is pretty straightforward:

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]

I am having a tough time thinking how Minimum length subsequence with sum <= K could be implemented along the same lines.

Example:

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

Its certainly not as easy as just changing the max to min as then the answer shall always be the base case. Which leads me to think, Do we need to tweak the base case? I am stuck here and need some push.

Any ideas on how one should be solving this problem?

Answer 1

I think this is along the lines of what you're looking for. We have to be more careful than in your formulation of maximum subsequence in checking whether or not a sum can be reached. In this formulation dp[i][j] is the smallest subsequence summing to j, considering elements up to A[i] (so i is not subsequence length).

JavaScript code (only lightly tested):

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 2

The code snippet below shows what I mean by a sieve. It's a simple solution, and probably not useful for large input. It's not like the sieves to find primes, which only contain true or false, but more like a dictionary of combinations and their sum, like e.g.:

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

If you're unfamiliar with Javascript, arrays behave more like associative arrays or dictionaries with string keys (that's why the Number conversion is needed), and for in only iterates over the elements that have a value if the array is sparse. Also, slice and concat create a copy of the array.

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));

Note that, contrary to what I suggested in a comment, sorting the input in descending order doesn't guarantee that the simplest combination to form a value is found first; you have to check the number of components whenever you encounter a value already present in the sieve; e.g. with the input:

{8, 4, 3, 2, 1}

You'd find the combination:

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

before finding:

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

Answer 3

Replace the sums with ordered pairs (sum, length). And now apply the previous algorithm that you know. Order is lexicographic, by sum then by length. You are trying to come close to (target_sum, 0).

The closest "sum" now will be the shortest subsequence with minimum positive difference.