如何重新包装最大容量的多个背包，将它们的物品倾倒在一堆，洗牌，并取出一些物品？

Question

在多背包问题的这个变体中，只考虑了项目的权重，所以我猜它更像是一个多子集和问题，但用背包更容易解释。

有n背包，每个背包充满其个人最大重量容量C[j]，其中0 <= j < n。

背包被倒空到一堆，总共有m项目，每个都有一个重量W[i]，其中0 <= i < m。堆中的物品被洗牌，k物品从堆中移除，其中0 <= k <= m。

n，m，C[j]和W[i]是大于零的整数; i，j和k是非负整数。

此状态是打包算法的初始输入。

如何重新包装所有剩余的m - k项目，以便不超过每个背包C[j]的个人能力？

• 包装工不知道以前如何包装背包
• 以前打包过背包，所以存在一个有效的解决方案
• 使用的背包数量不需要优化，可以有空的背包和/或包装不足的背包
• 即使结果权重也是整数，项目也不能分解成较轻的部分
• 如有必要，可以对物品和背包进行分类
• 我最关心的是正确性，时间对于内存使用更为重要
• 从我提供的样本输入，通常是m <= 10and k ~= 7，但有些情况下m = 20，或k = 0或k = m

我不知道当k接近于零时，首次适合或全包装算法是否能保证达到正确的结果，例如：如果算法在大型背包中包装尽可能多的小物品，但随后是大件物品需要打包，唯一的大背包已经满了。

这是Javascript中我想要完成的一个简单示例：

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 ]
  }
];

Answer 1

是否知道从装箱单中删除了哪些物品？并且，知道什么算法成功打包原始列表？如果这些是已知的，那么子集列表的打包将回复到打包原始​​列表的问题：使用先前成功的打包算法打包原始列表，然后从打包的背包中移除项目以获得子集列表的打包。