Skip to main content
Major revision to substitute a new algorithm for the previous one.
Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

Here is an outline of an algorithm using dynamic programming to solveYou 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.)

You can create a 3-dimensional array $b$, whereLet us use the notation in the original question. $b[i,j,k]$$R$ is true iffor the first $i$ friends can makeresistance capacity. $j$ kicks$S$ is for the array of totalstrengths.

Let the index of the first minimum strength be $k$$m$. All elements inThen the maximum number of kicks is $b$ are initialized to be false$n = R/S[m]$. FirstlySo $O=[m, m, \cdots, m]$, you can compute the case whenwhere the first friend makes somenumber of $m$'s is $n$, is a kick order with maximum number of kicks, with total strength $n*S[m]$. Then you

How can compute the case whenwe get a lexicographically smaller order with the first two friend make somesame number of kicks. Then? 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 case withresistance capacity $R$, then we can replace the first three friends and so on. The recurrence relation will be roughly likeelement in $b[i,j,k]$ is true if$O$ by $b[i-1,j-t,k-t*s_{i}]$ is true for some nonnegative integer$i$, making the order lexicographically smaller. To make it as lexicographically as small as possible, we would like the index $t$$i$ as small as possible and, wherethen, we would like to use it as many times as possible.

For example, $s_i$ is$R = 11, S = [6, 8, 5, 4, 7, 4]$. Then the kickfirst minimum strength ofis the first 4 whose index is 3. So $i$-th student$n=11/4=2$ and $O=[3,3]$ with total strength $4*2=8$. Once you have computedTo make it smaller, we will check the arraystrengths before 4 in order. The first one is $b$$6$. Since (by$8-4+6=10<11$, we find a nested loop of three levels)smaller order $[0,3]$. If we apply 6 again, itwe would get $10-4+6=12 > 11$. So we go ahead to check the next strength 8, which is easytoo large. So we go ahead to check 5. Since $10-4+5=11\le 11$, we find "the lexicographically smallesta smaller order of friends to kick Tushar so that$[0,2]$. Since the cumulative kick strengthroom left for replacement, (sum of$11-11 =0$, we stop our effort. The final answer is [0,2].

I have verified that my program wrote along the strengths of friends who kicks) doesn’t exceed his resistance capacity and total no"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.

Here is an outline of an algorithm using dynamic programming to solve the original question.

You can create a 3-dimensional array $b$, where $b[i,j,k]$ is true if the first $i$ friends can make $j$ kicks of total strength $k$. All elements in $b$ are initialized to be false. Firstly, you can compute the case when the first friend makes some number of kicks. Then you can compute the case when the first two friend make some number of kicks. Then the case with first three friends and so on. The recurrence relation will be roughly like $b[i,j,k]$ is true if $b[i-1,j-t,k-t*s_{i}]$ is true for some nonnegative integer $t$, where $s_i$ is the kick strength of the $i$-th student. Once you have computed the array $b$ (by a nested loop of three levels), it is easy to 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".

This problem is a variation of the unbounded knapsack problem.

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$, we find a smaller order $[0,3]$. If we apply 6 again, we would get $10-4+6=12 > 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.

Correct some typos.
Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

Here is an outline of an algorithm byusing dynamic programming to solve the original question.

You can create a 3-dimensional array $b$, where $b[i,j,k]$ is true if the first $i$ friends can make $j$ kicks of total strength $k$. All elements in $a$$b$ are initialized to be false. Firstly, you can compute the case ofwhen the first friend makemakes some number of kicks. Then you can compute the case ofwhen the first two friend makingmake some number of kicks. Then the case with first three friends and so on. The recurrence relation will be roughly like $b[i,j,k]$ is true if $b[i-1,j-t,k-t*s_{i}]$ is true for some nonnegative integer $t$, where $s_i$ is the kick strength of the $i$-th student. Once you have computecomputed the array $b$ (by a nested loop of three levels), it is easy to 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".

This problem is a variation of the unbounded knapsack problem.

Here is an outline of an algorithm by dynamic programming.

You can create a 3-dimensional array $b$, where $b[i,j,k]$ is true if the first $i$ friends can make $j$ kicks of total strength $k$. All elements in $a$ are initialized to be false. Firstly, you can compute the case of the first friend make some number of kicks. Then you can compute the case of the first two friend making some number of kicks. Then the first three friends and so on. The recurrence relation will be roughly like $b[i,j,k]$ is true $b[i-1,j-t,k-t*s_{i}]$ is true for some nonnegative integer $t$, where $s_i$ is the kick strength of the $i$-th student. Once you have compute the array $b$ (by a nested loop of three levels), it is easy to 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".

This problem is a variation of the unbounded knapsack problem.

Here is an outline of an algorithm using dynamic programming to solve the original question.

You can create a 3-dimensional array $b$, where $b[i,j,k]$ is true if the first $i$ friends can make $j$ kicks of total strength $k$. All elements in $b$ are initialized to be false. Firstly, you can compute the case when the first friend makes some number of kicks. Then you can compute the case when the first two friend make some number of kicks. Then the case with first three friends and so on. The recurrence relation will be roughly like $b[i,j,k]$ is true if $b[i-1,j-t,k-t*s_{i}]$ is true for some nonnegative integer $t$, where $s_i$ is the kick strength of the $i$-th student. Once you have computed the array $b$ (by a nested loop of three levels), it is easy to 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".

This problem is a variation of the unbounded knapsack problem.

Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

Here is an outline of an algorithm by dynamic programming.

You can create a 3-dimensional array $b$, where $b[i,j,k]$ is true if the first $i$ friends can make $j$ kicks of total strength $k$. All elements in $a$ are initialized to be false. Firstly, you can compute the case of the first friend make some number of kicks. Then you can compute the case of the first two friend making some number of kicks. Then the first three friends and so on. The recurrence relation will be roughly like $b[i,j,k]$ is true $b[i-1,j-t,k-t*s_{i}]$ is true for some nonnegative integer $t$, where $s_i$ is the kick strength of the $i$-th student. Once you have compute the array $b$ (by a nested loop of three levels), it is easy to 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".

This problem is a variation of the unbounded knapsack problem.