Problem 45450. Don't be Too Greedy!

Created by Asif Newaz

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Refer to the prev problem</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/problems/45416-don-t-be-greedy\"><w:r><w:t>&lt;https://www.mathworks.com/matlabcentral/cody/problems/45416-don-t-be-greedy</w:t></w:r></w:hyperlink><w:r><w:t>&gt;</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A list of assignments is given to the students. For this problem, assume - each of the assignment carries equal marks.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Different assignments take different amounts of time to complete - which is also given.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>But for each day of delay before starting an assignment, a penalty is added.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>for example,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Assignment = [ a1, a2, a3, a4, a5, a6]\n Marks = [100,100,100,100,100,100]\n Time Req. = [ 2, 4, 3, 8, 1, 10]\n Penalty = [ 10, 4, 1, 2, 5, 2]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Now, say if he starts with the 1st assignment - then a penalty will be added to all the other assignments for two days since it takes 2 days to complete the 1st assignment.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Then say he starts the 2nd assignment which takes 4 days to complete. So penalty will be added for the other assignments that he hasn't started yet (not the 1st one--since it's been finished)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>In which order should he finish his assignments so that he has to suffer the minimum penalty.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Refer to the prev problem <a href = "https://www.mathworks.com/matlabcentral/cody/problems/45416-don-t-be-greedy">https://www.mathworks.com/matlabcentral/cody/problems/45416-don-t-be-greedy</a>A list of assignments is given to the students. For this problem, assume - each of the assignment carries equal marks.Different assignments take different amounts of time to complete - which is also given.But for each day of delay before starting an assignment, a penalty is added.for example,<pre> Assignment = [ a1, a2, a3, a4, a5, a6]
 Marks = [100,100,100,100,100,100]
 Time Req. = [ 2, 4, 3, 8, 1, 10]
 Penalty = [ 10, 4, 1, 2, 5, 2]</pre>Now, say if he starts with the 1st assignment - then a penalty will be added to all the other assignments for two days since it takes 2 days to complete the 1st assignment.Then say he starts the 2nd assignment which takes 4 days to complete. So penalty will be added for the other assignments that he hasn't started yet (not the 1st one--since it's been finished)In which order should he finish his assignments so that he has to suffer the minimum penalty.

Solve

Solution Stats

28 Solutions
4 Solvers

Last Solution submitted on Dec 16, 2020

Last 200 Solutions

Problem Comments

6 Comments

6 Comments

Show 3 older comments

Binbin Qi on 13 Apr 2020

Can you give more explain about the example?

Asif Newaz on 14 Apr 2020

say i start 1st assign. today -- now it'll take me 2 days to complete. once I start with one assign, I've to finish it first - then jump to the next assign.
Now for these 2 days, I couldn't 'start' the other assign. so i've to suffer given penalty for each assign. each day. that is = 4*2 + 1*2 + 2*2 + 5*2 + 2*2 .= Σt(1)*p
After 2 days, say I start the last assign. which will take 10 days to finish. so for each of these 10 days - the penalty will keep adding for those assigns. that I've not yet started.
this way I'll continue.
at the end, a particular amount of penalty will be accumulated.
I want that total penalty to be minimum.
there'll be many combinations - among all those, which one will give me minimum penalty?
hope it is clear

Binbin Qi on 15 Apr 2020

OK, I see now

William on 15 Apr 2020

It seems that these problems have multiple degenerate solutions. For example, problem 1 is solved by [1 5 2 3 4 6] or [5 1 2 3 4 6]. Problem 2 has 4 solutions.

Asif Newaz on 16 Apr 2020

william,
if there exists more than one possible scenario, then the assignments are to be assigned based on their priority - meaning, 1st task should get preference over 5th.
similar is in the case of test suite 2 -- a3 should come before a6.
I think it should be ok then.

Rafael S.T. Vieira on 14 Oct 2020

Please, Asif, add the example that you gave in the comments to the problem description. It will make the problem clearer.

Problem Recent Solvers4

Problem Tags

array optimization

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 45450. Don't be Too Greedy!

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers4

Suggested Problems

More from this Author149

Problem Tags

Community Treasure Hunt

Problem 45450. Don't be Too Greedy!

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers4

Suggested Problems

More from this Author149

Problem Tags

Community Treasure Hunt

Players