Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

Question

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 <= 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!

Answer 1

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.

Answer 2

JAVA Implementation of the above approach by Apaas.Jack:-

public class Solution {
    public int sumDiff(ArrayList<Integer> ans, ArrayList<Integer> B,int A){
        int sum = 0;
        for (int i = 0;i<ans.size();i++){
            sum += B.get(ans.get(i));
        }
        return A-sum;
    }
    public ArrayList<Integer> solve(int A, ArrayList<Integer> B) {
        int min = Integer.MAX_VALUE;
        int ind = -1;
        for (int i = 0;i<B.size();i++){
            if (min>B.get(i)){
                min = B.get(i);
                ind = i;
            }
        }
        int maxKicks = A/min;
        int temp = maxKicks;
        ArrayList<Integer> ans = new ArrayList<>();
        if (maxKicks==0){
            return ans;
        }
        for (int i = 0;i<maxKicks;i++){
            ans.add(ind);
        }
        int sum = maxKicks*B.get(ind);
        for (int i = 0;i<ind;i++){
            if (sumDiff(ans,B,A)==0||temp==0){
                Collections.sort(ans);
                return ans;
            }
            while ((sum-B.get(ind)+B.get(i))<=A && temp != 0){
                ans.remove(0);
                ans.add(i);
                temp--;
                sum += (B.get(i)-B.get(ind));
            }
        }
        Collections.sort(ans);
        return ans;     
    }
}

Answer 3

`c++ solution

#define deb(x) cout<<#x<<" : "<<x<<"\n"
vector<int> Solution::solve(int A, vector<int> &B) {
map<int,int> s;

  for(int i=0;i<B.size();i++)
  if(s[B[i]]!=0)
  s[B[i]]=min(s[B[i]],i);
  else
  s[B[i]]=i;
  int idx=min_element(B.begin(),B.end())-B.begin();
  int mini=*min_element(B.begin(),B.end());
 int x=A/mini;
 vector<int> ans;
 for(int i=0;i<x;i++)
 ans.push_back(mini);
 int sum=mini*x;
 int j=0;
 for(int i=0;i<idx;i++)
  {  //  deb(sum);
   while(j<ans.size() && sum+B[i]-mini<=A)
   {
       ans[j]=B[i];
       sum=sum+B[i]-mini;
       //deb(sum);
       j++;
   }
  }
  for(int i=0;i<ans.size();i++)
  {
    ans[i]=s[ans[i]];    
   }
    return ans;

}

`