|
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...
|
|
|
|
|
HI all,
I wanna find angle between hours & minutes needle of a clock,where i will get the time dynamically from the user.
Suppose,now the time is 12:40,i have to find angle between 12 and 8 of the clock.
Am strucked with the startup,i mean with the help of arc length and radius we can start after that bit trouble,
can anyone help me
Bye
Have a Nice Day Dudes
|
|
|
|
|
clockwise angle (of course...)
degrees = (hour % 12) * 30 - minutes * 6;
where '%' is the reminder of the integer division.
Note that you'll get negative angles too.
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.
|
|
|
|
|
CPallini wrote: degrees = (hour % 12) * 30 - minutes * 6;
where '%' is the reminder of the integer division.
The hour hand does not jump in 30 degree steps, you need to work out the location of the hour hand as it moves steadily from (hour % 12) * 30 to ((hour+1) % 12) * 30 and then subtract the minutes angle. The minutes angle (minutes * 6) looks OK unless you have to take seconds into account - then it is the same issue.
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."
|
|
|
|
|
if you have a clock that moves the hands continuously, you need to use the time in seconds to generate decimal hour and minute values and use those instead.
--
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?
|
|
|
|
|
OK, friends...
double radians =(( hours * 3600 + minutes * 60 + seconds)/21600.-(minutes * 60 + seconds)/1800.) * PI_GREEK;
the conversion to degrees, minutes,... is up to you...
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.
|
|
|
|
|
milliseconds? 
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."
|
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
