|
Thanks for the advice.
The book did not help but I found a very good tutorial on the net. Now I can find the rule for a set of given points
Thanks again
|
|
|
|
|
pHysiX wrote: The book did not help but I found a very good tutorial on the net.
It would be very helpful to others trying to figure out how to solve this type of problem if you posted a link to the tutorial that you found.
Thanks,
BillW
|
|
|
|
|
I am trying to find a solution/algorithm which can find a closest match to a given number. For example you were given 100 and you have 10 records in a table in following order:
1. 28
2. 35
3. 43
4. 23
5. 35
6. 78
7. 8
8. 5
9. 12
10. 33
I need to find sum of what combination of these records matches close or equal to 100 (but it should not exceed). One record can be used only one time. I am looking for an algorithm which can find the combination quickly. In this example I have only 10 records to search. But there can be more records. Number of records to search increases regular way of checking combinations takes more time. I really appreciate if anyone can provide me an algorithm which can do this type of job quickly.
Thanks in advance
Sam
|
|
|
|
|
Hi,
this seems like an extension to the "knapsack problem" (fill a given space with as
many objects as possible from a given collection); I suggest you google it.
|
|
|
|
|
What if you first sorted the set of numbers, yielding:
{78, 43, 35, 35, 33, 28, 23, 12, 8, 5}
Then search the set for the largest number that is less than or equal to 100, subtract that from 100, search the set again for the largest number that is less than or equal to 22, subtract that from 22, etc. So, 78+12+8 is the closest you can get to 100.
Or am I way off base?
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
No you're not. What you could do is add the largest to the smallest and save it subtract 100 and save it. Stop if 0. Then use the second smallest and compare to the last result. Save the smaller one. If it becomes negative, change the largest number and keep the current smallest number. Repeat until you get two numbers that sum to less than 100 and your previous pair are the answer you're looking for.
"Oh, what a tangled web we weave, when first we practice to deceive." - Sir Walter Scott
Web - Blog - RSS - Math - LinkedIn - BM
|
|
|
|
|
I don't think this is a good idea. But I do appreciate your input. Ex: Assume that I had {78,43,35,35,28,23,8,5,4}. As per your explanation I get 78+12+8 = 98. But if I add 78+12+5+4 = 99 (this is closest to 100).
Let us take this way:
In our warehouse we process Pallets quickly (They are packed and ready to ship). Loose items go through multiple stages before they get out of door. So, they take time. We need to satisfy our customer. For example customer requested 100 pens. We got pallets (and partial pallets) like 78,43,35,35,23,8,5,4 (I am giving small numbers here for an example. We have pallets with minimum quantity above 100). With our current process we are going the same way you explained here and ship 98 first. Remaining 2 takes couple of days (or weeks) before they get out of door. If the difference is a small number not much problem. This loose quantity adding together putting more load on manual process and causing more delays (finally unhappy customer). You may ask how much difference 2 makes here (This is only an example. We get difference in 2 to 3 digits depending on item). I can’t lock tables for a long time trying to find best match for each request. So, I need to find best closest match quickly and proceed.
Thanks for your help in Advance.
Sam.
|
|
|
|
|
The knapsack problem is NP-complete, meaning there is no upper bound to the time you
need to find the optimal solution. All simple attempts may seem reasonable, but are
not guaranteed to lead to the real solution.
Cant you simplify the task and take whatever combination of (partial) pallets that
slightly exceeds the requirement and remove a few items from one of them ??
(If so, you soon would not have that many partial pallets either!)
|
|
|
|
|
The issue is probably the number of partial pallets you need to search. If you have N partial pallets then a completely brute force approach requires searching roughly 2^N combinations. If N was like 8 as in your example then this is only 256. If N was likely to stay below say 20 then you only have to search 1e6 combinations, this can be implemented with about 4e6 integer ops, coded in a decent compiler should take a few milliseconds on a modern machine.
Of course, your problem may be that your environment is not conducive to numerically intensive calculations.
If N gets large, then that is a different problem, N = 40 requires an exhaustive search of 1e12 combinations... There are probably better sub-optimal algorithms that you could use in this case.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
samv98 wrote: Assume that I had {78,43,35,35,28,23,8,5,4}. As per your explanation I get 78+12+8 = 98. But if I add 78+12+5+4 = 99 (this is closest to 100).
Of course, but 4 was not in your original set of numbers. Had it been, I would have obviously chosen 78+12+5+4.
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
Consider the set {78, 12, 11, 11}, your algorithm gives 78 + 12 = 90 whereas the best is 78 + 11 + 11 = 100.
Even worse, consider the set {78, 35, 34, 31}, your algorithm gives 78 whereas 35+34+31 = 100.
I don't think you will find a general algorithm that does not grow at a similar rate to the brute force approach, but I could be wrong..
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
cp9876 wrote: Consider the set {78, 12, 11, 11}, your algorithm gives 78 + 12 = 90 whereas the best is 78 + 11 + 11 = 100.
Even worse, consider the set {78, 35, 34, 31}, your algorithm gives 78 whereas 35+34+31 = 100.
Fair enough. See here.
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
I think it is actually a kind of knapsack problem link[^], the bin packing problem is close but it tries to minimize the bins needed to pack all the items into fixed size bins. I'm not being picky, but the distinction could be important if the OP needs to look for approximate algorithms.
Whilst it has all the appeal of a sledgehammer, the brute force approach could be the simplest if he has sufficuent grunt for the range of N needed.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
It is. I actually programmed in VB a long time ago a very similar problem. Scarily, I still have it. One of my first programs.
I had to find the closest product to a number given the prime decomposition of the product. In other words, given N and a1, a2, … an, minimize N - a1e1a2e2…anen either in absolute value or not.
I'm not sure if I used this for resizing images or what?
I think this method is also much more complex. I can't remember if I required ei to all be greater than 1. Just checked. Nope. But I did think about modifying it for that.
|
|
|
|
|
Thank you guys for your very valuable input. I do appreciate. I read about Knapsack problem, Bin Packing Problem and Brute Force Algorithm. Unfortunately I have no clue about the logical flow for any of those to try. I did find few links when I searched on Google about those. But they are not very explanatory. On one site they provided demo for Knapsack. It was very impressive. I tested with 100 items and it provided results in 0.028 seconds. But they did not provide source code or any kind of logical flow. I am leaning more towards Brute Force solution and then Knapsack. Can any of you point me to correct path where I can get a flow chart or source code (any language is fine except assembly language). Once again do I appreciate your valuable input.
Thanks
Sam
|
|
|
|
|
Have a look at this algorithm
http://www.netlib.org/toms/632[^]
(I hope fortran is within your definition of 'any language except assembly').
I believe this code is public domain, and is documented in TOMS (detailed ref in comments).
It actually solves a more general problem,
SUBROUTINE MKP(N,M,P,W,K,BCK,XSTAR,VSTAR)<br />
C<br />
C SUBROUTINE TO SOLVE A 0-1 MULTIPLE KNAPSACK PROBLEM OF N<br />
C ITEMS (WITH N .GE. 2) AND M KNAPSACKS (WITH M .GE. 1 ,<br />
C I.E. ALSO SUITABLE FOR A 0-1 SINGLE KNAPSACK PROBLEM).<br />
C THE PROBLEM TO BE SOLVED IS:<br />
C<br />
C MAXIMIZE VSTAR = P(1)*(X(1,1) + ... + X(M,1)) + ...<br />
C ... + P(N)*(X(1,N) + ... + X(M,N))<br />
C SUBJECT TO<br />
C W(1)*X(I,1) + ... + W(N)*X(I,N) .LE. K(I) FOR I=1,...,M<br />
C X(1,J) + ... + X(M,J) .LE. 1 FOR J=1,...,N<br />
C X(I,J) = 0 OR 1 FOR I=1,...,M , J=1,...,N ,<br />
C<br />
C WITH ALL P(J) , W(J) AND K(I) POSITIVE INTEGERS.
i.e. if you have all your partial pallettes {a1, a2, .., aN}
set W(1) = P(1) = a1, ..., W(N) = P(N) = aN
so it will actually optimally pack M orders at a time with quantities K(1) ... K(M). (This is why it is called a multiple knapsack problem.) It works with M=1 (your problem), and the runtimes apparently increase significantly as M increases.
I tried it out, using g77 on my 700MHz linux box (the only fortran compiler I have). I just wrote a simple loop to randomly generate the partial pallettes, each with a value 1 - 100, with single knapsack packing goal of 100, and ran it for 1000 problems. If you want this code let me know. The runtimes were (M=1):
<br />
N Runtime(1000 problems)<br />
10 50ms<br />
20 80ms<br />
30 100ms<br />
50 150ms
Although the runtime is not bounded (some sets of numbers may take much longer), you could play with the BCK parameter which limits how many times the algorithm can backtrack to find the best answer, I just left it set to -1 with is supposed to find the best fit. Note that as N increased it almost always managed to find a perfect match.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Thank you Peter. You shown path, I will dig deep. Fortran is not a problem. I used it around 15 years ago. But I have no problem understanding it now. Thank you everyone for your kind reply to this thread. Appreciated.
Thanks for your help
Sam
|
|
|
|
|
You have two teams broken up by gender. Each team is to do some amount of work (one day per week for several weeks). The girl's team consistently does more work as there are more of them showing up to do the work. In the end, it's not fair to just look at how much work each team did, but I can't figure out what other factor(s) I need to look at to make the results fair. For example:
Week 1:
19 girls did 42 units of work
17 boys did 37 units of work
Week 2:
20 girls did 19 units of work
15 boys did 15 units of work
Week 3:
18 girls did 20 units of work
14 boys did 15 units of work Any ideas?
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
Sorry but the question (at least for me...) is not enough clear...
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
|
|
|
|
|
If your question is which team worked harder, I'd do it like this:
Week 1:
the average girl did 2.21 units of work.
the average boy did 2.18 units.
week2:
G .95
B 1.00
week3
G 1.11
B 1.07
three week average:
1.42 units of work/girl/week
1.42 units of work/boy/week
Presumably if you kept more than 2 digits right of the decimal you'd find the numbers didn't come out identical.
--
CleaKO The sad part about this instance is that none of the users ever said anything [about the problem].
Pete O`Hanlon Doesn't that just tell you everything you need to know about users?
|
|
|
|
|
Try this (average work per worker per week):
week 1:
g 42/19 = 2.21
b 37/17 = 2.17
week 2:
g 19/20 = 0.95
b 15/15 = 1.0
week 3:
g 20/18 = 1.11
b 15/14 = 1.07
averages:
girls: (2.21 + 0.95 + 1.11) /3 = 1.423 units of work per week per girl on average
boys: (2.17 + 1.0 + 1.07 ) /3 = 1.413 units of work per week per boy on average
the difference is < .5 %, and is not likely significant.
|
|
|
|
|
If you define the average productivity as total output / total person weeks then the boys do better
Girls = 81/57 = 1.421
Boys = 67/46 = 1.457
despite the boys being behind on 2 of the 3 weeks.
Do the girls deserve to be rewarded for showing up in greater numbers and actually delivering more?
Note that this set of numbers is the basis for some sort of paradox. If the girls made one more unit in week 2, then their productivity would be greater than the boys in weeks 1 and 3, and equal to the boys in week 2, but their average productivity overall (total output / total input) would still be less than the boys!
Girls: 82/57 = 1.439
Boys: 67/46 = 1.457
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
What you have succeeded in demonstrating is that you sample size is too small to make any meaningful comparison.
|
|
|
|
|
I wasn't even going to post until I saw the mathematical curiosity that it is possible that the girl's weekly productivity could be never less than the boys, yet their overall productivity could be lower, that piqued my interest a bit. Otherwise it is not that interesting a problem.
As far as the sample size is concerned, I agree that you can't say that one group is definitely more productive than the other with the data you have. Whether this is relevant depends on the original problem - is it a race/competition or a measurement? If it was a race/competition then one group may have won. I've never heard the athlete that came second by 0.01 sec protest on the basis that because the sample size was so small that the time difference was insignificant!
If it is a competition then the rules should be set in advance!
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
This might be a bit late but you need to find out what each girl did and what each boy did, then do a frequency and find the standard deviation on that. From this you can do curves and boxplots etc to see if there really is a difference between boys and girls.
Also what is your sample size, you need at least a 25 to do any reasonable statistics etc...
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
