scm007

Does anybody have a working script to solve a knapsack problem using VB? I need to use it on an Excel file and VB seems the easiest way to do so. If you have a working knapsack, or other optimization script/program I'd really like to mod it for my purposes. ThANKS!

melbolt

homework?

I'm not totally familiar with the knapsack problem, but from googling a bit it sounds like you're headed for some recursion.

you're going to have to explain the problem a little better, as far as i can tell you have a sack that can hold an unspecified amount of items. each item may come in stacks of an unspecified number of identical "brother" items? each item has a size and weight right?

the sack has a limit as to how much volume but not weight right? and you are trying to get the sack to weigh as much as possible?


the questions i have for you are:

what are your constraints? are there a specified number of items to work with or is it 0 to N number of items, each weighing 0 to N lbs and having a volume with 0 to N? I'm afraid without this info it would be pointless to continue.

I assume you will supply a two dimensional array or even better, an array of a class or struct you build. something with the given items to work with? one dimension holding the weight of the object, the other holding the volume of the object. and you will also supply the max volume of the sack(N).

what you would want to do in this situation is a recursive algorithm trying different combinations and find out which combination returns the largest weight.

will be a somewhat processor demanding algorithm but will get you your answer.

feel free to post whatever code you got and I(or we) will try to give you a hand. I'm not gonna do your homework for you

__________________
I have never let my schooling interfere with my education. -Mark Twain-

Xbox live gamertag: melbolt

scm007

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?

bl00dninja

please don't cross-post.

__________________
i put on my robe and wizard hat...

Have you ever heard of Plato, Aristotle, Socrates?...Morons.