|
Yes, I thought about that algorithm for my purpose.
But the two targets are different: in the knapsack problem you must maximize a value minimizing a cost; the value and the cost are two different quantities.
In this case the value and the cost are very related and you have to minimize the value constrained it is more than a given quantity.
Maybe I can apply the same algorithm, but I cannot see how to reduce my problem to the knapsack's one.
|
|
|
|
|
It may be overkill but you can easily write it as an integer linear program:
minimize h.x
st.
h.x >= minheight
for all i: x[i] is boolean
Where h are the heights of the brights, x are boolean decision variables deciding for each brick whether to take it or not, minheight is the minimum height that must be reached, and . is the dot product between two vectors.
With just a little coding effort, you can make solvers like GLPK or Gurobi solve that.
Of course it can be solved with DP, but it will be at least an O(height*#bricks) time algorithm where height is the final height, and realistically you'd have to go a bit higher up to some guessed upper bound.
|
|
|
|
|
correct
thanks for the pointer to GLPK and Gurobi
|
|
|
|
|
Hello !
Can you mathmaticiens, help me ! I'm stuck for weaks to understand this;(least squares conformal mapping)
In the file uvedit_parametrizer.c (in blender or any src code) this part of code :
/* angle based lscm formulation */
ratio = (sina3 == 0.0f) ? 1.0f : sina2 / sina3;
cosine = cosf(a1) * ratio;
sine = sina1 * ratio;
EIG_linear_solver_matrix_add(context, row, 2 * v1->u.id, cosine - 1.0f);
EIG_linear_solver_matrix_add(context, row, 2 * v1->u.id + 1, -sine);
EIG_linear_solver_matrix_add(context, row, 2 * v2->u.id, -cosine);
EIG_linear_solver_matrix_add(context, row, 2 * v2->u.id + 1, sine);
EIG_linear_solver_matrix_add(context, row, 2 * v3->u.id, 1.0);
row++;
EIG_linear_solver_matrix_add(context, row, 2 * v1->u.id, sine);
EIG_linear_solver_matrix_add(context, row, 2 * v1->u.id + 1, cosine - 1.0f);
EIG_linear_solver_matrix_add(context, row, 2 * v2->u.id, -sine);
EIG_linear_solver_matrix_add(context, row, 2 * v2->u.id + 1, -cosine);
EIG_linear_solver_matrix_add(context, row, 2 * v3->u.id + 1, 1.0);
row++;
(sparsematrix) prepares a matrix.
what kind of eqaution is getting solved, Thanks!
|
|
|
|
|
Find optimum rectangular size of the box to pack all the small rectangular boxes
|
|
|
|
|
Hi Andrew and thank you very much for your library !
I have a little question for your concerning the BlobCounter method, what is its principle ?
Thank for advance
Vincent
|
|
|
|
|
You should post your question as a comment to the article it refers to. It's unlikely the author of the article will come here and answer, as there will not be any notification of your question.
selfish adj. Defines someone who does not think of me.
|
|
|
|
|
I would like to share some interesting results of playing with the N-Queens problem solver. The following plots represent distribution of the solutions number depending on the arrangement of a subset of queens. This distribution is built by iterating the possible permutations of such a subset and counting the number of all solutions containing the current permutation (i.e. by solving N-Queens Completion Problem for each permutation).
In this particular case, subset consists of three queens that occupy the first three adjacent columns and only the permutations without overlaps (no one attacks each other) are enumerated. The subset length affects the resolution of the plot but not the general nature of the distribution.
plots_img
plotly_link
|
|
|
|
|
If you want to offer this sort of information then you should write a proper article. The forums are more for technical questions.
|
|
|
|
|
OK! I just thought that amount of information I have at the moment is not enough for a new article
|
|
|
|
|
You can always post it as a Tip if there is not enough for a full article. But either way, it will be more accessible there than in the forums.
|
|
|
|
|
I am having difficulty figuring out how to go about creating a dialog box which, when the user clicks the OK button, if that user hasn't answered all the questions in the dialog, then an error message should appear and reshow the dialog (either with or without the selections made previously).
My original solution was something similar to this:
show dialog box
while (!allAnswered) {
if (OK clicked) {
if all questions have answers then allAnswered=true
else
show error message
show dialog box again
end if
end if
loop
Each of the questions contain a drop-down box with the first choice being empty. So, if the drop-down has the empty string for the result, then I know that it hasn't been answered.
However, I wasn't sure if I was performing the if and while in the correct order because it seemed that it wasn't. Could someone please confirm whether I have the proper algorithm or what I need to do to fix it.
Chris
|
|
|
|
|
I suggest doing the checks within the dialog box so you won't need a loop at all. If it's WinForms then it could look like this:
In the "calling" Form:
private void ShowQuestionsDialog()
{
using (QuestionsForm form = new QuestionsForm())
{
if (form.ShowDialog() == DialogResult.OK)
{
}
else
{
}
}
}
In the "Questions Dialog":
private void OkButton_Click(object sender, EventArgs e)
{
if ()
{
DialogResult = DialogResult.OK;
Close();
}
else
{
MessageBox.Show("Please answer all questions.");
}
}
If the brain were so simple we could understand it, we would be so simple we couldn't. — Lyall Watson
|
|
|
|
|
A common method is to show the dialog only once (initial) and perform the checks in the OnOK handler.
If all has been answered, close the dialog. Otherwise, show the error message box, optionally reset the selections and return from the handler which should let the dialog stay visible and active.
A more specific answer requires knowing which GUI framework you are using. But those usually provide some kind of OnOK or OnClicked handler which by default call a function to close the dialog. Just don't call that default function and return from the handler to let the dialog be alive.
|
|
|
|
|
Could someone point me to an algorithm or something that might help me solve this problem:
I have 3 tours going to Disneyland, each of these tours need tickets for the passengers to get into Disneyland. In total I have 60 tickets and they can be distributed in this way: I have 20 tickets to share between Tour1 and Tour2. I have another 20 tickets to share between Tour2 and Tour3. I have another 20 tickets for just Tour3.
Image of ticket allocation to tours[^]
For each person that books a tour, the ticket number is reduced by 1.
I want to maximize the availability that is shown to the user when they are attempting to book any of the 3 tours
With no bookings, the Availability for each tour is:
Tour1: 20
Tour2: 40
Tour3: 40
If we now add bookings for each tour:
Tour1 Bookings: 12
Tour2 Bookings: 10
Tour3 Bookings: 10
The availability when looking at each tour INDIVIDUALLY (aka how many tickets can I book), it should return:
Tour1: 8
Tour2: 18
Tour3: 28
Image[^]
As we increase bookings, availability will be adjusted accordingly. Notice in the next example, when there are an additional 10 bookings for Tour1, Availability for all 3 tours change:
Tour1 Bookings: 18
Tour2 Bookings: 10
Tour3 Bookings: 10
The availability when looking at each tour INDIVIDUALLY (aka how many tickets can I book), it should return:
Tour1: 2
Tour2: 12
Tour3: 22
Image[^]
I'm sure someone has already come up with an algorithm for this... could someone point me in the right direction? Please?
modified 5-Oct-17 10:01am.
|
|
|
|
|
I would do it like this :
Assuming that a Tour has more Information/Content than only the Count :
- you have for each Tour an Array (or better a List) with the availible Tours and one with the booked Tours
- if you book one Tour you move it from the Availible_Tours to the Booked_Tours
- the other way round it you free a Tour
If you only need the Count you can work instead of this only with Integer-Variables.
|
|
|
|
|
You need to go "deeper"; and think "allocation" or "reservation" system.
You need "instances" for each ticket (60); tour (3); and "seats" (20;40;40).
A "booking" links a ticket with a passenger / seat.
Iterating over these "lists" of bookings, seats, tours allows you to know at any time what's what.
Draw a picture; or think of a flight seat reservation you make yourself.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Hi,
Let's say, I have an XML file that looks like this.
<donors>
<donor>
<donorid>1
<name>abc
<amount>$50
<donor>
....
and I have a table that looks like this:
Relation Name
-------------
Donor
Columns
-------
DonorID - bigint
DonorName - nvarchar(100)
DonationCeiling - float
I want to get all of the donor names and amounts from the xml and compare them against the maximum amount allowed. I want to remove all donors from the xml whose donation has exceed the ceiling.
I can do this.
XmlNamespaceManager nsmanager = new XmlNamespaceManager(reader.NameTable);
nsmanager.AddNamespace("donor", "www.mydomain.com/xmlns/donor");
nsmanager.PushScope();
XmlDocument doc = new XmlDocument();
doc.Load("donors.xml");
//Select and display the value of all the ISBN attributes.
XmlNodeList donorIds;
XmlNodeList donationAmount ;
XmlElement root = doc.DocumentElement;
nodeList = root.SelectNodes("/donors/donorid", nsmanager);
Is there a way to retrieve all xml node values from two different xml nodes using one xml path expression into one data structure. For instance, get all donor Ids an donation amount as a key-value list in one data-structure making a single call to root.SelectNodes
Once the donation ids and donations amounts are retrieved, even if they are retrieved as two separate XmlNodeLists, what is the most efficient way to compare these values to the DonationCeiling values returned from the Donor table.
The select query to the Donor table would look like this:
string sql = "Select DonorID, DonationCeiling from Donor where DonorID in ('" + (why can't we just pass the whole XmlNodeList as one data-structure here, without having to loop-through and build the list of DonorId's from the XMLNodeList + "') ;
recordset.ExecuteSQL(sql) ;
After the sql returns the recordset, is there an efficient way to compare the DonationAmounts in the XmlNodeList to the DonationCeiling amounts returned from the Donor table without having two nested loops.
int donorId = Convert.ToInt32(donorIds[0].InnerText) ;
while (!recordset.EOF) {
for (int i=0; i < donorIds.Count;i++) {
if (Convert.ToInt32(donationAmount[i].InnerText) > recordSet.Fields("donationCeiling").Value (should not have to cast to string and then to an integer - the compiler should automatically determine the type based on the returned value from the database column) {
// remove donor node from xml file
}
}
}
Is there a way to do the above without two loops?
Thanks for the time you might spend trying to figure this out. If you can't, that is ok, I have not figured it out so far. Maybe, there is no other way.
Thanks,
Saad
|
|
|
|
|
Upload "both" to "tables" (you admit to at least one) and use SQL.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
I've written a 6502 assembler (for Commodore machines) and one of its features is conditional assembly, like this;
ifdef var1
<some code>
else
<some other code>
elseif
So if var1 is defined then <some code=""> is assembled, else <some other="" code="">. However I want to expand this by allowing nested conditional assembly, like this:
ifdef var1
ifdef var2
<some code>
else
<some other code>
endif
else
<yet more code>
endif
Basically the way my assembler works at the moment is if the 'ifdef' condition fails (the variable is not defined) then all of the code following it (until the corresponding 'else' directive) is ignored. It's the 'corresponding else' part which is the problem here. How do I determine which 'else' corresponds with which 'ifdef'? Please note that I can't use the code indentation to determine which 'level' the directives are on. In real life, all of the code will be in the first column (no indentation at all) as my assembler needs directives to be in the first column.
I don't need specific code as such, I'm more interested in an algorithm for this.
In case you're interested, here's my assembler:
www.ajordison.co.uk
modified 28-Sep-17 6:16am.
|
|
|
|
|
The common method for processing such nested commands is using a stack. If you encounter a condition, you push it onto the stack which holds the required information like type (if) and evaluated result. Upon an else, you modify the current stack value accordingly (e.g. by setting an else flag), and upon an endif you pop (discard).
|
|
|
|
|
Yes this is the approach I tried first, but I still had the same problem when I hit an 'else', i.e. which 'else' is it?
|
|
|
|
|
It is the else for the current (top of stack, recent) if.
|
|
|
|
|
|
Hello,
I have a problem with finiding soultion to my product configurator. I'm looking for algorithms that could help me with matching similar datas. The problem is all of entries might be even unique cause they are insert by different people and they are wishes of different clients. Generaly product has option that client can choose from LOV but each option can be replaced by manualy added text. For example one product can have 70 unique values and other 400 and only 5 are values of the same atribute and only 3 are the same values but only 1 is described in exactly the same words. I'm not looking for exact solution, only for tips what algorithms could be helpfull.
Example values from one contract only(they are not describing the same thing, just wanted to show what different type of values I'm talking about):
- 81.0PA KNEITZ Sylby Silbergrau 65726598 / add 5 meter roll to contract
- 411.N015 System cable with a plugin connecting the 19 "box to the printer
One thing i can match values is number before "." cause it places value in group, but there can be multiple entries in one group or there could be none.
So at the end i would need to get 3-5 the most likely similar values to the entered one.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
