What is the length of the longest subsequence of positive numbers in a list whose sum does not exceed k?

edit

Let the list be $a1, a2, \dots, an$. We can use dynamic programming to solve this problem. Let $dp[i][j]$ represent the length of the longest subsequence of positive numbers in the list $a1, a2, \dots, ai$ whose sum does not exceed $j$. We can calculate $dp[i][j]$ by considering two cases:

Case 1: We include $ai$ in the subsequence. In this case, $dp[i][j]$ is equal to $dp[i-1][j-ai] + 1$, since we need to find the longest subsequence that does not exceed $j-ai$, and then add $ai$ to it.

Case 2: We do not include $a_i$ in the subsequence. In this case, $dp[i][j]$ is equal to $dp[i-1][j]$, since we can use the longest subsequence we found in the previous step.

Therefore, we have the following recurrence relation:

$$ dp[i][j] = \max(dp[i-1][j],\ dp[i-1][j-a_i] + 1), $$

with the base case $dp[0][j] = 0$ for all $j$, and the answer is $\max{dp[n][j]}$ such that $j \leq k$.

The time complexity of this algorithm is $\mathcal{O}(nk)$, where $n$ is the length of the list and $k$ is the maximum sum allowed.