Problem Statement is something like : We can carry 2 kinds of toys, both have some **weight** and **profit**. We want to **maximize** the profit in a way that the total weight does not exceed the given total **capacity**. There are infinite amount of both toys.↵
↵
Constraints : weights, profits of both kind of toys and capacity can have values between [1, 1e9]. ↵
↵
I was thinking of a greedy approach to this, where we can maximize the profit / weight ratio but it doesn't always give the optimal answer. Specifically in the case when we have unused space left. Also, linear solution won't fit in the time bounds.↵
I know this is a standard problem, but I always get stuck in them. I'd truly appreciate any help.↵
↵
UPD : Example : Profit_of_A = 3, Profit_of_B = 5, Weight_of_A = 2, Weight_of_B = 3, Capacity = 10. Answer = 16, as we can carry 2 type B toys and 2 type A toys which gives us the maximum profit.
↵
Constraints : weights, profits of both kind of toys and capacity can have values between [1, 1e9]. ↵
↵
I was thinking of a greedy approach to this, where we can maximize the profit / weight ratio but it doesn't always give the optimal answer. Specifically in the case when we have unused space left. Also, linear solution won't fit in the time bounds.↵
I know this is a standard problem, but I always get stuck in them. I'd truly appreciate any help.↵
↵
UPD : Example : Profit_of_A = 3, Profit_of_B = 5, Weight_of_A = 2, Weight_of_B = 3, Capacity = 10. Answer = 16, as we can carry 2 type B toys and 2 type A toys which gives us the maximum profit.
