Possible Combination of Knapsack problem and ???

Question

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

-Zack

Answer 1

So you don't really care about filling the inner bags? You just want to fit items (inner bags) into a bag (outer bag) with the additional constraint that the bag (outer bag) cannot contain multiple items (inner bags) of the same type. Right?

Answer 2

Okay, well, knapsack is NP-hard so I'm pretty certain this will be NP-hard as well (if it weren't you could solve knapsack by doing this with only one outer bag.) So for an exactly optimal solution, you're probably going to be able to do no beter than searching all combinations. So the outline of the program you want will be like

 for each possible combination
 do
   if current combination is better than best previous
      save current combination as best so far
   fi
 od

and the run time will be exponential. It sounds, though, like you might be able to get a near solution with dynamic programming.

Answer 3

Consider using Prolog for your logical programming. There's multiple implementations of it including P# on mono (.NET). Theres a bit of a learning curve, but once you get used to it, it's pretty much in a league of its own for this kind of problem solving.

Hope this helps. Cheers!

link to P#