Standard Problem Need help

Revision en1, by strange14, 2022-01-15 20:51:42

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.

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)