"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 :)
nice post
ReplyDeleteThanks for sharing this.
ReplyDeleteI like the problem and the way you described it too :)
Just want to know, will this be always O(n^2) ?
Thanks,
DeleteAnd yes the the complexity will always be O(nm) n = no of days need to survive & m = no of days he can survive.
Using Brute Force, running time will grow exponentially.
Not sure if my previous comment appeared, but I got a solution in ruby with O(1) solution:
Deletehttps://github.com/gouravtiwari/algorithmic-puzzles/blob/master/world_war_iv.rb
Can you please write your algorithm in comments. It will help non-ruby programmers/readers to understand your code. Also this is first time i have encountered ruby code in my life, so figuring out your solution and finding case where it might fail. And if it doesnt then we have O(1) solution. Thanks
Deleteint [] no_of_days = {1,5,10,20,25};
Deleteint need_to_survive = 40;
what answer you get for this case ?
Good point, here what my assumption and algorithm is:
Delete#Fruits are in array and their index in array represents days, i.e. fruits = ['m','pi','o','pa','a']
#no_of_days_to_survive can be any integer, by default it is 13
def min_weight(no_of_days_to_survive=13, fruits=[])
#if fruits array is passed then take it as it is, otherwise pick default ['m','pi','o','pa','a']
fruits = fruits.size == 0 ? ['m','pi','o','pa','a'] : fruits
# create map of fruits with days
fruits_map = {}
# for each fruit create a key value pair, i.e. {1: 'm', 2: 'pi', 3: 'o', 4: 'pa', 5: 'a'}
fruits.each_with_index{|f,i| fruits_map[i+1] = f}
# divide the no of days from fruit size array, i.e. if there are 5 fruits, and we calculate for 11 days, best fruit we want is 5th one twice, 11/5 = 2
no_of_best_picks = no_of_days_to_survive / fruits.size
# take a modulus to figure out which is next fruit, i.e. 11%5 = 1
next_fruit_to_pick = no_of_days_to_survive % fruits.size
#add the choices to the optimum choice map/hash
optimum_choices = {fruits_map[fruits.size] => no_of_best_picks}
optimum_choices[fruits_map[next_fruit_to_pick]] = 1 unless next_fruit_to_pick == 0
p "minimum weight: #{optimum_choices.values.inject(:+)}"
optimum_choices
end
so running this:
min_weight(13)
produces:
"minimum weight: 3"
"13 : {\"a\"=>2, \"o\"=>1}"
(1..13).each do |s|
p "#{s} : #{min_weight(s).inspect}"
end
# "minimum weight: 1"
# "1 : {\"a\"=>0, \"m\"=>1}"
# "minimum weight: 1"
# "2 : {\"a\"=>0, \"pi\"=>1}"
# "minimum weight: 1"
# "3 : {\"a\"=>0, \"o\"=>1}"
# "minimum weight: 1"
# "4 : {\"a\"=>0, \"pa\"=>1}"
# "minimum weight: 1"
# "5 : {\"a\"=>1}"
# "minimum weight: 2"
# "6 : {\"a\"=>1, \"m\"=>1}"
# "minimum weight: 2"
# "7 : {\"a\"=>1, \"pi\"=>1}"
# "minimum weight: 2"
# "8 : {\"a\"=>1, \"o\"=>1}"
# "minimum weight: 2"
# "9 : {\"a\"=>1, \"pa\"=>1}"
# "minimum weight: 2"
# "10 : {\"a\"=>2}"
# "minimum weight: 3"
# "11 : {\"a\"=>2, \"m\"=>1}"
# "minimum weight: 3"
# "12 : {\"a\"=>2, \"pi\"=>1}"
# "minimum weight: 3"
# "13 : {\"a\"=>2, \"o\"=>1}"
What answer did you get after running your Algorithm on this case
Deleteint [] no_of_days = {1,5,10,20,25};
int need_to_survive = 40;
Earlier version had a different assumption, where I assumed no_of_days will be sequential and I got O(1) solution.
DeleteNow, with:
int [] no_of_days = {1,5,10,20,25};
int need_to_survive = 40;
I get, 40 : {\"a\"=>1, \"o\"=>1, \"pi\"=>1}", in O(n), where n is length of no_of_days array.
Here is algorithm:
def min_weight_for_days_list(no_of_days=[], no_of_days_to_survive)
# Assumption is no_of_days[] and fruits[] both will be mapped one-to-one
fruits = ['m','pi','o','pa','a']
fruits_map = {}
# performing mapping
fruits.each_with_index do |fruit, index|
fruits_map[no_of_days[index]] = fruits[index]
end
# important mapping and reversing the order(so that is comes in descending order of keys) of the fruit_map
fruits_map = Hash[fruits_map.sort.reverse]
# fruits_map now a map, e.g. {25=>"a", 20=>"pa", 10=>"o", 5=>"pi", 1=>"m"}
# Here is the real procedure:
optimum_choices = {}
fruits_map.each do |days, fruit| # Runs O(n) times
no_of_picks = no_of_days_to_survive / days
if no_of_picks > 0
optimum_choices[fruit] = no_of_picks
end
no_of_days_to_survive = no_of_days_to_survive % days
end
return optimum_choices
end
def min_weight_for_days_list()
Delete# Assumption is no_of_days[] and fruits[] both will be mapped one-to-one
fruits = ['m','pi','o','pa','a']
fruits_map = {}
no_of_days = [1,5,10,20,25]
no_of_days_to_survive = 40
# performing mapping
fruits.each_with_index do |fruit, index|
fruits_map[no_of_days[index]] = fruits[index]
end
# important mapping and reversing the order(so that is comes in descending order of keys) of the fruit_map
fruits_map = Hash[25=>"a", 20=>"pa", 10=>"o", 5=>"pi", 1=>"m"]
# fruits_map now a map, e.g. {25=>"a", 20=>"pa", 10=>"o", 5=>"pi", 1=>"m"}
# Here is the real procedure:
optimum_choices = {}
fruits_map.each do |days, fruit| # Runs O(n) times
no_of_picks = no_of_days_to_survive / days
if no_of_picks > 0
optimum_choices[fruit] = no_of_picks
end
no_of_days_to_survive = no_of_days_to_survive % days
end
return optimum_choices
end
p min_weight_for_days_list()
The output of your logic is {"pi"=>8} Which is not optimal solution.
And it seems that logic you are trying to apply will give answer as a 3. But this is again not the optimal solution.
There are cases where Greedy Strategy will work for this problem. But that strategy wont give optimal solution for all cases.
Oh yes, I did not think this way, you are right, this is greedy, not optimal solution.
DeleteI think what I understood from this problem was, the fruits will be in sequence to save the person,e.g. 1,2,3,4,5... in that case the solution is in O(1). In the case where it is different than sequence, it gives greedy in O(n) but that is not optimal.
Thanks for explanation :)