|
Creating the output of the pixel's isn't exactly the part I am looking for guidance on but this is a useful read anyhow to keep on my radar. I think maybe I am looking for "image vectoring" perhaps? Im not sure if that the correct term.
|
|
|
|
|
There is 4x4 matrix type of bool (can be 0 or 1)
It looks like this e.g.:
(1)(1)(0)(0)
(1)(0)(0)(1)
(1)(0)(0)(1)
(1)(1)(0)(0)
That is input...
And output is list(array) of pairs of positions and that pair represents one area
for example
In first column there are four 1s, so it should return (0,0)&(0,3) (1x4)
After that step then it becomes:
[1](1)(0)(0)
[1](0)(0)(1)
[1](0)(0)(1)
[1](1)(0)(0)
that means that 1s are used
After that you can do (0,3)&(1,0) (it's 2x2)
And that means that group can pass over like it's folded paper(when iterating use i%4)
Also that means 1s that are used can be used again
[1][1](0)(0)
[1](0)(0)(1)
[1](0)(0)(1)
[1][1](0)(0)
And do that over and over until all 1s are used
There are rules:
- All 1s must be used
- Same 1s can be used more than once
- Width and height must be power of 2 (1,2,4)
that means groups can be (1x1,2x1,1x2,2x2,4x2,2x4,4x1,1x4,4x4) - Group can cross over border to get to the other side
(like folded paper; 0 can be connected with 3 and vice versa) - Logically number of areas should be minimum possible
- Area is defined by it's top left corner and it's bottom right corner
(In form of point) - Optional:
The times one [1] is used more than once must be maximum possible
Output for this example:
(0,3)&(1,0)
(3,1)&(0,2)
Also output can be done with more areas but this is only using two and it's wanted solution
There is example of one interesting matrix:
(1)(0)(1)(1)
(1)(0)(1)(0)
(1)(0)(1)(0)
(1)(0)(1)(1)
Output:
(3,3)&(0,0)(that means that all 4 corners are included in one area)
(0,0)&(0,3)
(2,0)&(2,3)
Another:
(0)(1)(1)(1)
(0)(1)(0)(1)
(1)(1)(0)(1)
(0)(0)(0)(0)
Output:
(0,2)&(1,2)
(1,1)&(1,2)
(1,0)&(2,0)
(3,0)&(3,1)
(3,1)&(3,2)
Preferable languange is any C type (C C++ C#)
|
|
|
|
|
Very interesting, but what is your question? If you are expecting someone here to write your homework assignment, then I am afraid you will be disappointed.
|
|
|
|
|
My question is:
Is there any idea I can start from I tried finding every group for each [one] left...
but it takes 16 ifs...
Also this is not my homework I'm just trying to implement algorithm of
"minimization of switching function" for digital circuits with visualising it so I need that output
|
|
|
|
|
Sorry, no idea. What algorithm is it supposed to follow?
|
|
|
|
|
|
I would try a "classifier".
Flatten it out to a 16 column "record".
4x4 is manageable; you should be able to construct your own "training data" with all combinations.
You then run your "sample" against the training data and have it "classify" your (flattened) matrix by comparing columns.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
I would start by writing classifiers for all sub-sizes:
1x1 (trivial)
2x2
3x3
4x4
The previous level may be placed inside the next level in one of 4 positions, possibly allowing the creation of additional output lines. IOW, use recursion!
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows.
-- 6079 Smith W.
|
|
|
|
|
I work for a milk company and I have to deliver Milk to stores. I also have to pick up expired milk when there is some. Is there an algorithm or process that can track the sales and expired product to predict future sales and minimize the amount of expired product picked up?
|
|
|
|
|
I was wondering a problem from algorithm - Proving that a particular matrix exists - Stack Overflow[^] Somebody said that there is a solution found by a computer, but I was unable to find a proof.
Prove that there is a matrix with 117 elements containing the digits such that one can read the squares of the numbers 1, 2, ..., 100.
Here read means that you fix the starting position and direction (8 possibilities) and then go in that direction, concatenating the numbers. For example, if you can find for example the digits 1,0,0,0,0,4 consecutively, you have found the integer 100004, which contains the square numbers of 1, 2, 10, 100 and 20, since you can read off 1, 4, 100, 10000, and 400 (reversed) from that sequence.
But there are so many numbers to be found (100 square numbers, to be precise, or 81 if you remove those that are contained in another square number with total 312 digits) and so few integers in a matrix that you have to put all those square numbers so densely that finding such a matrix is difficult, at least for me.
I found that if there is such a matrix mxn, we may assume without loss of generality that m<=n. Therefore, the matrix must be of the type 1x117, 3x39 or 9x13. But what kind of algorithm will find the matrix?
I have managed to do the program that checks if numbers to be added can be put on the board. But how can I implemented the searching algorithm?
|
|
|
|
|
Hi all,
I want to calculate the number of labels available on a roll.
Please help me to found the exact formula.
Thanks
|
|
|
|
|
|
I'm working on formulating an optimization problem to find the minimum weighted tree between a set of terminals (aka Steiner tree). The literature on Steiner tree formulations consider the set of terminals as input, and provides the minimum weighted tree connecting them (possibly also including non-terminal transit nodes). However, the structure of my problem requires these set of terminals to be decided "in conjunction with" the minimum Steiner tree between them. Hence, existing Steiner tree formulations based on cut-sets, multi-commodity flows, etc., are not applicable in my case, given lack of prior knowledge about the set of terminals.
Any suggestions on how to design a linear program for Steiner tree where the set of terminals is not provided as an input, and at best can be denoted by a set of decision variables?
|
|
|
|
|
The problem is the following:
Given N containers with different sizes between 1 and N (2 <= N <= 10^5), each of them placed in a line, determine how many places can be freed if one container can be placed in another only if its size is less that the others size and they don't have any other containers between them. Multiple placings can be made, so if there are containers placed in each other, they can be placed in another container (if the bottom container size is less than the others size), a container can be placed in another group of container (if its size is less than the top container size), and a group of containers can be placed in another group of containers with similar rules.
Example: if N = 8 and the containers are placed in the following order: 1 8 2 4 3 6 7 5, then 7 places can be freed; we place 3 in 4, then 2 in 3, 6 in 7, 5 in 6, 4 in 5, 7 in 8, and 1 in 2. This way all the containers can be packed in a single group.
My idea of solving this problem is the following: calculate the minimum difference between all the neighbour containers sizes, then find the first pair where this minimum appears and make a placement. Then repeat the whole process again until no placements can be made. Then calculate the freed places.
This can be done trivially in quadratic time, but that is too slow. The other thing that bothers me that this method may not lead to the optimal solution.
Note: I have to implement the algorithm in C++, and my program has to finish in 200ms. This is why a quadratic solution has no chance. Also, I don't want to have my job done by others, I posted this because I got stuck solving the problem, and needed some help to know if my approach is correct or how can I make optimizations.
modified 24-Apr-22 21:01pm.
|
|
|
|
|
You set no limit on N, so there is no solution that will always "finish in 200 ms" ... (which is a long time) ... unless you add a timer; if it runs too fast.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Hello,
First and foremost thank you very much to anyone who may be able to help. I am looking for anyone to help me understand the steps that need to be taken in order to predict the output of the following code:
var msg = 'hellohello'
for(x = 2; x < msg.length - 2; x++)
{
if(msg.length == 1)
{
for(var i = 0; i < 6; i++)
{
console.log(i);
}
}
else
{
for(var i = msg.length; i > (msg.length - 1); i--)
{
console.log(i);
}
}
}
|
|
|
|
|
One option would be to step through it with a debugger.
Another option (which will teach you more) is to "play computer". You read through the code, following the instruction at each line. For example:
var msg = 'hellohello'
(Create a label 'msg', and give it the value 'hellohello')
for(x = 2; x < msg.length - 2; x++)
(Create a label 'x', and give it the value 2. If x < msg.length - 2, execute the loop)
…
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows.
-- 6079 Smith W.
|
|
|
|
|
You should be the computer. Start at the beginning, keep a written note of the current values of x, i and the length of the message, and proceed to the next statement. It might seem tedious, but it will help you develop a skill that has will serve you well (as it has served me well in my 40+ years as a programmer).
|
|
|
|
|
Problem Statement :
Given a graph which represents a flow network where every edge has a capacity. Also given two vertices source ‘s’ and sink ‘t’ in the graph, find the maximum possible flow from s to t with following constraints :
Flow on an edge doesn’t exceed the given capacity of the edge.
Incoming flow is equal to outgoing flow for every vertex except s and t.Dinic’s algorithm for Maximum Flow - Code Companion[^]
|
|
|
|
|
And you have a question ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Hello to all! I need to solve the problem. An approximate representation and partial solution is already there. This controversial mathematical question can push you away, since I do not go into some important points. I just want to state the very idea. I hope someone has enough time and will interest you. In programming, we are all accustomed to using only the numerical number system. However, theoretically, there is a vector system. Why not try to implement it in such a way that the distances between the cells of information are also carriers of information? Due to this, the counting rate will be completely predetermined, and, accordingly, it will be possible to solve much more complex tasks. Below I have laid out my presentation, as an example of the simplest implementation can be represented through the creation of an emulator.
Can apply c/c++
// designation in area. Position Form.
arr1 =
Vector1 = Vector3 + Vector2, Vector4 + (-Vector5), Vector10 + (-Vector12), Vector16 + (-Vector17) = 1;
Vector2 = (-Vector3) + Vector1, Vector6 + (-Vector5), Vector15 + (-Vector13), Vector18 + (-Vector17) = 1;
Vector3 = Vector1 + (-Vector2), Vector4 + (-Vector6), Vector7 + (-Vector9), Vector16 + (-Vector18) = 1;
Vector4 = Vector1 + Vector5, Vector3 + Vector6, Vector10 + (-Vector11), Vector7 + (-Vector8) = 1;
Vector5 = (-Vector1) + Vector4, (-Vector2) + Vector6, Vector12 + (-Vector11), Vector13 + (-Vector14) = 1;
Vector6 = (-Vector5) + (-Vector2), (-Vector3) + Vector4, Vector15 + (-Vector14), Vector9 + (-Vector8) = 1;
Vector7 = Vector4 + Vector8, Vector3 + Vector9 = 1;
Vector8 = (-Vector6) + Vector9, (-Vector4) + Vector7 = 1;
Vector9 = Vector6 + Vector8, (-Vector3) + Vector7 = 1;
Vector10 = Vector4 + Vector11, Vector1 + Vector12 = 1;
Vector11 = (-Vector5) + Vector12, (-Vector4) + Vector10 = 1;
Vector12 = Vector5 + Vector11, (-Vector1) + Vector10 = 1;
Vector13 = Vector5 + Vector14, (-Vector2) + Vector15 = 1;
Vector14 = (-Vector6) + Vector15, (-Vector5) + Vector13 = 1;
Vector15 = Vector6 + Vector14, Vector2 + Vector13 = 1;
Vector16 = Vector1 + Vector17, Vector3 + Vector18 = 1;
Vector17 = (-Vector1) + Vector16, (-Vector2) + Vector18 = 1;
Vector18 = Vector2 + Vector17, (-Vector3) + Vector16 = 1;
// arr is an array containing the shape of the initial tetrahedron for defining the reference system in space.
// 4 conditions(directions) of expansion
Vector1 * 2, Vector4 * 2, Vector3 * 2, Vector10 * 2, Vector7 * 2, Vector16 * 2;
// if not, then
Vector1 * x^(x + 1), Vector4 * x^(x + 1), Vector3 * x^(x + 1), Vector10 * x^(x + 1), Vector7 * x^(x + 1), Vector16 * x^(x + 1);
Vector3 * (-2), Vector6 * 2, Vector2 * 2, Vector9 * 2, Vector15 * 2, Vector18 * 2;
// if not, then
Vector3 * (-x^(x + 1)), Vector6 * x^(x + 1), Vector2 * x^(x + 1), Vector9 * x^(x + 1), Vector15 * x^(x + 1), Vector18 * x^(x + 1);
Vector1 * (-2), Vector2 * (-2), Vector5 * 2, Vector12 * 2, Vector13 * 2, Vector17 * 2;
// if not, then
Vector1 * (-x^(x + 1)), Vector2 * (-x^(x + 1)), Vector5 * x^(x + 1), Vector12 * x^(x + 1), Vector13 * x^(x + 1), Vector17 * x^(x + 1);
Vector4 * (-2), Vector5 * (-2), Vector6 * (-2), Vector8 * 2, Vector11 * 2, Vector14 * 2;
// if not, then
Vector4 * (-x^(x + 1)), Vector5 * (-x^(x + 1)), Vector6 * (-x^(x + 1)), Vector8 * x^(x + 1), Vector11 * x^(x + 1), Vector14 * x^(x + 1);
x = 2^n
n = 1++
int r1 = sum(arr1; sum[arr1; g]);
// the sum of all vectors, in an arbitrary order g, in the range from 1 to 18
arr1 = sum(Vector1; Vector18);
arr2 = sum(Vector18; Vector36);
arrn = sum(18*n; n+18);
// reverse motion system.
// points of position with points in the center and continuous connection of vectors at points of separation are indicated
arr1_=
Line14 = Vector1(0; 0.5); Vector4(0; 0.5);
Line15 = Vector1(0.5; 1); Vector5(0; 0.5);
Line13 = Vector1(0; 0.5); Vector3(0; 0.5);
Line34 = Vector3(0; 0.5); Vector4(0; 0.5);
Line117 = Vector1(0.5; 1); Vector17(0; 0.5);
Line12 = Vector1(0.5; 1); Vector2(0.5; 1);
Line217 = Vector2(0.5; 1); Vector17(0; 0.5);
Line25 = Vector2(0.5; 1); Vector5(0; 0.5);
Line212 = Vector2(0.5; 1); Vector12(0; 0.5);
Line213 = Vector2(0.5; 1); Vector13(0; 0.5);
Line112 = Vector1(0.5; 1); Vector12(0; 0.5);
Line37 = Vector3(0; 0.5); Vector7(0; 0.5);
Line316 = Vector3(0; 0.5); Vector16(0; 0.5);
Line310 = Vector3(0; 0.5); Vector10(0; 0.5);
Line410 = Vector4(0; 0.5); Vector10(0; 0.5);
Line416 = Vector4(0; 0.5); Vector16(0; 0.5);
Line47 = Vector4(0; 0.5); Vector7(0; 0.5);
Line512 = Vector5(0; 0.5); Vector12(0; 0.5);
Line513 = Vector5(0; 0.5); Vector13(0; 0.5);
Line517 = Vector5(0; 0.5); Vector17(0; 0.5);
Line62 = Vector6(0; 0.5); Vector2(0; 0.5);
Line63 = Vector6(0; 0.5); Vector3(0.5; 1);
Line618 = Vector6(0; 0.5); Vector18(0; 0.5);
Line69 = Vector6(0; 0.5); Vector9(0; 0.5);
Line615 = Vector6(0; 0.5); Vector15(0; 0.5);
Line79 = Vector7(0.5; 1); Vector9(0.5; 1);
Line78 = Vector7(0.5; 1); Vector8(0.5; 1);
Line89 = Vector8(0.5; 1); Vector9(0.5; 1);
Line1012 = Vector10(0.5; 1); Vector12(0.5; 1);
Line1011 = Vector10(0.5; 1); Vector11(0.5; 1);
Line1112 = Vector11(0.5; 1); Vector12(0.5; 1);
Line1315 = Vector13(0.5; 1); Vector15(0.5; 1);
Line1314 = Vector13(0.5; 1); Vector14(0.5; 1);
Line1415 = Vector14(0.5; 1); Vector15(0.5; 1);
Line1617 = Vector16(0.5; 1); Vector17(0.5; 1);
Line1618 = Vector16(0.5; 1); Vector18(0.5; 1);
Line1718 = Vector17(0.5; 1); Vector18(0.5; 1);
Line64 = Vector6(0.5; 1); Vector4(0.5; 1);
Line65 = Vector6(0.5; 1); Vector5(0.5; 1);
Line611 = Vector6(0.5; 1); Vector11(0; 0.5);
Line614 = Vector6(0.5; 1); Vector14(0; 0.5);
Line68 = Vector6(0.5; 1); Vector8(0; 0.5);
// Expansion of the reverse system
// Superimposed on top in the same position with additional conditions.
Vector1 * 2, Vector4 * 2, Vector3 * 2, Vector10 * 2, Vector7 * 2, Vector16 * 2;
// if not, then
Vector1 * x ^ (x + 1), Vector4 * x ^ (x + 1), Vector3 * x ^ (x + 1), Vector10 * x ^ (x + 1), Vector7 * x ^ (x + 1), Vector16 * x ^ (x + 1);
Vector3 * (-2), Vector6 * 2, Vector2 * 2, Vector9 * 2, Vector15 * 2, Vector18 * 2;
// if not, then
Vector3 * (-x ^ (x + 1)), Vector6 * x ^ (x + 1), Vector2 * x ^ (x + 1), Vector9 * x ^ (x + 1), Vector15 * x ^ (x + 1), Vector18 * x ^ (x + 1);
Vector1 * (-2), Vector2 * (-2), Vector5 * 2, Vector12 * 2, Vector13 * 2, Vector17 * 2;
// if not, then
Vector1 * (-x ^ (x + 1)), Vector2 * (-x ^ (x + 1)), Vector5 * x ^ (x + 1), Vector12 * x ^ (x + 1), Vector13 * x ^ (x + 1), Vector17 * x ^ (x + 1);
Vector4 * (-2), Vector5 * (-2), Vector6 * (-2), Vector8 * 2, Vector11 * 2, Vector14 * 2;
// if not, then
Vector4 * (-x ^ (x + 1)), Vector5 * (-x ^ (x + 1)), Vector6 * (-x ^ (x + 1)), Vector8 * x ^ (x + 1), Vector11 * x ^ (x + 1), Vector14 * x ^ (x + 1);
x = 2^n
n = 1++
int r1 = sum(arr1_; sum[arr1_; G]);
G = Line g
// the sum of all vectors, in an arbitrary order g, in the range from 1 to 18
arr1_ = sum(0.5*Vector1 + 0.5*VectorN; 0.5*Vector18 + 0.5*VectorN);
0.5*Vector1 + 0.5*VectorN = 1 or 0.5
arr2 = sum(Vector18; Vector36);
arrn = sum(18*n; n+18);
// number of combinations and setting of numerical conditions
K(arr1) = 2 ^ x - 1
// if not, then
K(arr1_) = 2 ^ x - 1
// number of algorithms max movement on a diverging row
:Vectorn
(arr1 - 1) ^ 2 = 17 ^ 2 = 289
(arr_1 - 1) ^ 2 = 17 ^ 2 = 289
(arrn - 1) ^ 2
(arr_1 - 1) ^ 2
// max movement arr1
:K_maxr
= sum[1; (Vectorn-2)] + (Vectorn + Vectorn+1) or
= sum(Vector1; Vector16) + (Vector n + Vector n+1);
// min movement arr1
:K_minr
= Vectorn +(arrn-Vector g)
// max movement arr1_
: K_maxr
= sum[1; (Line n - 2)] + (Line n + Line n + 1)
// min movement arr_1
: K_minr
= Vectorn + (arr_n - Line g)
// the numerical designation must be replaced on vector combinations from maximum
// to minimum in the system arr1 and vice versa in the system arr1_
I'm not so good at writing code. Moreover, it is necessary to take into account all the subtleties of the low-level environment. It is difficult to explain, but if short, it is necessary to create an artificial vector environment inside the existing numerical (point). When compliance with several specific conditions, will be folded into a figurative array. Which, in turn, is the composition of the new elements (geometric) composite units appearing in space. If you are interested, I can tell you in more detail. I do not scream with pride about the prospects and uniqueness. But I am sure that this method of calculation has never been applied before. This is just an idea. And if it seems stupid to you, that's your opinion.
|
|
|
|
|
Too much code. Meaningless variable names. An "emulator" that emulates "what"?
You're going to have to be a lot more "interesting" for anyone else to take any interest.
Is this another one where you need an NDA before you over the "important points"?
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Going to give you a small bio just so you know I have a feel for what (I think) you're trying to do. I'm old, but (to my knowledge) wrote the first flight simulator with shading including a helmet you wore to display the world depending on where you turned your head. This was 1984. At that time I had to write a fast transcendental calculator (nearly 100x faster than the then blossoming Math CoProcessors; not as precise but good enough for the app). During that time frame I read a book called, "Flight Simulators" by Dr. Bruce Artwick and a fellow that was shafting us $30-$40 a pop for new fixes to his DOS OS named Bill Gates. [My opinion of Mr. Gates improved drastically when he donated $2 billion to world health.].
My brother had recommended the book, my comment was, "These guys know their math (linear algebra) but can't write code worth sh..". Mr. Gates openly admitted this fact in an interview.
When asked "Just how good is S.... (me)?" in class one day, a 25 year Calculus teacher remarked, "He's certainly the best I've ever had and maybe the best I've ever met.".
Now that my back is throbbing from all the self-patting. I'll start the humble path. I'm "out of shape". Math is like distance running. A guy who can break 4 minutes for the mile (I got THAT close but never did) is only as good as his recent workouts. The same is true for math. I am WAY out of shape but hope my intuition is still decent.
When you say "solve more complex problems", I beg to differ. Tensor mathematics, matrices and the like introduce methodology shorthands and NOT the ability to solve unique types of problems (like calculus, differential equations and Laplace Transforms do). Even the latter is solved using the four basics (multiplication, division, etc.) in the end but they introduce the logic required to deduce those basic operations.
Let's take a discussion of matrices for example. Given a set of simultaneous equations you can reduce them to a matrix and it and the rules present easy visualization (for human eyes, not code) and logic-less (strictly rule based) solution methods (which makes coding easier).
A clever coder can solve simultaneous equations in code w/o matrices but a garden variety coder can do it with matrices. My impression of what's going on here may be similar. You're trying to introduce a visualization method and set of rules to bypass the complexity of "the other way". What you will not introduce is ability to solve problems that were deemed unsolvable by other methods. I hope I'm wrong and we get to read about your receipt of the Nobel Prize for Mathematics one day.
If you actually want help writing the code then write a function that calculates ONE calculation you want to perform no matter how ugly.
Perhaps someone familiar with tensor math (or something similar) can point you to the latest and greatest technique (like using the GPU to help). BTW, physicists have been coding solutions for as long as there have been PCs (starting with the Manhattan Project) and, because they are the tools of the trade, use math as a second language. After a lifetime of experience, I have come under the impression that nowadays anybody can write code (thanks in no small part to the efforts of the aforementioned, Mr. Bill Gates) but only mathematicians can write the really hard stuff. Again, thanks to the efforts of many, 99% (probably more like 99.9999%) of all coding requires little math skill. Yours appears to be the exception.
Good luck. Apologies for the long post... I almost never post on anything, this one caught my eye looking for something else. All the best.
|
|
|
|
|
Hi all,
I'm hoping someone can help me out with an algorithm question I got stuck on, while contemplating optimal scheduling algorithms (as one does lol).
Consider a basic task scheduling system, where there's a queue of "Tasks" that need to get done, a pool of "Workers" that can execute work (one at a time), and a scheduler that pulls work form the queue and assigns to the workers in some fashion.
( [Task1] [Task2] [Task3] ... [TaskT] ) ---> [Scheduler] ===> ( [Worker1] [Worker2] ... [WorkerN] )
I've been thinking about various optimal scheduling algorithms for such a system, with various parameters.
For this discussion, let's assume:
- The work is uniform (all Task units are exactly the same).
- "Optimal Scheduling" just means "If I add a bunch of work to the queue, all of it will be completed ASAP."
The Trivial Case
If, in addition to tasks being uniform, all workers are perfectly uniform, it's easy to see that assigning the work to the first available free worker is optimal, and that the scheduler can just be a dumb round-robin allocator of work.
The Heterogeneous Worker Case
Suppose we have an added constraint: Not all workers are the same; they take different amounts of time to perform a work unit. Maybe they run on a heterogeneous fleet, and some are on better hardware....
In that case, if we want optimal scheduling, we can do so greedily, by always assigning to the worker that will become available the soonest given one more unit of work (i.e. "store workers in a priority queue sorted by 'when it will be done with all its work, given one more unit of work'")
The Heterogeneous Worker with Scheduled Work Case
Ok, THIS is the one I am stuck on.
Suppose, in addition to the workers being different, we ALSO have a constraint where each unit of work becomes available at a specific time t into the execution.
The aforementioned greedy approach won't work anymore. Consider this example:
Workers:
- W1 takes 8 minutes to finish a work item.
- W2 takes 10 minutes to finish a work item.
Work:
- Task1 is available immediately (t = 0)
- Task2 is available one minute in (t = 1)
With the greedy algorithm: T1 will be assigned to W1, and T2 will be assiged to W2 one minute in, resulting in all work completing after 11 minutes.
However, the optimal solution is, T1 gets assigned to W2, and T2 gets assigned to W1, making T1 the long pole, and allowing the work to complete in only 10 minutes.
Intuitively, it kind of feels like this has to become a search/backtracking problem, perhaps with heavy pruning of nonsensical choices, but... is there a simpler solution I'm missing? I keep getting the sense that there's a viable DP approach, if we're generous with things like declaring all times are integers, and throwing everything at the slowest worker is guaranteed to take less than some reasonably small amount of time...
... or maybe there IS a greedy solution, and I'm just not seeing it...
Any thoughts/direction here?
|
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
