Standard Problem Need help
Difference between en1 and en2, changed 198 character(s)
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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English strange14 2022-01-15 22:01:53 198
en1 English strange14 2022-01-15 20:51:42 743 Initial revision (published)