CODEWITHSUNDEEP
knapsack-problemsubset-sum
boobsbr
boobsbr

Reputation: 379

How to repack multiple knapsacks which were at maximum capacity, had their items dumped onto a pile, shuffled, and had some items removed?

In this variant of the Multiple Knapsack Problem, only the weight of the items is considered, so I guess it's more like a Multiple Subset Sum Problem, but it's easier to explain with knapsacks.

There are n knapsacks, each filled with items to its individual maximum weight capacity C[j], where 0 <= j < n.

The knapsacks are emptied onto a pile, with a total of m items, each with a weight W[i], where 0 <= i < m. The items in the pile are shuffled and k items are removed from the pile, where 0 <= k <= m.

n, m, C[j] and W[i] are integers larger than zero; i, j and k are non-negative integers.

This state is the initial input to the packing algorithm.

How to repack all the remaining m - k items so that the individual capacity of each knapsack C[j] is not exceeded?

I don't know if first-fit or full-bin packing algorithms are guaranteed to reach a correct result when k approaches zero, for example: if an algorithm packs as many small items as possible in a large knapsack, but then a large item needs to be packed and the only large knapsack is already full.

Here's an simple example in Javascript of what I want to accomplish:

let knapsacks = [
  { capacity: 13 },
  { capacity: 9 },
  { capacity: 60 },
  { capacity: 81 }
];

let items = [ 52, 81, 13 ];

// all items packed
let aSolution = [
  {
    capacity: 13,
    items: [ 13 ]
  },
  { capacity: 9 },
  {
    capacity: 65,
    items: [ 52 ]
  },
  {
    capacity: 81,
    items: [ 81 ]
  }
];

// item 81 not packed
let notASolution = [
  { capacity: 13 },
  { capacity: 9 },
  { capacity: 65 },
  {
    capacity: 81,
    items: [ 52, 13 ]
  }
];

Upvotes: 0

Views: 80

Answers (1)

Thomas Bitonti
Thomas Bitonti

Reputation: 1234

Is it known what items were removed from the packing list? And, is it known what algorithm successfully packed the original list? If those are known, then packing of the subset list reverts to the problem of packing the original list: Pack the original list using the previously successful packing algorithm, then remove the items from the packed knapsacks to obtain a packing of the subset list.

Upvotes: 0

Related Questions