No Dp Simple Greedy Solution


#1

No need of DP, This is a simple greedy question.

vector Solution::solve(int A, vector &B) {
int ind,minn = B[0];
int n = B.size();
for(int i = 1;i<n;i++)
{
if(minn>B[i])
{
minn=B[i];
ind = i;
}
}
int hits = A/minn;
vector ans;
int i = 0;
while(A>=0)
{
if(A-B[i]>=(hits-1)*minn)
{
A -=B[i];
hits -=1;
ans.push_back(i);
}
else i++;
}
ans.pop_back();
return ans;
}


#2

Your way of approaching the problem is nice. Just one suggestion though
You should modify your while loop to:
while(A>=0 && i<B.size())
Thank you


#3

Constraint on i is not needed here since i will never cross ind value