Standard Problem Need help

Правка en2, от strange14, 2022-01-15 22:01:53

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский strange14 2022-01-15 22:01:53 198
en1 Английский strange14 2022-01-15 20:51:42 743 Initial revision (published)