Skip to content

Latest commit

 

History

History
63 lines (44 loc) · 1.7 KB

robbery.md

File metadata and controls

63 lines (44 loc) · 1.7 KB
Raw

Problem statement

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.

Constraints
1 <= cap       <= 10^9
1 <= valueOfA  <= 10^9
1 <= valueOfB  <= 10^9
1 <= weightOfA <= 10^9
1 <= weightOfB <= 10^9
Format
Input

The only line contains 5 space separated integers denoting cap capacity of Truck), valueOfA(cost of type A toy), valueOfB(cost of type B toy), weightOfA(weight of type A toy) weightOfB(weight of type B toy) respectively.

Output

MAX AMOUNT THAT CAN BE GENERATED

Example
Sample Input
10 3 5 2 3
Sample Output
16

Possible solution

click to expand
  • let say the capacity = x.
  • take LCM of both the prices.
  • till the k * LCM take the maximum either A or B.
  • let the remaining capacity(y) = x - k * LCM
  • possible sceneraios
    • 0 < y < capacity_of_A < capacity_of_B < LCM : have no option, can't choose.
    • 0 < capacity_of_A < y < capacity_of_B < LCM : have no other option, will have to pick A.
    • 0 < capacity_of_A < capacity_of_B < y < LCM : coin change DP.