Knapsack Problem

V

Vacuum Sealed

Hi all

I found this in a forum, can't say I recognise the language, C+ maybe, was
wondering if anyone within this NG has an idea as to how to mod it for VB
use.

Specifically, a 0-1 scenario, which I posted in another thread entitled "Mt.
Everest of Requests".

The details of what I need are listed at the bottom of this, and I am hoping
I can see it come to life...

TIA

Mick..
Knapsack solved
Before we can create a Knapsack function we need some data to test it.

All we have to do is to load an array with a reasonable set of integers to
try to make the target up from and it then calls the recursive SUM function
which tries to find a subset:

int N = 50;Random R = new Random();int Target = R.Next(1,N * N);int[] A =
new int[N];for (int i = 0; i < N; i++) A = R.Next(1,N * N /
2);Console.WriteLine("Target: " + Target.ToString());int
CurrentSum = 0;Sum(0,N,ref
CurrentSum,A,Target);Console.WriteLine("done");Sum is recursive but not
difficult to follow - it is just a set of nested for loops one per call of
the function and is based on the Loop function listed earlier.

Now as well as nest and N we also need the CurrentSum, i.e. what the
selected elements add up to, the array, and the Target value:

void Sum(int nest, int N, ref int CurrentSum, int[] A,int Target){ if (nest
= N)return; int i; nest++; for (i = 0; i < N; i++) {The CurrentSum has to
be passed by ref because it is changed by the function and this change needs
to be returned to show what the result so far is. It is also what brings all
of the loops to a stop. When we find a set of values that add to the Target
that's enough, i.e. we are looking for the first solution not all of the
solutions.

The logic in each loop is to first test to see if adding the next selected
element will take the CurrentSum over the Target. If so we simply move on to
the next element in the loop and see if this is worth considering:

if (CurrentSum + A > Target) continue;If the
current element can be added to the CurrentSum without exceeding the Target
then we update the CurrentSum and call the function to find the next element
using the next nested loop:

CurrentSum += A; Sum(nest,N,ref CurrentSum,A,Target);When this
function returns it has either tested all of the elements and failed or it
has found the correct sum, i.e. CurrentSum equals the Target and we test for
this:

if (CurrentSum == Target) { Console.WriteLine(nest.ToString() +
"," + A.ToString()); break; }If the CurrentSum is equal to the target
we print the current index and the array element that was used in the sum
and break out of the loop. Notice that once the CurrentSum is equal to the
target it stays equal to the target and all of the loops come to an end by
executing the break. If the inner loop fails to find a solution we have to
correct CurrentSum by subtracting the failed element and moving on to try
the next element in the loop.

CurrentSum -= A; } nest--; }If you run it and it finds a solution it
prints the elements of the array. If it fails to find a solution you just
see the magic word "done" - you can't always make the target up from a
subset of the values.

..........................................................................................................................................................................



Step.1

Individually, Filter/Select all rows from each Zone.

We will use Zone "N"orth for the starting example.

Step.2

Further Filter the selected "N" rows for each Dest(s)

We will use Dest "H" for this stage.

Step.3

Look at all of the rows that match the above filtering and place them into
groups where the Stacks sum to 22 & or where the Weight does not exceed
24.5t....

When a summed combination is found, place a consecutive (Groups number) in
Column "AI" so that those share the all the same Grouping, and then the next
group of 22 would have the next consecutive (Grouping number).

Then repeat for each of the remaining combinations, placing incremental
numbers for the groups to match....

......................................................................................................................................................................
 
V

Vacuum Sealed

Knapsack solved
int N = 50;Random R = new Random();int Target = R.Next(1,N * N);int[] A =
new int[N];For (int i = 0; i < N; i++) A = R.Next(1,N * N /
2);Console.WriteLine("Target: " + Target.ToString());int CurrentSum =
0;Sum(0,N,ref CurrentSum,A,Target);Console.WriteLine("done");void Sum(int
nest, int N, ref int CurrentSum, int[] A,int Target){ if (nest >= N)return;
int i; nest++; for (i = 0; i < N; i++) {if (CurrentSum + A >
Target)continue; CurrentSum += A; Sum(nest,N,ref
CurrentSum,A,Target);if (CurrentSum == Target) {
Console.WriteLine(nest.ToString() + "," + A.ToString());
break; } CurrentSum -= A; } nest--; }
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top