Click here to Skip to main content
15,442,578 members
Home / Discussions / Algorithms
   

Algorithms

 
AnswerRe: Right approach for Dynamic Programming Pin
Patrice T29-Jun-20 11:26
mvePatrice T29-Jun-20 11:26 
AnswerRe: Right approach for Dynamic Programming Pin
Richard MacCutchan29-Jun-20 21:50
mveRichard MacCutchan29-Jun-20 21:50 
AnswerRe: Right approach for Dynamic Programming Pin
Gerry Schmitz30-Jun-20 15:13
mveGerry Schmitz30-Jun-20 15:13 
AnswerRe: Right approach for Dynamic Programming Pin
Luc Pattyn5-Jul-20 3:40
sitebuilderLuc Pattyn5-Jul-20 3:40 
Questionwhat is being done in this algorithim Pin
Muhammad Sudais26-Jun-20 8:40
MemberMuhammad Sudais26-Jun-20 8:40 
AnswerRe: what is being done in this algorithim Pin
Dave Kreskowiak26-Jun-20 9:06
mveDave Kreskowiak26-Jun-20 9:06 
AnswerRe: what is being done in this algorithim Pin
Richard MacCutchan26-Jun-20 22:19
mveRichard MacCutchan26-Jun-20 22:19 
QuestionDynamic Programming / Greedy algorithm - Best time with constraints Pin
Member 1487381426-Jun-20 1:04
MemberMember 1487381426-Jun-20 1:04 
Hey there.
First, it's not my homework, I've done my semester and I'm studying for my finals.
I find the course of Algorithms very difficult for me, and I would like to go over some exercises from past finals.

Here is one:
Given an array of jobs with different time requirements. There are K identical assignees available. Suggest an algorithm that, given K identical assignees, time-requirement for n jobs (t1, ..., tn), and time T1 answers "Yes" if it's possible to split the jobs among the assignees such that the maximum time required for each assignee to accomplish his jobs is at most T1. Otherwise, answer "No". 
The following constraints:
1. An assignee can be assigned only contiguous jobs. For example, an assignee cannot be assigned jobs 1 and 3, but not 2.
2. Two assignees cannot share (or co-assigned) a job, i.e., a job cannot be partially assigned to one assignee and partially to other

I thought of the greedy way - going over the job times, and sum them up to each assignee as far as possible. Also, I don't know if some sorting can help to make it more efficient.

Dynamic programming way - can't even start thinking about solution using DP. We are told to observe sub-problems of our problem etc... But I don't even see some suitable sub-problem. Can someone direct me please? How do you start thinking about solution using DP?

Thanks in advance.
AnswerRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
Richard MacCutchan25-Jun-20 23:18
mveRichard MacCutchan25-Jun-20 23:18 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
Member 1487381425-Jun-20 23:30
MemberMember 1487381425-Jun-20 23:30 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
Richard MacCutchan25-Jun-20 23:43
mveRichard MacCutchan25-Jun-20 23:43 
AnswerRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
Greg Utas26-Jun-20 0:42
mveGreg Utas26-Jun-20 0:42 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
Member 1487381426-Jun-20 1:00
MemberMember 1487381426-Jun-20 1:00 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
Greg Utas26-Jun-20 1:41
mveGreg Utas26-Jun-20 1:41 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
harold aptroot26-Jun-20 1:15
Memberharold aptroot26-Jun-20 1:15 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
Member 1487381426-Jun-20 1:19
MemberMember 1487381426-Jun-20 1:19 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
harold aptroot26-Jun-20 2:54
Memberharold aptroot26-Jun-20 2:54 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
Member 1487381426-Jun-20 3:14
MemberMember 1487381426-Jun-20 3:14 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
harold aptroot26-Jun-20 4:28
Memberharold aptroot26-Jun-20 4:28 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
Member 1487381426-Jun-20 5:27
MemberMember 1487381426-Jun-20 5:27 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
harold aptroot26-Jun-20 6:32
Memberharold aptroot26-Jun-20 6:32 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
Member 1487381426-Jun-20 9:06
MemberMember 1487381426-Jun-20 9:06 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
harold aptroot26-Jun-20 9:27
Memberharold aptroot26-Jun-20 9:27 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
Member 1487381426-Jun-20 10:30
MemberMember 1487381426-Jun-20 10:30 
GeneralRe: Dynamic Programming / Greedy algorithm - Best time with constraints Pin
harold aptroot26-Jun-20 11:05
Memberharold aptroot26-Jun-20 11:05 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.