4th question is also based on the same principle: subsequence.
There is always shortcut for a long way. I am finding long way. When I get the short cut I will surely provide the algorithm. 3rd question is possible when you know about fractional knapsack. After getting correct answer I will comeback here again.