时间戳

首页 > 解决方案 > 如何重新包装多个最大容量的背包，将他们的物品倾倒在一堆，洗牌，并移除一些物品？

knapsack-problem - 如何重新包装多个最大容量的背包，将他们的物品倾倒在一堆，洗牌，并移除一些物品？

问题描述

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

有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]

我不知道首次拟合或满箱包装算法是否能保证在接近零时达到正确的结果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 ]
  }
];

标签： knapsack-problemsubset-sum

解决方案

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

推荐阅读