|
I'm not entirely sure what to even Google for this particular algorithm, so any insight would be much appreciated.
The following is the problem I need to solve:
Say I have a list of many raw items, with some repeats (the number doesn't matter, just assume it's more than three or 4. It could be several hundred, it could be 5).
I have ANOTHER list of possible combinations of those items. We'll call these recipes. Each recipe can be created out of 3 of the other items.
The algorithm I need to create will do the following:
* Determine which recipes can be created out of the list of raw items.
* Determine the OPTIMAL combination of recipes. That is, I want to minimize the number of remaining items.
Yes, I could do this the brute force way - if I wanted my program to run all night. I KNOW there are implementations of this algorithm that will run in mere seconds.
It has been 6 years since I took my CS class on algorithms, so I no longer remember what this is called. Doesn't it have something to do with Hamiltonians? Consequently, it's hard to search Google for it
If you remember what this is and/or can point me the right direction, I'd appreciate it!
More Info
This is a problem I've set for myself simply to re-develop these skills. This is not homework or work, I just want to figure out how to do it.
Also, this actually IS a way to figure out how to make real food recipes. I have a game I play where I can get lots and lots of raw ingredients, and I can make recipes out of those ingredients. I've gotten sick of referring back to the list of recipes, so I wanted to make a program that will do the crunching for me. I figured this would be a perfect opportunity to use to remind myself how to solve these types of problems.
The early bird who catches the worm works for someone who comes in late and owns the worm farm. -- Travis McGee
|
|
|
|
|
You might be looking for the Simplex algorithm. I think the restriction is that the combinations have to be linear to be able to use it. I'm assuming that since it's called "linear optimization".
Save an endangered species. The American Engineer.
|
|
|
|
|
That's it!
Thanks!
I don't know if this problem is even solvable - seems so simple, but then, so does the Traveling Salesman. I suspect this problem is probably NP if it doesn't have sufficient initial conditions. But at least I know where to look now
The early bird who catches the worm works for someone who comes in late and owns the worm farm. -- Travis McGee
|
|
|
|
|
In .Net the Image class has a GetThumbnailImage method, which returns a thumbnail image of the image in question. Now I know next to nothing about math, but can anyone suggest a good resource which explains how this thumb nailing process works?
Me: Can you see the "up" arrow?
User:Errr...ummm....no.
Me: Can you see an arrow that points upwards?
User: Oh yes, I see it now!
-Excerpt from a support call taken by me, 08/31/2007
|
|
|
|
|
|
Interesting tool - unfortunately it only shows that the .Net funtion wraps a GDI+ funtion:
internal static extern int GdipGetImageThumbnail(HandleRef image, int thumbWidth, int thumbHeight, out IntPtr thumbImage, Image.GetThumbnailImageAbort callback, IntPtr callbackdata);
Me: Can you see the "up" arrow?
User:Errr...ummm....no.
Me: Can you see an arrow that points upwards?
User: Oh yes, I see it now!
-Excerpt from a support call taken by me, 08/31/2007
|
|
|
|
|
That method is used to define a status object. It that calls another function, but it still might be pointing to a wrapper.
|
|
|
|
|
for a component we are using we need a color to be converted to a hex number (this is no problem my college wrote the code for it) but now we need that number (wich is stored in a sql db) to be converted back to a color (for displaying purposes)
this is the code to convert a color to number:
Dim R As Byte = &HFF - color.R
Dim G As Byte = &HFF - color.G
Dim B As Byte = &HFF - color.B
Dim co, cn As Integer
co = R + 256 * G + 256 * 256 * B
cn = &HFFFFFF - co
Return cn
anyone know how I can 'revert' this conversion so that I get the color back
If my help was helpfull let me know, if not let me know why.
The only way we learn is by making mistaks.
|
|
|
|
|
have a look at Color.FromArgb()
TDDragon wrote: The only way we learn is by making mistaks
You can also learn from reading documentation.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Luc Pattyn wrote: have a look at Color.FromArgb()
that was the first thing I tried but it doesn't return the correct color
If my help was helpfull let me know, if not let me know why.
The only way we learn is by making mistaks.
|
|
|
|
|
TDDragon wrote: it doesn't return the correct color
if you create a Color from its RGB components (within their valid range) and then extract
its components again, you get the same RGB values you started with. This proves nothing
is wrong with FromArgb().
If it does not work for you, you did something wrong elsewhere. Why does your code invert the
color components (0xFF-...)? Did you forget to invert them a second time?
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
well we are working with a component (datawindows) and in order to get that component to display the same color as was picked in .NET we need to convert them (that is what the above code does).
But now I have to display the color that has been saved to the db (in this converted state) in .NET. And that is where I'm stuck.
The problem is that I can't get the RGB and A extracted back from the converted integer
maybe an example would help
I used the color red for this one:
color.toargb(color.red) = -65536
put red true the conversion for the component and we get: 255
conversion: (255-255)+(256*(255-0))+(256*256*(255-0)) = 16776960
16777215-16776960=255
now getting the number in bold back isn't a problem the problem is that I don't know how to get R,G and B back from the above formula.
once I have these it's indeed a simply putting them thru the fromargb methode
hope this clears things up a bit
If my help was helpfull let me know, if not let me know why.
The only way we learn is by making mistaks.
|
|
|
|
|
I am using C# syntax here:
So what you are saying is you have a hex integer c=0x00bbggrr where rr,gg,bb are the
255-complement of R,G,B and you need to figure out the values for R, G and B?
int r=c%255;
int b=(c>>8)%255;
int g=(c>>16)%255;
Color col=Color.FromArgb(255-r,255-g,255-b);
BTW there is no need for magic constants such as 16777215 (which is 0x00FFFFFF)
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
somehow that doesn't work I think that this line of code (from the conversion) is the cause off all this trouble:
co = R + 256 * G + 256 * 256 * B
if I use you're code I keep getting 0-values for R,G,B nomatter wich color I'm using
Luc Pattyn wrote: BTW there is no need for magic constants such as 16777215 (which is 0x00FFFFFF)
I know but on paper it's easier to look at the number
to make it easier to read here is the entire code again
Dim R As Byte = &HFF - color.R
Dim G As Byte = &HFF - color.G
Dim B As Byte = &HFF - color.B
Dim co, cn As Integer
co = R + 256 * G + 256 * 256 * B
cn = &HFFFFFF - co
Return cn
'cn' is the value stored in the db and also the value that needs to be converted back to a color
If my help was helpfull let me know, if not let me know why.
The only way we learn is by making mistaks.
|
|
|
|
|
if something does not work properly, you need to debug it, which means test a simple
case and look at intermediate values to find out where exactly it starts to go wrong,
then fix that.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
done that, still can't figure it out. Anyway I discused the problem with my boss and we'll just add a column to the db with the arg (vb.net style) value in it and use that one so my problem has been solved well at least worked around it
thank you for you're time
If my help was helpfull let me know, if not let me know why.
The only way we learn is by making mistaks.
|
|
|
|
|
TDDragon wrote:
<br />
Dim G As Byte = &HFF - color.G <br />
Dim B As Byte = &HFF - color.B <br />
Dim co, cn As Integer <br />
co = R + 256 * G + 256 * 256 * B<br />
I'm not sure about the promotion rules in VB (that ugly stuff is VB? ) But in C and C++ by declaring R, G, and B as "byte" the arithmetic on the right of "co = " would be performed as byte and then promoted to int to be stored in co. If that is the case, you're getting overflow and wrap around.
Save an endangered species. The American Engineer.
|
|
|
|
|
didn't think of that but just tested it and there doesn't seem to be a problem with it (calculated it manualy (yes I still know how to do that )) and compared it to what is storred in co and in cn
anyway we solved our problem by just storing the argb value of the color into the db in a new column (it's a work around but it works so... (this isn't something we wanted to loose time over))
thank you anyway
If my help was helpfull let me know, if not let me know why.
The only way we learn is by making mistaks.
|
|
|
|
|
TDDragon wrote: anyone know how I can 'revert' this conversion so that I get the color back
Speaking in VB because that's what you have...
Function GetRValue(ByVal nColor As Long) As Long
GetRValue = nColor And &HFF&
End Function
Function GetGValue(ByVal nColor As Long) As Long
GetGValue = (nColor \ &H100&) And &HFF&
End Function
Function GetBValue(ByVal nColor As Long) As Long
GetBValue = (nColor \ &H10000) And &HFF&
End Function
|
|
|
|
|
Hi all,
last days I'm trying to stablish a priority dinamically. The objective is to determine which object is the best option to be chosen every cycle execution, and then operate with it.
The objects are mashines. Some parameters (like consumed energy) affect directly the priority, others (like reaction time, non stop activity time...) affect inversely Proportional, other parameters have to have some fixed values (like steps in the process) and other are bool (like permission).
I have it more or less clear with the factors that have to go multiplying, dividing and so on... but I don't find any formule that gives me a desirable result.
More or less is something like:
Permission * Already_Activate * ((Energy / (Reaction_time * Non_Stop_Time)) + StepValue [Actual]).
This is a simplified example (actually I have 10 different parameters, some of them variable during the process), I hope you can understand what I mean.
Does anyone know any web where the creation of formules for dinamically calculate priorities or parameters is explained?
Or give me some tips, methodes to find it out by myself.
Thanks
Greetings.
--------
M.D.V.
If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about?
|
|
|
|
|
Nelek wrote: dinamically
We understand your formula...but I can't understand how you wan't to 'dinamically ' change the parameters.
You have:
priority=f(par1, par2, par3,...,parN);
where f mixes that parameters with '* ' or '+ ' . This depends only on the logic of that parameter and only you can prepare f(...) .
Now, if I well understand you want to change the output of the function f(...) (ie the priority ) using the same parameters. This means that you need some extra parameters (we can call they as calibration-parameters): calib1 , calib2 ...calibM . In this case:
priority=g(par1, par2, par3,...,parN, calib1, calib2...calibM);
The function g is more complex from f (you can for example implement it as a FIR/IIR filter).
The problem now is how change the calibration-parameters calib* (par* are constants).
Then you need a calibration step. This to learn how set calib* values.
It is not looking very very simple ... but at the same time, not so hard
Russell
|
|
|
|
|
First of all, thanks for your answer. I know that is quite extrange, maybe with a little more info...
The fact is that the parameters won't change, I mean... they will be always the same parameters on the formule, but their value (at least in 70% of the parameters DO will change with the time).
Some of the parameters will have a constant value in every mashine, but others will change their value depending on the moment in which they are used. For example (taking the same parameters as above)
Permission can be 0 or 1 depending of the user that comand the mashine, if he wants the mashine to be available to interact with my program or not, or in some critical parts of the process where they have to work at 100% independantly of what happens around.
Already_Activate can be 0 or 1, this parameter will be set/reset by my programm.
Energy depends on the concrete mashine, from one mashine to another may be different, but always constant for every mashine.
Reaction_time is mashine dependant, like the energy. Is the time between my command and the answer to that command.
Non_Stop_Time is variable for every case, it is the time between the last time that the mashine had a command from my programm to the actual moment.
StepValue [Actual] can be variable with the time, but according to a relation of fixed values (the array). In some minutes will have a value, in other moments another value and so on.
Because of that the output of the function will be variable with the time. And this value (priority) is the value that I will check in a for every certain periode of time to choose the mashine that has to receive my commands or specifications. The higher the priority is, has more oportunities to be selected.
The concrete problem is that the formule I have to create should take care of all the parameters with fixed value, the actual moment and the values of the parameters that change with the time.
Trying to write similar to your answer I need a function more o less like that:
Priority = F (par1, par2, ..., parN, f1(t), f2(t), ... fN(t));
I already know (more o less) where the parameters have to be placed (numerator, denominator), but my problem is to connect the terms. I mean... for example:
the boolean values are to allow, discard some terms, because of that are out to multiply the term: Permision * (....) would be like: if (!Permision) {continue;} in the first line of a while (...) or a for (...), but...
I don't know if it's better to use only one fraction and add, substract, multiply... the terms of numerator/denominator. If it's better to use more fractions adding every partial result... If it's better to use only multiplications and divisions and then normalize to a fixed interval...
I would like to have a priority with a similar value with mashines of similar properties, but the tests that I have made give me results that I don't like (differences to big between very similar cases, or too small with very different cases... things like that)
It is the first time I have to do something like this. Im not bad with the algorithms, but this is killing me
Is there any procedure to reach such a thing? or is just empiric with tests and failures?
Greetings.
--------
M.D.V.
If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about?
Help me to understand what I'm saying, and I'll explain it better to you
|
|
|
|
|
I'm quite sure that to solve this problem you have to solve it in 2 steps:
Step 1:
Nelek wrote: Permission can be 0 or 1 depending of the user that comand the mashine, if he wants the mashine to be available to interact with my program or not, or in some critical parts of the process where they have to work at 100% independantly of what happens around.
Already_Activate can be 0 or 1, this parameter will be set/reset by my programm.
Energy depends on the concrete mashine, from one mashine to another may be different, but always constant for every mashine.
Reaction_time is mashine dependant, like the energy. Is the time between my command and the answer to that command.
Non_Stop_Time is variable for every case, it is the time between the last time that the mashine had a command from my programm to the actual moment.
StepValue [Actual] can be variable with the time, but according to a relation of fixed values (the array). In some minutes will have a value, in other moments another value and so on.
There are what we called Parm1 , ... parmN (parm* )
Now fix a 'standard ' output:
priority_Std=F_std(parm1, parm2, ...parmN);
This step is quite simple, you gave good ideas on how mix this parameters to obtain the right output. The only problem is to choose the 'standard' output that you want to obtain (priority_Std).
I think that it could be the more probable output..
Step 2)
You will have
priority=priority_std+F_Variation(parm1, parm2, ...parmN, calib1, ...calibM);
M!=N in general (I hope that M<N)
where calib* is the calibration parameter at that time (you correcly refer this to a function of time), this mens that priority is a function of time. The parameters parm* mest be taken as constants.
Write the function F_std is quite simple...not the same for F_Variation !
One way is this
F_Variation=SumOn(i,j)(parm_i*parm_j*calib(i,j))
Now you have simply to find this calib values according on what priority_variation you want in different conditions.
Russell
|
|
|
|
|
I have to read it slowly because I don't get correctly what you mean (I'm not english speaker), but I think I have an aproximated idea.
Thanks a lot for your help. I didn't thought about doing it in two steps. I was combining all in only one step and that was to become crazy :P
P.S. how about your template?
Greetings.
--------
M.D.V.
If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about?
Help me to understand what I'm saying, and I'll explain it better to you
|
|
|
|
|
think also to this
parm(N+1)=time
in step 1 it values 0, so it comes only in the second step.
Nelek wrote:
P.S. how about your template?
not well
The compiler doesn't match well my specialization member function with the general declaration.
Give me 2 or 3 days to find the way to tell him that they are the same thing;)
thanks
Russell
|
|
|
|
|