Safe packing Constraint satisfaction problem - is it optimal?

60 Views Asked by At

Problem:

You need to pack several items into your shopping bag without squashing anything. The items are to be placed one on top of the other. Each item has a weight and a strength, defined as the maximum weight that can be placed above that item without it being squashed. A packing order is safe if no item in the bag is squashed, that is, if, for each item, that item’s strength is at least the combined weight of what’s placed above that item. For example, here are three items and a packing order:

https://i.stack.imgur.com/PZbeW.png

This packing is not safe. The bread is squashed because the weight above it, 5, is greater than its strength, 4. Swapping the apples and the bread, however, gives a safe packing.

Goal:

Construct a CSP model for this problem, i.e. one which finds safe packings. In constructing the model, consider the need to place N items, where item i is placed in position Pi (0 means “at the top”), has weight Wi and strength Si.

What I tried:

https://i.stack.imgur.com/KI5xK.jpg

So I wanted to know if my CSP model was correct and optimal ?

1

There are 1 best solutions below

0
On BEST ANSWER

Your approach seems correct. Just to ease the notation a bit. Consider a new variable amount of weight placed on it $W$. If you are actually coding the problem it might help to reduce the overweight of calculating $\sum_T w_i$ in your notation.