# dynamic programming with memoization

I’ve a problem with a programming exercise. I hope you can help me. In this exercise I need to find out what the maximum profit is of taking pictures from several items in a park. For taking pictures I only have 50 minutes. Each item which you photograph has its own price. You can only photograph each item once. The exercise looks like this directed weighted graph:

The profit of taking pictures of items is shown right.

For this problem I’m going to use dynamic programming memoization, but I don’t know how to start. I’ve seen code from the knacksack problem, but I’m still stuck.

If you have any tips I would be really thankful!

This is the only code I have. The array for the names:

``````N[0] = ‘a’;
N[1] = ‘b’
N[2] = ‘c’
``````

I got this array for the weights:

``````W[0][0] = 100
W[0][1] = 17
W[0][2] = 40
W[1][0] = 60
W[1][1] = 100
W[1][2] = 103
W[2][0] = 23
W[2][1] = 29
W[2][2] = 100
``````

To get from the start to a, b or c it also cost time. I got the following array for that:

``````SW[0] = 12
SW[1] = 19
SW[2] = 10
``````
• Is this the whole problem? Why not just enumerate all six possibilities by hand? I am not sure that a computer is needed for this problem, unless this is a simplification and the real problem is much larger.
– user22815
Commented Feb 28, 2015 at 19:54
• Well, it is an exercise. Commented Mar 1, 2015 at 1:29
• Thank you for the comments. As Robert has mentioned it's an exercise to learn about memoization:) Commented Mar 1, 2015 at 18:44