Return N Optimal Choices for Multiple Choice Knapsack Variation

user_4665755 0
Viewed 69

Problem

I'm trying to return N optimal answers (for an exact number I want 250). From what I understand with dynamic programming is that it will return one most optimal answer. So I believe I have to use backtracking in order to generate N optimal answers.

For the knapsack variant problem, I have a maximum weight that the combination of objects should not pass. I have 4 sets of objects, and exactly one must be chosen from each set to give the highest value without surpassing the weight constraint. Each object in the sets have a value and a weight.

The sets have 164, 201, 90 and 104 objects which means there are 308,543,040 variations to try. I have a brute force algorithm implemented but it takes forever.

Attempts At Optimization

So far, my attempt at optimizing is to preprocess the input sets by sorting by increasing weight. (lowest first). At the addition of each object, if the constraint weight is greater than the object's combination weight, then I can skip the rest of the set since all other options will not be valid. This can be run at any level of the recursive function.

I also have a minimum heap that stores the maximum values I've found. If the combination of four objects is less than the top of the heap, then it will not be added. Otherwise, pushpop to the heap. I'm not sure if I can use this to optimize the backtracking even further, since it requires all four objects to be selected. It's used more as validation rather than improving the speed.

Questions

  • Are there any other optimizations I can do with backtracking that will speed up the process of finding N optimal answers? Have I exhausted optimization and should just use multiple threads?
  • Is it possible to use dynamic programming with this? How can I modify dynamic programming to return N optimal choices?
  • Any other algorithms to look into?
knapsack-problem backtracking dynamic-programming algorithm
1 Answers

Since exactly one item has to be picked from each set, you can try this optimization:

  1. Let the sets be A,B,C,D.
  2. Create all combinations of items from sets A,B together and sets C,D together. This will have O(n^2) complexity, assuming lists have length n. Let the combination lists be X and Y now.
  3. Sort X and Y based on weight. You can use something like a cumulative array to track the combination with the max possible value under a given weight. (Other data structures might be used for the same task as well, this is just a suggestion to highlight the underlying idea).
  4. Create a max heap to store the combinations with max values
  5. For each combination in X, pick the combination in Y with the highest value under the constraint that it's weight is <= target weight - X_combination_weight. Based on this combination's value, insert it in the max heap.
user_93507200
Related