dynamic programming with memoization

Question

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:

Directed 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

• user22815: 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.
• Robert Harvey: Well, it is an exercise.
• maffh: Thank you for the comments. As Robert has mentioned it's an exercise to learn about memoization:)

Answer 1

As this is an excersize, I'll just give you a hint.

Look at the traveling salesperson dynamic programming algorithm. Its solving a similiar problem, and you should be able to adjust it to fit this problem.

• maffh: Thank you for the hint! Tommorow I'm going to look at the traveling salesperson dynamic programming algorithm.