Problem Statement
It has become increasingly popular in recent years to "soup-up" import automobiles.
What we want is to find the optimal mix of upgrades from a list of potential upgrades, given a fixed budget. We can use any item in the list either once, or not at all. If we have any money left over after buying items that give actual horsepower gains (hp gain > 0), we will then purchase accessories (defined as hp gain = 0). The more accessories we can buy, the better. You need to find out how much money we will have after we purchase all of our upgrades.
We will do the following steps, in order, to find the optimal mix:
- First, increase horsepower as much as possible within the given budget. Cost is only an issue if there are multiple mixes that produce the maximum amount of horsepower. If this situation occurs, choose the cheaper mix.
- Then proceed to take whatever money is left over, and buy as many accessories as possible. If there are multiple ways to purchase the same number of accessories, then we will choose the least expensive combination. Remember that accessories are defined as horsepower gain equals 0 (hp gain = 0).
Your task is to write a class Auto with a method upgrades that will return how much money we will have left over after all our purchasing is complete. The input will be a
Definition
- Class:
- Auto
- Method:
- upgrades
- Parameters:
- String[], int
- Returns:
- int
- Method signature:
- int upgrades(String[] options, int budget)
- (be sure your method is public)
Notes
- The method will return the amount of money we have left over after we have finished choosing, NOT the horsepower gain.
- Names of the modifications need not be unique.
Constraints
- options will contain between 0 and 10 elements, inclusive.
- Each element of options will be of the following format: "name:cost:hp_gain"
- name will be of length between 1 and 15, inclusive.
- name will contain only letters ('a'-'z','A'-'Z').
- cost will be between 0 and 9999, inclusive, no leading zeros are allowed.
- hp_gain will be between 0 and 999, inclusive, no leading zeros are allowed.
- budget will be between 0 and 2147483647, inclusive.
Examples
{ "intake:225:12", "turbo:1750:45", "exhaust:400:15", "fogs:150:0", "decals:10:0"}
0
Returns: 0
With a budget of 0, we must have 0 money left over.
{ "intake:225:12", "turbo:1750:45", "exhaust:400:15", "fogs:150:0", "decals:10:0"}
380
Returns: 145
We first search the modifications that will actually create a horsepower gain. We see that we can only afford the intake, so we purchase that. Now, we have 155 left over to buy accessories. We can afford either the fogs or the decals, but not both, so we buy the decals because they are cheaper.
{ "intake:225:12", "turbo:1750:45", "exhaust:400:15", "fogs:150:0", "decals:10:0"}
5000
Returns: 2465
We will first buy everything that has a horsepower gain of greater than 0, and that will leave us with 2625. Then, we can purchase both the fogs and the decals, so in the end we are left with 2465.
{ "intake:225:30", "turbo:1750:45", "exhaust:400:15", "fogs:150:0", "decals:10:0"}
1800
Returns: 1015
Again, we have the same list of options, but this time we have to decide carefully. At first glance, we see that we can purchase the turbo with the given budget, and receive a gain of 45 for 1750. But, as we keep searching, we see that we can purchase both the intake and the exhaust for 625, and get the same hp gain. We prefer this, so we will buy those two modifications and will be left with 1175. Now, we go on to purchase accessories, and see we can buy both with no problem.
{ "intake:225:12", "turbo:1750:45", "exhaust:400:15", "fogs:150:0", "decals:10:0"}
380
Returns: 145
returns 145
{"AA:1:1","AB:1:1","AC:1:1","AD:1:1","AE:1:1","BA:1:1","BB:1:1","BC:1:1","BD:1:1","BE:1:1"}
50
Returns: 40
return 30
{"AA:1:1","AB:1:1","AC:1:1","AD:1:1","AE:1:1","BA:1:0","BB:1:0","BC:1:0","BD:1:0","BE:1:0"}
5
Returns: 0
Returns 0
{}
0
Returns: 0
return 0
{}
98756
Returns: 98756
return 98756
{"AA:10:1","AB:10:2","AC:10:3","AD:5:5","AE:15:8","DA:10:0","DB:1:0","DC:1:0","DD:1:0","DE:1:0"}
125
Returns: 61
return 0
{"AA:1:10","AB:1:11","AC:1:12","AD:1:13","AE:1:14","BA:1:15","BB:5:0","BC:4:0","BD:3:1","BE:2:1"}
100
Returns: 80
Should return 70
{"a:100:10", "b:50:25", "c:60:20", "d:45:0", "e:50:0", "f:0:0"}
75
Returns: 25
{"a:100:10", "b:50:25", "c:60:20", "d:45:0", "e:50:0", "f:10:0"}
165
Returns: 0
should return ... 165 - 110 = 55; 55- 10 -45 = 0; return 0
{"a:5000:500", "b:4000:30", "c:9000:250", "d:2500:750", "e:1000:0"}
100000
Returns: 78500
{"a:5000:500", "b:4000:30", "c:9000:250", "d:2500:750", "e:1000:0", "f:4500:10", "g:2300:15", "h:1050:500", "i:1200:35", "j:7500:750"}
500000
Returns: 461950
hes rich, can buy eveyrthing
{"a:5000:500", "b:4000:30", "c:9000:250", "d:2500:750", "e:1000:0", "f:4500:10", "g:2300:15", "h:1050:500", "i:1200:35", "j:7500:750"}
15000
Returns: 450
{"a:5000:500", "b:4000:30", "c:9000:250", "d:2500:750", "e:1000:0", "f:4500:10", "g:2300:15", "h:1050:500", "i:1200:35", "j:7500:750"}
25001
Returns: 451
{"a:5000:500", "b:4000:30", "c:9000:250", "d:2500:750", "e:1000:0", "f:4500:10", "g:2300:0", "h:1050:500", "i:1200:35", "j:7500:750"}
9999
Returns: 249
{"a:5000:50", "b:5000:0"}
9999
Returns: 4999
{"a:5000:0", "b:4000:30", "c:9000:250", "d:2500:750", "e:1000:0", "f:4500:10", "g:2300:15", "h:1050:50", "i:1200:35", "j:7500:750"}
10097
Returns: 97