3

Trying out a Knapsack variant where the rules are

  1. Any item you take must fit completely in the bag
  2. Usable metrics of the bag are length(l),width(w),height(h) and you can assume that if the products fit into the bag both individually and together by total volume, there is a way to pack them in
  3. Price value must be maximized
  4. Weight must be minimized without compromising on dollar value

The input is basically a list of items with l,w,h, value in dollars and weight. Seems like thats a lot of metrics apart from the regular knapsack variants. What I am doing is first eliminating all products that dont fit into the bag (volume and dimensions wise). Next I am doing regular knapsack logic (figuring out if each item belongs in the bag or not) based on volume and price using the common DP pseudo code

if (volume[i] > V) {
        return knapsack(i-1, V);
    } else {
        return Math.max(knapsack(i-1, V), knapsack(i-1, V - volume[i]) + values[i]);
    }

This seems to go haywire considering maximum l,w,h of the bag is like 40, 40, 40. (Hence volume is 64000) and number of items is to the tune of 16k. (Java out of memory error). Trying out Branch and Bound (not sure if correctly though)

Another suboptimal way I've tried is to use heuristics based on value/weight ratio and then taking the best volume fit. Another way would be to find all possible packing ways and then pick out the best weight fit (But again this would be hyper exponential)

How to solve this?

1
  • Go as simple knap-sack. Just keep updating the min-weight you need to make a sum
    – Krrish Raj
    Dec 29, 2015 at 8:27

1 Answer 1

1

As the weight optimization should not compromise on the dollar value, presumably there will be multiple ways to fill the knapsack with items that add up to the same highest dollar value.

So, the optimization for weight then consists of selecting the knapsack with the lowest weight among the knapsacks with the highest dollar value.

2
  • Thanks, Does that mean I will have to brute-force all possible combinations(O(2^n)) and then sort on weight? How do I work this into the DP algorithm? Dec 29, 2015 at 8:18
  • 1
    You don't need to brute force all possible combinations, but you may have to adapt the DP algorithm to deal with having multiple identical maximums. Dec 29, 2015 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.