Programming Forums - View Single Post - Has anybody done a knapsack problem in VB-- I'd like your script!

scm007 · Nov 3rd, 2006, 3:53 AM

Sort of. Imagine an x,y,z space filled with points. I need to find a solution set of points whos average falls within a box of some dimensions. Basically I'm going to take a seed set of values, then recursively determine the best move and ... well it would be better if I explained it a different way. Say there are 2000 points.

Take a seed of 1000 points (x,y,z), assume the average is outside of the defined box.
There are 3000 possible moves to make. Adding 1 of 1000 points, subtracting 1 of 1000 points, or swapping 1 point in the set for 1 of the 1000 points outside of the set.
Pick the move that minimizes the value relative std. deviation
sqrt[(x/x_desired)^2 + (y/y_desired)^2 + (z/z_desired)^2]
the _desired variables would be the coordinates of the center of the box.
Recurse until the average falls within the box.
Or if the function gets stuck, reseed.

Help?

Nov 3rd, 2006, 3:53 AM	#3
scm007 Newbie Join Date: Jan 2006 Posts: 27 Rep Power: 0	Sort of. Imagine an x,y,z space filled with points. I need to find a solution set of points whos average falls within a box of some dimensions. Basically I'm going to take a seed set of values, then recursively determine the best move and ... well it would be better if I explained it a different way. Say there are 2000 points. Take a seed of 1000 points (x,y,z), assume the average is outside of the defined box. There are 3000 possible moves to make. Adding 1 of 1000 points, subtracting 1 of 1000 points, or swapping 1 point in the set for 1 of the 1000 points outside of the set. Pick the move that minimizes the value relative std. deviation sqrt[(x/x_desired)^2 + (y/y_desired)^2 + (z/z_desired)^2] the _desired variables would be the coordinates of the center of the box. Recurse until the average falls within the box. Or if the function gets stuck, reseed. Help? Last edited by scm007; Nov 3rd, 2006 at 4:43 AM.