# Really annoying dynamic programming problemWatch

Announcements
#1
An artist has been commissioned to paint four portraits, each painting requires at least one day, and he has seven days to paint them all in. There are no fractions of a day allowed, and obviously he has to spend at least one day on each portrait, (and therefore he can't spend more than 4 days any one of them).
The longer he spends on a painting the more money he will receive for it.
Thus for portrait ONE he gets £120 for one day's effort, £150 for two, £165 for three and £200 for four. The revenues on the other portraits are similar but not exacly the same. You probably get the idea.
Now, this is a dynamic programming problem, which I thought I had no problems with, but I cannot see how to model it. If stage 1 is "nbr of days spent on portrait ONE", and so on, then I seem to get in a mess around stage 3 since how long you can spend on portrait THREE sepends on how long you spent on the first two portraits in horribly complicated ways.
Anyway, has anybody got a clue how I should model it? What will be the states and the stages?
0
7 years ago
#2
You have 7 days and 4 portraits what are the options for the time spent on each portrait?

What is the pay-off for each extra day spent on a portrait?
0
7 years ago
#3
Does it need to be a dynamic programming model?

I can see a 0-1 integer programming model.
0
#4
(Original post by msmith2512)
You have 7 days and 4 portraits what are the options for the time spent on each portrait?

What is the pay-off for each extra day spent on a portrait?
Thanks for your reply. For the portraits you have to spend at least one day on each one but can't spend more than 4 on any one (otherwise you can't spend at least one day on each one!) There are no other time restrictions.

The payoffs are similar (but not identical) to those I wrote for portrait one.
0
#5
(Original post by ghostwalker)
Does it need to be a dynamic programming model?

I can see a 0-1 integer programming model.
Can you give me a hint? I can't see anything that's not very complicated..
0
7 years ago
#6
(Original post by BrightStarXXXpa)
Can you give me a hint? I can't see anything that's not very complicated..
It's not complicated, but does involve a lot of variables, and constraints (would suit a computer).

For the j'th day's effort on painting i, we assign the variable which will take values in depending on whether we don't, or do, work the j'th day on painting i.

Since there are 4 paintings and we can spend up to 4 days on any one, we have a total of 16 variables.

Object function and all except one of the sets of contraints are straight forward.
The only "interesting" set is how to ensure that you can't do, for example, work day 3 of a particular painting, if you haven't worked day 1 and day 2.
I'll let you discover a method (it is simple), but can post further on that if you need. There's a hint in the spoiler.

Spoiler:
Show

For any given painting, we can consider the 4 days in order. In effect we have a function we can graph. That graph has a particular characteristic.

Edit: For a dynamic programming method, follow msmith2512, and there is a good example here.
0
7 years ago
#7
(Original post by BrightStarXXXpa)
Thanks for your reply. For the portraits you have to spend at least one day on each one but can't spend more than 4 on any one (otherwise you can't spend at least one day on each one!) There are no other time restrictions.

The payoffs are similar (but not identical) to those I wrote for portrait one.
These weren't questions - I had read your post. They are hints at how to think about doing the question. The key to this problem is understanding the benefit to the artist of doing each extra days work on a painting - possibly at the expense of working on a different portrait.

Of course the playoffs are similar but different. The whole point of the question is to work out the most advantageous order to utilise these similar but different payoffs.
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### University open days

• University of Bristol
Wed, 23 Oct '19
• University of Exeter
Wed, 23 Oct '19
• University of Nottingham
Wed, 23 Oct '19

### Poll

Join the discussion

Yes I know where I'm applying (152)
59.61%
No I haven't decided yet (58)
22.75%
Yes but I might change my mind (45)
17.65%