Buying Apples! | Editorial by realalphastar

The question can be simplified as buying K kg of apples given cost and weight of bags in which they are available.

You are given an array of cost weight pair of bags of apples, you need to use those bags to sum up the weight to exactly K and to minimize the cost. The cost is the index of the array and weight is the value at that index(array is 1 indexed), the value -1 indicates that the particular  ith weighed bag is unavailable.

We can solve it by following recursive function.

cost(i) = min(A[j]+cost[i-j])

where cost[0]=0, j refers to the array of bags in that we skip if value is -1(box is unavailable).

![](https://1.bp.blogspot.com/-ygNPolu7DIo/XQnOGA6uQJI/AAAAAAAAIBk/L73KLEz9Rkw-wgaSR-46caEmRAdPgQxtACLcBGAs/s1600/IMG20190619112026.jpg)

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int N,K;
        cin>>N>>K;
        int A[K+1];
        for(int i=1;i<=K;i++)
            cin>>A[i];
        int ans[K+1];
        for(int i=0;i<=K;i++)
            ans[i]=-1;
        ans[0]=0;
        for(int i=1;i<=K;i++)
        {
            int mini = INT_MAX;
            for(int j=1;j<=K;j++)
            {
                if(i>=j&&A[j]!=-1)
                {
                   if(ans[i-j]!=-1)
                        mini = min(mini,A[j]+ans[i-j]);
                    else
                        mini = -1;
                }
            }
            if(mini == INT_MAX)
                ans[i]=-1;
            else
                ans[i]=mini;
        }
//        for(int i=0;i<=K;i++)
//            cout<<ans[i]<<" ";
            cout<<ans[K]<<endl;
    }
}

```

Buying Apples! | Editorial by realalphastar

Download submission

All caught up!

View submission

Is your resume even shortlisted?