"I know not with what weapons World War III will be fought, but World War IV will be fought with sticks and stones."
- Einstein
World suffered a great loss due to World War III. World is taken aback to the age when there were no mobiles, no computers, no TV's , no machines. Every nation, religion, community, who survived the war, are in the process of building a new World.
Two countries "Megaricka" and "Hugeisia" are emerging as new super-powers. There is a huge conflict between these two nations. If the conflict is not resolved, soon the world will suffer from another world war, World War IV. To stop the World War IV, a messenger named Bellman from Hugeisia is sent to Megaricka to sign a peace treaty. Everything went well, but there were few people from Megaricka who were against this treaty. So on the return journey of Bellman, he was held back by these protagonist of Megaricka.
Now if Bellman does not reach Hugeisia within 20 days, Hugeisia will attack Megaricka which will lead to World War IV. Bellman, being held hostage, could'nt do anything but plan his escape route. After 6 days of planning, Bellman finally planned his escape route. He must return to Hugeisia before the eve of 13th day from next morning. Bellman needs to carry some food with him to survive the next 13 days. Only options left in front of him were 5 fruits. He knew how long he could survive by eating fruit of each type.
Type of Fruit | Mango | Pineapple | Orange | Papaya | Apple
------------------------------------------------------------------------------------------------------------------
No of days 1 2 3 4 5
he can survive
------------------------------------------------------------------------------------------------------------------
Weight 1 2 3 4 5
Bellman's task was to find the combination of fruits he can carry with him which would weigh less and also at the same time, give him just enough energy to survive for 13 days. He could have tried all the combinations and found out the one which would suffice his need. But that would have taken long.
He remembered a technique called Dynamic Programming by which he can pick up minimum number of fruits that would let him survive for 13 days.
"Dynamic Programming : Dynamic programming is a method for solving complex problems by breaking them down into simpler sub-problems. To solve a given problem, we need to solve different parts of the problem (sub-problems), then combine the solutions of the subproblems to reach an overall solution. "
Now lets see how Bellman solved this problem. He split the problem of surviving for 13 days .
To survive 0th day he needs 0 fruits weighing 0 KG.
To survive 1st day he can select any from the 5 fruits.But if he selects anything but Mango, the weight will also increase, so he selects Mango.
To survive for 2 days he has 2 choices, 2 Mangoes or 1 Pineapple. In this case he selects 1 Pineapple. If he would have selected 2 Mangoes he would have had to carry two objects with him. So he makes a choice of 1 pineapple.
Similarly, he makes choices for all days till 13th day.
| Days | Options | Bellman's Choice | Total No of Fruits |
| 0 | No fruits | 0 | 0 |
| 1 | Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 1 | 1 M | 1 |
| 2 | Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 2 | 1 Pi | 1 |
| 3 | Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 3 | 1 O | 1 |
| 4 | Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 4 | 1 Pa | 1 |
| 5 | Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 5 | 1 A | 1 |
| 6 | Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 6 | 1 A,1 M | 2 |
| 7 | Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 7 | 1 A,1 Pi | 2 |
| 8 | Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 8 | 1 A,1 O | 2 |
| 9 | Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 9 | 1 A,1 Pa | 2 |
| 10 | Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 10 | 2 A | 2 |
| 11 | Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 11 | 2 A,1 M | 3 |
| 12 | Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 12 | 2 A,1 Pi | 3 |
| 13 | Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 13 | 2 A,1 O | 3 |
* M = Mango , Pi = Pineapple , O = Orange , Pa = Papaya , A = Apple
Code :
public int getMinimumFruits(int [] no_of_days,int need_to_survive) {
int [] optimum_choices = new int[need_to_survive+1];
optimum_choices[0] = 0;
for(int i = 1; i < optimum_choices.length;i++)
optimum_choices[i] = Integer.MAX_VALUE;
for(int i = 1; i <= need_to_survive;i++) {
for(int j = 0; j < no_of_days.length;j++) {
if(no_of_days[j] <= i && optimum_choices[i- no_of_days[j]] + 1 < optimum_choices[i] ) {
optimum_choices[i] = optimum_choices[i- no_of_days[j]] + 1;
}
}
}
return optimum_choices[need_to_survive];
}
From the above table, we can see that Bellman will carry 2 Apple and 1 Orange which will weigh 13 kg and he can survive for 13 days on those fruits.
He could have selected 13 mangoes which would weigh 13 kgs and survive for 13 days. But with this selection he would have had to carry a total of 13 objects with him, which are far too many compared to the optimum selection of only 3.
Before the World War III similar problem named "Min Coin Change" problem was solved using this technique.
Our hope is on Bellman to save the World from World War IV.Lets hope and pray that he escapes from Megaricka and reaches Hugeisia on time. :)
Happy Reading :)
