Knapsack-similar problem

Hello there,

I've been struggling with this problem for a while now, and this seems a good place to ask it. My mathematical knowledge is a bit rusty, so I'm turning to others for help.

This problem is similar to the knapsack issue, in such that I need to find the optimal way to fill a box with items.

Each item has the following properties:
- There's a price for it
- It's got weight
- There's a limited supply of it.

The box needs to be filled according to the following requirements:
- There's a maximum total price set
- There's a maximum total weight set
- At least half of the available items must be used at least once

As you can see, there's quite some limitations to this problem, but, still solvable I think. It's just been a while since I last solved an algorithm like this.

Anyone got any ideas?
[930 byte] By [Werelds] at [2007-11-20 11:42:34]
# 1 Re: Knapsack-similar problem
Just write the whole thing as an integer linear program (ILP) and use a solver to solve it. I think the easiest would be to take binary variables that indicate whether a particular item is included or not.

If the problem is reasonably large, you may have to come up with some heuristic to find a good solution.
D_Drmmr at 2007-11-10 3:52:23 >
# 2 Re: Knapsack-similar problem
If there is large data, then use genetic programming. That gives one of the best results. You can search for GA (genetic algorithms) fr knapsack in the web. If its smaller data, then try to use ILP as drmmr pointed out above.

Check for each condition , as every item is loped through. To find the minimal condition , its best to use GA and find the optimum of 5-10 runs.
Charu0306 at 2007-11-10 3:53:23 >