Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is &lt;= T.

This question is a simplification of this dynamic programming question:


  It’s Tushar’s birthday today and he has N friends. Friends are
  numbered [0, 1, 2, …., N-1] and i-th friend have a positive strength
  S(i). Today being his birthday, his friends have planned to give him
  birthday bombs (kicks :P). Tushar’s friends know Tushar’s pain bearing
  limit and would hit accordingly. If Tushar’s resistance is denoted by
  R (>=0) then find the lexicographically smallest order of friends to
  kick Tushar so that the cumulative kick strength (sum of the strengths
  of friends who kicks) doesn’t exceed his resistance capacity and total
  no. of kicks hit are maximum. Also note that each friend can kick
  unlimited number of times (If a friend hits x times, his strength will
  be counted x times)
  
  Example: 
  
  R = 11, S = [6,8,5,4,7] Ans = [0,2]


Clearly, the maximum number of kicks = R/ min_element(S) = 11/4 = 2

So the question reduces to find the lexicographic smallest order of 2 elements in the Array such that the total of N elements is less than or equal to 11. 

I am having a tough time thinking about a solution for this. Any leads/ ideas would be appreciated!
You are on the right track.

It turns out the original question can be solved by a greedy algorithm. (A full blown solution by dynamic programming as I tried a while ago is both an overkill on coding and short of performance.)

Let us use the notation in the original question. $R$ is for the resistance capacity. $S$ is for the array of strengths. 

Let the index of the first minimum strength be $m$. Then the maximum number of kicks is $n = R/S[m]$. So $O=[m, m, \cdots, m]$, where the number of $m$'s is $n$, is a kick order with maximum number of kicks, with total strength $n*S[m]$.

How can we get a lexicographically smaller order with the same number of kicks? If we can find an index $i$ smaller than $m$ such that we can replace a kick of strength $S[m]$ by a kick of strength $S[i]$ without overpassing the resistance capacity $R$, then we can replace the first element in $O$ by $i$, making the order lexicographically smaller. To make it as lexicographically as small as possible, we would like the index $i$ as small as possible and, then, we would like to use it as many times as possible.

For example, $R = 11, S = [6, 8, 5, 4, 7, 4]$. Then the first minimum strength is the first 4 whose index is 3. So $n=11/4=2$ and $O=[3,3]$ with total strength $4*2=8$. To make it smaller, we will check the strengths before 4 in order. The first one is $6$. Since $8-4+6=10&lt;11$, we find a smaller order $[0,3]$. If we apply 6 again, we would get $10-4+6=12 &gt; 11$. So we go ahead to check the next strength 8, which is too large. So we go ahead to check 5. Since $10-4+5=11\le 11$, we find a smaller order $[0,2]$. Since the room left for replacement, $11-11 =0$, we stop our effort. The final answer is [0,2]. 

I have verified that my program wrote along the above approach works. Hopefully, I have written enough to encourage you to go ahead. Hopefully, I have not written too much to spoil the fun for you.

This problem is a variation of the unbounded knapsack problem.