Greedy solution with explanation in comments


#1

vector Solution::solve(int A, vector &B) {

int n = B.size();

vector<int> ans;

//Calculate min value
int min = 0;
for(int i=0;i<n;i++)
    if(B[min] > B[i])
        min = i;

//Calculate length of answer
int len = A/B[min];

//Calculate new set of interested values
vector<int> newSet;
int temp_min = 0;
newSet.push_back(temp_min);
for(int i=1;i<min;i++) {
    if(B[i] < B[temp_min])
        {
            temp_min = i;
            newSet.push_back(temp_min);
        }
}
newSet.push_back(min);

//Try to replace current answer having all min values with a lesser index values
int curr_ans = 0;
for(int j=1;j<=len;j++)
{
    for(int i=0;i<newSet.size();i++)
    {
        //B[newSet[i]] = pick curr element from interested array
        //curr_ans = Add already selected strength 
        //B[min]*(len-ans.size()-1) = Add strength of minimum value for remain ans
        if(B[newSet[i]] + curr_ans + B[min]*(len-ans.size()-1) <= A)
        {
            curr_ans += B[newSet[i]] ;
            ans.push_back(newSet[i]);
            break;
        }
        //Select min if none of the other elements satisfy condition
        else if(newSet[i] == min)
        {
            curr_ans += B[min] ;
            ans.push_back(min);
            break;
        }
    }
}
return ans;

}