0

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

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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