|
What's this - an easter craze on knapsack problems?
This looks like homework, in which case I guess the number of integers in the set is modest (<= say 16), in which case you can simply search all combinations and find the best.
For other comments and a more general solution see this thread: link[^]
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."
|
|
|
|
|
please tell me if there is any way to convert an array like 936 to an integer 936?
and how can i understand that the number the user inputs how many digits has?(for example 99999 is a 5digit number)
Khodadad Pakdaman
Pakdaman@CleanMail.it
|
|
|
|
|
array ?
if you mean string, use int.Parse() or int.TryParse()
if you mean a char array, first convert it to a string using a String constructor.
|
|
|
|
|
My suggestion for a beginner like yourself is to find a tutorial in whatever language you are using, one with some simple examples involving user i/o, get these working and then experiment with modifying them to do what you want.
Google on (language of choice) tutorial
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 are able to write this program please help me:
YOU KNOW THAT THE ISDN NUMBER IS A SPECIFIC NUMBER FOR EACH BOOK,AND FOR EXAMPLE AN ISDN NUMBER LIKE 964-92032-1-4 CONTAINS THIS INFORMATION:
ISDN : TheLanguageOfTheBook-PublisherCode-BookNumber-CheckDigit
the check digit number is calculated in this way,
for example for 964-92032-1-4 :
10x9 + 9x6 + 8x4 + 7x9 + 6x2 + 5x0 + 4x3 + 3x2 + 2x1 = 271
271%11=7 = Result
then the CheckDigit number should be (11-Result)
ok?
Here's the interface of the program:
Enter ISBN: 964-92032-1-4
Language: 964
Publisher: 92032
Book number: 1
Check digit: 4
This ISBN code “964-92032-1-4” is valid!
or
This ISBN code “964-92032-1-4” is invalid!
Please let me know if you understood the program well!thanks again,sorry for the english mistakes found in my text,i'm really sorry!
Khodadad Pakdaman
Pakdaman@CleanMail.it
|
|
|
|
|
Sounds like homework to me - in which case try to do it and if you run into difficulties post on one of the programming forums.
Just noticed that you have posted the same question on the Managed C++ forum. This is a BIG hint - you will get much more help here if you are seen to be making an effort yourself. If you just type your problem into the forum expecting someone else to do your work, you will not get much of a response.
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."
|
|
|
|
|
ok,dear peter,
thanks for your reccomendations,
in a simple C++ program,
please tell me if there is any way to convert an array like 936 to an integer 936?
and how can i understand that the number the user inputs how many digits has?(for example 99999 is a 5digit number)
in the case mentioned up there,i don't know how i can calculate the check digit number?because i stored the input in a string!
Thanks again for your reccomendations,
Khodadad Pakdaman,
Pakdaman@CleanMail.it
|
|
|
|
|
How about the standard C function "strtoul()" which stands for "string to unsigned long". Will that do it for you?
|
|
|
|
|
Hey. I am doing advanced maths this year and need help with quadratics.
The chapter that I am doing focuses on find a quadratic rule from a given graph or co-ordinates.
The book I am using is state approved, but does not seem to explain what to do.
My question is, can anyone make a "guide" on what to do for different scenarios.
For example, what should I do when I know one co-ordinate or when I know two co-ordinates etc.
And also, what is the quadratic rule if a graph has vertex (-1,3) and passes through (3,8)?
Thanks in advance
|
|
|
|
|
I don't think this is the place for school maths homework. Some hints:
1. read the book again
2. hopefully discover that the 'quadratic rule' is commonly called the parabola
3. google on thinge like {parabola vertex} etc
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."
|
|
|
|
|
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
|
|
|
|
|