How to solve these type of problems?

general
1

A thief plans to rob in a shop having 2 types of toys typeA toy and typeB toy.
Toys have some weight and cost.
i.e. Toy A has weight given by “weightOfA” and cost given by “ValueOfA”
similarly
ToyB has weight given by “weightOfB” and cost given by “ValueOfB”.
Shop has Infinite toys of both type.

Now thief has to rob some toys from the shop such that he generates maximum cost but the problem is that the thief has to carry the toys in a truck and the truck has a capacity (maximum weight which can be load on truck) given by “cap”,

Now you have to help Robber to generate maximum amount such that the toys can be carried in given capacity truck.

1 <= cap <= 10^9
1 <= valueOfA <= 10^9
1 < =valueOfB <= 10^9
1 <= weightOfA <= 10^9
1 <= weightOfB <= 10^9

We can’t run for loop as it is order of 10^9. According to me it’s answer is something like this eqn :

K1 * wa + K2 * wb <= cap , where K1 and K2 are the number of toys of type A and type B

2

Your equation is correct! , but it will not run in 1 second.
do you want to find no. of total toys, thief has stolen or you want to display the maximum amount he can make?
if you want to find , just multiply the number of toys of type A by their weight and subtract from total weight and find the nearest element which is divisible by no. of toys B. you can change whichever is greater A or B for maximum cost.

1 Like
3

I want to find the maximum amount. Not necessarily in \mathcal O(1). You can also find for \mathcal log(N).

4

Isn’t there any constraint for the number of toys for a particular test case?

5

No there is nothing like that, Only care about the amount irrespective of number of toys from both types.

6

Do you have question link?

7

No I don’t have link. This problem is appear in a hiring challenge, I solved it partially that’s why I want to know its full solution.

1 Like
8

Possible solutions:

  • Since it is a Maximisation problem, binary search is worth trying.
  • Simplex based solution.

I don’t know how to solve using either of them.

One of my friends (@bennyjoseph) has solved a similar problem using Simplex. You can refer to his solution.

He also explained his solution in the editorial.

1 Like