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
  • 3
    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 Feb 28 '15 at 19:54
  • 2
    Well, it is an exercise. – Robert Harvey Mar 1 '15 at 1:29
  • Thank you for the comments. As Robert has mentioned it's an exercise to learn about memoization:) – maffh Mar 1 '15 at 18:44

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.

  • Thank you for the hint! Tommorow I'm going to look at the traveling salesperson dynamic programming algorithm. – maffh Mar 1 '15 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.