Question

On the planet Sigma, robots excavate chunks of a very precious cristaline. These chunks can be divided into smaller part only on the Earth. Once a month, a spaceship comes to Sigma to bring cristaline to the Earth. The spaceship cannot take more than k pounds of the load. Naturally, it is desirable to take as much cristaline as the spaceship can.

Required:
a. Write an algorithm that will allow bringing the maximal amount of cristaline to the Earth. Prove that it is correct and estimate its time complexity.
b. Write an efficient algorithm that will allow bringing the maximal amount of cristaline to the Earth. Prove that it is correct and estimate its time complexity.

Answer 1

Start the algorithm and check the weight of the ship. Load the crystalline to the ship. Check to see if the ship weighs ship weight + k pound crystalline, if less, add more crystalline. If excess, remove the excess crystalline, but if the weight meets the condition, then take off with the loaded ship to planet sigma.

Step-by-step explanation:

The algorithm continuously checks the weight of the ship on loading with the calculated sum of the ship and k pound crystalline weight. The ship is able to load the correct maximum amount of crystalline to the planet sigma.