Home |
Search |
Today's Posts |
#1
Posted to microsoft.public.excel.programming
|
|||
|
|||
Knapsack Problem
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[i] = 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[i] 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[i]; 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[i].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[i]; } 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.... .................................................. .................................................. .................................................. ................ |
#2
Posted to microsoft.public.excel.programming
|
|||
|
|||
Knapsack Problem
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[i] = R.Next(1,N * N / 2);Console.WriteLine("Target: " + Target.ToString());int CurrentSum = 0;Sum(0,N,ref CurrentSum,A,Target);Console.WriteLine("done");voi d 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[i] Target)continue; CurrentSum += A[i]; Sum(nest,N,ref CurrentSum,A,Target);if (CurrentSum == Target) { Console.WriteLine(nest.ToString() + "," + A[i].ToString()); break; } CurrentSum -= A[i]; } nest--; } |
Reply |
Thread Tools | Search this Thread |
Display Modes | |
|
|
Similar Threads | ||||
Thread | Forum | |||
Colon at the end of excel file name(ex: problem.xls:1, problem.xls | New Users to Excel | |||
Started out as an Access problem. Now an Excel problem | Excel Discussion (Misc queries) | |||
problem with a conditional max problem | Excel Discussion (Misc queries) | |||
Problem when multipple users access shared xl-file at the same time, macrocode for solve this problem? | Excel Programming |