Knapsack

Alright quick overview

I have looked into the knapsack problem

http://en.wikipedia.org/wiki/Knapsack_problem

and i know it is what i need for my project, but the complicated part of my project would be that i need multiple sacks inside a main sack.

The large knapsack that holds all the "bags" can only carry x amount of "bags" (lets say 9 for sake of example). Each bag has different values;

    * Weight
    * Cost
    * Size
    * Capacity

and so on, all of those values are integer numbers. Lets assume from 0-100.

The inner bag will also be assigned a type, and there can only be one of that type within the outer bag, although the program input will be given multiple of the same type.

I need to assign a maximum weight that the main bag can hold, and all other properties of the smaller bags need to be grouped by weighted values.

Example

Outer Bag:

    * Can hold 9 smaller bags
    * Weight no more than 98 [Give or take 5 either side]
    * Must hold one of each type, Can only hold one of each type at a time.

Inner Bags:

    * Cost, Weighted at 100%
    * Size, Weighted at 67%
    * Capacity, Weighted at 44%

The program will be given an input of multiple bags, and then must work out combinations of Smaller Bags to go into the larger bag, there will be multiple solutions depending on the input, and the program would output the best solutions for me.

I am wondering what you guys think the best way for me to approach this would be.

I will be programming it in either Java, or C#. I would love to program it in PHP but i'm afraid the algorithm would be very inefficient for web servers.

Thanks for any help you can give

>>5
Taking the low hanging fruit eh ;)