Memoization & Statistics

Question

Assume that you have to fill a water tank by using cups of different sizes. Available cup sizes are 0.5, 1, 2, 5, 10, 20, 50, 100 liters. How many different ways are there to fill a tank of arbitrary size?

Write a recursive Python code to find the number of different ways to fill a tank of size given by user during run-time.

Improve your code by introducing a structure memoize. (Note that memoization is a technique that eliminates redundant calls and usually implemented by using a dictionary in Python.)

As an example for a tank of size 6lt. 18 Possible solutions are

0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5

1, 1, 1, 1, 1, 1

2, 2, 2

0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1

0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1, 1

0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1, 1, 1

0.5, 0.5, 0.5, 0.5, 1, 1, 1, 1

0.5, 0.5, 1, 1, 1, 1, 1

0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 2

0.5, 0.5, 0.5, 0.5, 2, 2

0.5, 0.5, 5

1, 1, 1, 1, 2

1, 1, 2, 2

1, 5

0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1, 2

0.5, 0.5, 0.5, 0.5, 1, 1, 2

0.5, 0.5, 1, 1, 1, 2

0.5, 0.5, 1, 2, 2

Answer 1

So before we can help you, you should do a try by yourself and present it here. Please store your code in playground, and link it here. Thanks!

Answer 2

It’s time dependent but I need a memoization approach and a recursive func.

Answer 3

Bobby if you do not know any approach or algorithm, you dont have to comment.This problem is very easy to some, and very hard to others.