Is there an algorithm similar to the pack packing problem , but with mutual exclusions? That is, if we took, for example, the first item, we cannot take the third and fifth and vice versa.

  • one
    I do not understand what prevents you from first choosing the order of filling items on the basis of it to define exceptions and continue to solve the usual problem of a backpack. - igumnov
  • What do you mean by "Select the order of filling items"? - stepbystep
  • one
    Mutual exclusions are non-commutative. For simplicity, there are only three items to pack ab c. a excludes c, c excludes b. Then there may not be 3! = 6 options for the packing order less. abc -> ab (a excludes c) acb -> ab (a excludes c) cab -> ca (c excludes b) cba -> ca (c excludes b) bac -> ba (a excludes c) bca -> bca ( Here, the behavior depends on whether an exception acts on what is already in order. That is, exceptions only affect the packing order and not the algorithm itself (where to put it). Therefore, you must first decide on them. - igumnov
  • For this task, the packing order is not important. Suppose we have objects with weights 1 2 and 3 and a backpack with a capacity of 4. Moreover, if we took an object with a weight of 1, we cannot take an object with a weight of 3 and vice versa. It does not matter how they will be placed in a backpack, it is important that we take items with which masses - stepbystep
  • Then you have (12, 21, 32, 23) 4 input options for the usual backpack problem. 2 (the solution of the problem itself does not depend on the order of the items, of course) we solve it once and choose the best backpack from the received ones. - igumnov

1 answer 1

For this task, the order of packing is not important. Suppose we have objects with weights 1 2 and 3 and a backpack with a capacity of 4. Moreover, if we took an object with a weight of 1, we cannot take an object with a weight of 3 and vice versa. It does not matter how they will be placed in a backpack, it is important that the items with which the masses we take

I, of course, apologize, maybe I’m wet off stupidity or stupidity, but why can't we take the capacity of things, including the expected one, which we check for entry from the capacity of the backpack? If the difference is positive - we take the thing, if negative - it does not fit .....

  • You have a backpack with a capacity of 6 and things with masses of 4 3 and 3. According to your algorithm, you will take 4 and stop. Although there is a more optimal option (3 + 3) - stepbystep