Please Help: Array Algorithm!!
Matt Sargent
<sear...@earthlink.net> wrote:
>I need to develop an algorithm that is similar to a classic algorithm called
>the "Knap Sack" problem. I have a book on computer alorithms, but I can't
>get it to work for me.
>
>Here's my probem.
>I have an array, example ar = Array(100,120,10,15,20,31).
Do you realize that you're creating an array with over 1.1 Billion
(yes, Billion) elements?
Matt Sargent
this:
>I have an array, example ar = Array(100,120,10,15,20,31).
to indicate the values with the array, not the dimensions of the
array. (At least I hope so.)
This simplest ways is just to take everything in order. For the 6
elements in the array, first check for an single element that equals
the total. You need to view this in a fixed font, or it won't make any
sense.
1 2 3 4 5 6
x
x
x
x
x
x
If no hits, then check for the any two elements:
1 2 3 4 5 6
x x
x x
x x
x x
x x
x x
x x
x x
x x
x x
x x
x x
x x
x x
x x
If no hits, check for any three elments:
1 2 3 4 5 6
x x x
x x x
x x x
x x x
x x x
x x x
x x x
x x x
x x x
x x x
x x x
x x x
x x x
...etc.
You get the idea. Continue the pattern and you'll hit every possible
combination.
Chamberlain, John
The knapsack problem: each possible addition to a knapsack has a weight and a value, maximize value for a given weight limit. Note that the maximum value might have a weight under the limit.
Your problem is somewhat more simple: find all combinations of elements that sum to a particular value exactly.
First Point: an algorithm to generate all possible combinations. The simplest such algorithm to understand is called the "binary" algorithm. Treat the members of your array as digits in a binary number. For example, if you have 12 elements then you have a 12-digit binary number that can range from 000000000000 to 111111111111. You need two nested loops, one outer loop to iterate the numbers, the inner to iterate the digits in each number. To know whether to add the number mask off the digit with a binary AND. Note that count of binary "numbers" will be equal to 2^(number of elements + 1)-1. For example, for a 12-element array it goes up to 2^13-1 = 8,191.
This is the algorithm for finding combinations in VB that match a sum:
lngDesiredTotal = 125 'or whatever
ctElements = Ubound(theArray)
For xCombination = 1 to 2^(ctElements+1)-1
lngRunningSum = 0 'reset the running sum
For xDigit = 1 to ctElements 'each element corresponds to a binary digit
If xCombination AND 2^xDigit > 0 Then
'this element is in the combination
lngRunningSum = lngRunningSum + theArray(xDigit)
End If
Next
If lngRunningSum = lngDesiredTotal Then
'we have found a matching combination
End If
Next
This is the most simplest, most concise algorithm for testing combinations.
Second Point: there is an easy way to make this algorithm MUCH more efficient: sort your input. If you sort your input array into ascending order then as soon as the running sum is greater than the target total then all numbers manifestly greater than the current combination can be skipped. For example, if the running sum is greater than the target total and the combination is the binary 100101100000 (=2400) then all combinations betweeen this and 100110000000 (=2432) can be skipped, thus saving 32 iterations.
Third Point: it is possible to devise many other more sophisticated strategies for increasing efficiency.
-----Original Message-----
From: Michael Hsueh [mailto:sear...@earthlink.net]
Posted At: Monday, April 26, 1999 11:39 AM
Posted To: discussion
Conversation: Please Help: Array Algorithm!!
Subject: Please Help: Array Algorithm!!
I need to develop an algorithm that is similar to a classic algorithm called
the "Knap Sack" problem. I have a book on computer alorithms, but I can't
get it to work for me.
Here's my probem.
I have an array, example ar = Array(100,120,10,15,20,31).
The number of items in the array varies almost in every situation.
I have a total, example 125.
I need to figure out which of the items in the array sum equals the total.
Of course I can look and it would be ar(0) + ar(2) + ar(3).
What I need to do is to write an alogorithm that will sum EVERY combination
of the items in the array. Example..
ar(0) + ar(1)
ar(0) + ar(2)
....
ar(1) + ar(2)
ar(1) + ar(3)
.....
ar(0) + ar(1) + ar(2)
ar(0) + ar(1) + ar(3)
....
..and so on.. If I can get the combinations of indexes, I can do the
sum, and see if the sum equals the total, Or at least find the closest
combination. If I can figure out how to output all the different
combinations of indexes, I can store the sums into another array or
recordset...and then find the closest match.
I've tried many different types of loops, but I can't figure this one out...
PLEASE HELP ME!!!
Please email me the solution and maybe reply back to the group as well, for
others if they have a similar problem.
My email address is sear...@earthlink.net
Thanks guys!
-Michael
Elocutus Plantagenet
<Jo...@CNRX.COM> wrote:
>The knapsack problem: each possible addition to a knapsack has a weight
>and a value, maximize value for a given weight limit. Note that the
>maximum value might have a weight under the limit.
Or, you could just do your own homework.
--Jekke Bladt, EBTS
===
E-Mail, News, Code, Books, Tools, Jobs, Classes
Rapidly becoming a portal for Windows-based developers:
http://www.optionexplicit.com