algorithm - 正和<= 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例子：

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

当然，要把最大值改为最小值并不是那么容易，因为答案永远是基本情况这让我想，我们需要调整基本情况吗？我被困在这里，需要一些推动。
你对如何解决这个问题有什么想法吗？

最佳答案

用有序对替换和。现在应用前面的算法。顺序是词典编纂的，然后是长度。你试图接近(sum, length)。
现在最接近的“和”将是具有最小正差的最短子序列。