Dynamic Programming: Water Tank Problem.

you are given following:
1. An empty tank
2. Unlimited source of water.
3. Some container of certain measurments and a container of 1 litre is always given.


Your job is to fill the tank from source of water using the containers in minimum number of steps.
You cant fill the container with a small amount of water than its size (filling partially is not allowed).
Find the number of steps and print the solution.


e.g.
Tank Size: 80 litre
Containers: 1,3,5,6,25 litre
Solution:
4
5,25,25,25


Tank Size: 71 litre
Containers: 1,3,5,6,25 litre
Solution:
6
3,6,6,6,25,25

Approach:
This problem is similar to the coin change problem, where the number of denominations is infinite.
Please refer:
http://karmaandcoding.blogspot.in/2012/01/coin-change-problem-with-limit-on.html

Code:

int [] container = {1, 3, 5, 6, 25};

fillTheTank(container, 80);
fillTheTank(container, 71);


Output:

Number of containers for 80: 4
25 25 25 5 
Number of containers for 71: 6
25 25 6 6 6 3