You are using an outdated browser. Please update your browser for a better user experience.

Death Star Deliberation

dynamic

You're Captain Jack, Laser Destruction Coordinator aboard the Death Star. You're a spy for the Rebel Alliance and lately you've been doing more snooping than lasering. In fact you've been slacking so much that you haven't fired a single beam in months. Coming up soon is a board meeting with your boss and other bad dudes including Darth Vader himself. And you know that there will be no mercy if they become aware your insolence.

So now you must go about determining which planets to destroy given:

a. an integer j representing the amount of "laser juice" available to use to destroy planets
b. an array COST[1...n] sorted in ascending order representing the necessary amount of "laser juice" needed to destroy each planet P1,P2...PN
c. an array VAL[1...n] representing the value (as determined by your boss) of destroying each planet P1,P2...PN

Your goal is to maximize your summed value of planetary destruction by carefully choosing which planets to destroy given your amount of "laser juice".

Details

  • Your algorithm will need to return a list of planets to be destroyed E.x. {1, 5, 2}
  • For each of the planets, you will either destroy it or not destroy it. Partially destroying a planet is not an option.
  • The cost and value for destroying the ith planet will be found by visiting the ith index of each array.

Example:

               P1 P2 P3 P4
COST = { 5, 10, 12, 20}
VAL =    {12, 10,  7, 15}
j = 30

Maximum value is destroying P1,P2,P3 using 27 units of "laser juice" for a total of 29 value
This, as opposed to destroying P2,P4 using 30 units of "laser juice" for a total of 25 value