GSFEB18C - Editorial

PROBLEM LINK :

Contest

DIFFICULTY:

Easy

PREREQUISITES :

Dynamic Programming Methodology

PROBLEM:

Obtain the maximum profit earned by selecting appropriate items and also, the sum of weights of the items should not be greater than the capacity of the basket.

EXPLANATION :

This is an analogy of the classic 0/1 Knapsack problem, where each item (i) has a specific weight wi and profit pi, and we have a knapsack with capacity M.
The goal is to fill the knapsack to it’s capacity atmost, and also maximise the profit by carefully selecting the items. This can be achieved using the concept of Dynamic Programming

For explanation of 0/1 Knapsack problem using Dynamic Programming Approach, refer this.

AUTHOR’S AND TESTER’S SOLUTIONS :

Solution to this problem is available here.