|
Given an array A of n integers and k <= n, we want to choose k numbers from this array and split them to pairs, such that the sum of the differences of those pairs (in absolute value) is minimal.
DP algorithm
Does someone have an idea? Where do I start from in this problem?
Thanks in advance.
modified 27-Jul-20 7:58am.
|
|
|
|
|
|
Please answer this question.
|
|
|
|
|
What question?
If you want to ask a question, then you need to watch what you are doing.
Edit the question, change teh subject line to a short (a dozen words max) description of the problem, then put the actual question in the "Message" area, which can take a fair amount of data.
At the moment, the subject is truncated so we have no idea what help you need.
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
What question ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
This exact worded homework assignment "question" showed up on this site two and half years ago.
You'll get the exact same answers the previous person got.
No, we're not doing your homework for you.
|
|
|
|
|
Basic Ideas
Here are some suggestions for distinguishing music from voice: Music usually has melody, which uses a wider range of sustained frequencies than voice. Polyphonic music has harmony, which uses more chords than does voice. A chord usually has multiple harmonics and subharmonics, while voice is much more limited in its harmonics.
Programming Approach
As general guidance, I would write tests based on realtime Fourier analysis, comparing samples of the range of music and the range of voice which you wish to distinguish (you have to make decisions about this so you know when you are successful). Each test can yield a measurement of effectiveness that you can use to direct the evolution of your ideas and program. Basically, if a test program gets 50% correct answers when faced with music and voice samples, then it is 0% successful, but if it gets 100% correct answers, it is 100% successful for that set of samples.
David Spector
|
|
|
|
|
Machine learning could probably use multi-track recordings of various genres for training. I have 3 volumes of Gregorian chanting.
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
I'm not sure what Confucius has to do with AI, but okay. Distinguishing music from voice must be done within a corpus of examples representative of a typical usage. I think I can say for sure that Gregorian Chant is not representative of typical use cases. But thanks for your post.
David Spector
|
|
|
|
|
Hey there.
So as my final in algorithms is getting closer, I'm trying to scrutinize some DP problems from past tests.
Input: A list L of strings, and another string s.
Output: "yes" if s is a concatenation of string from L, "no" otherwise.
Example: AGAGADIR is a concatenation of strings from the list {ADI, AG, R, SI}; but the string SIRA is not. Assume that checking if a string is contained in L costs O(1). Also, notice the option of an empty string.
My way of thinking about DP solution: The aim is initially to define the right sub-problems of the main problem, and then to develop the right recursion with the suitable memoization.
Sub-problems: we'll look at the string s up to the char at index i (between 0 and Length(s) - 1) and decide if it's itself a concatenation of strings from L.
Recursion: if i == 0 then the empty list is trivially in L, continue to i = 1; if i == 1 then go over the list L and compare if there is a char element in L which equals to the first character of s - if not, check for i=2, otherwise... here I'm stuck
Can someone please direct me? Give me some sense for DP?
Thanks in advance.
|
|
|
|
|
Member 14873814 wrote: DP problems
What is a DP problem ?
What i in your question ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Member 14873814 wrote: Example: AGAGADIR is a concatenation of strings from the list {ADI, AG, R, SI};
Where is "SI" in that? But "AGAGADIR" could also be considered to contain the strings "AG", "AGA", "GA", "GAD", "GADI" etc. You have to decide how you delineate each part that makes the whole string.
|
|
|
|
|
List<string> L = new List<string>() { "ADI", "AG", "R", "SI" };
StringBuilder sb = new StringBuilder( "AGAGADIR" );
foreach ( string l in L ) { sb.Replace( l, "" ); }
Console.WriteLine( sb.Length == 0 ? "YES" : "NO" );
sb = new StringBuilder( "SIRA" );
foreach ( string l in L ) { sb.Replace( l, "" ); }
Console.WriteLine( sb.Length == 0 ? "YES" : "NO" );
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
A recursive solution would be simple, something like:
bool CanBeConstructedFromPartsList(string word) {
if (word is empty) return true
result=false
foreach(part in partslist) {
if (word starts with part) result |= CanBeConstructedFromPartsList(word with part removed)
}
return result
}
I don't see a way to do better by storing some intermediate results though.
|
|
|
|
|
What is being done in following algorithm?
dmin ← ∞
for i ← 0 to n − 1 do
for j ← 0 to n − 1 do
if i != j and |A[i] − A[j]| < dmin
dmin ← |A[i] − A[j]|
return dmin
|
|
|
|
|
This smells of a homework assignment or a take-home test.
Walk through the code by hand, step-by-step, and start writing values down. You might find it pretty easy to figure out what it's doing.
|
|
|
|
|
It is not doing anything, since n and A are not defined.
|
|
|
|
|
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.
|
|
|
|
|
From the dark days of my project management life I think this is what we used to call CPA: Critical Path Analysis. So you need to build a picture of each stream where jobs must run in sequence, and how long they take. You can then figure out how many can actually run, given the number of assignees available. I have only ever done this manually by drawing a diagram on a blackboard, but I know there are plenty of packages around to help (even Microsoft Project). So start with some paper diagrams to get your thoughts clear on how to approach it in terms of logical steps.
BTW, the statement "an assignee cannot be assigned jobs 1 and 3, but not 2." does not make sense, as both parts are negative.
|
|
|
|
|
Actually, that doesn't help me to reach to something interesting...
I look at that this way: iterate over the jobs, summing their time-requirement up, and each time I sum another one up - I check if an assignee is able to... Actually, I don't know even what my condition has to be at all
Frustrating...
|
|
|
|
|
Sorry, that is the best I can offer, it's been more than 30 years.
|
|
|
|
|
I've never worked on this problem. Coming up with a solution is one thing, but coming up with the optimal solution is quite another. It seems to resemble the bin packing problem[^], which is NP-complete, but it has the additional constraint of having to assign contiguous jobs.
|
|
|
|
|
Hey, I've edited the problem.
It seems be different now from the bin one.
|
|
|
|
|
You need to provide an accurate description of the problem the first time so that people don't waste their time.
|
|
|
|
|
Checking whether the time limit of T1 can be met is easier than optimizing from scratch. You don't need DP, you don't need sorting, your greedy solution already does the job. It only takes linear time and there is nothing better you could do in that sense: the input all needs to be seen anyway so anything will take at least linear time.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
