patternMinor
Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value
Viewed 0 times
totalsmallestsuchorderthelexicographicallynumbersvaluethresholdthat
Problem
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 =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!
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!
Solution
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 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.
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 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.
Context
StackExchange Computer Science Q#96984, answer score: 7
Revisions (0)
No revisions yet.