用多个背包和约束求解一种背包概率

我有以下的问题，我想解决与Excel解决或任何其他工具（任何build议是受欢迎的），但我不想写代码。

我有几个项目（约40），放在几个背包（约5）。 每个项目有不同的重量，但每个背包都有相同的空间。

项目重量的总和远小于背包的容量。

我需要做的是在背包中分配物品，使其充满相同的重量。 换句话说，减less方差。

有一个限制：一些项目不能在一起。 我有一个列表（或邻接matrix）的项目可以或不可以一起去。

当然一旦一件物品放在背包里就不能进入第二件物品（每件物品只有一件物品）。

我试图解决这个与Excel解决scheme，但所有的algorithm3说，他们找不到解决scheme，但手动我可以find他们，所以我觉得我没有正确的configuration。

无论如何，我只能configuration有关权重的问题的一部分，但我不能设置有关项目之间不兼容问题的一部分。

感谢您的帮助

Answer 1

这是更多的多处理器调度与侧背约束比背包。

你可以尝试像这样天真的表述。 对于每个项目，有[背包的数量] 0-1variables指示项目在哪个背包，以及这些variables总和为1的约束。目标是最小化背包中的最大总重量。 对于每一对不能放在一起的项目，有相应的指标variables之和小于或等于1的[背包数量]约束。

这是一个有两个背包（A和B），三个项目（x，重量3; y，重量1和z，重量4）以及一个冲突（x不能与y）的工作示例。

 minimize C over 0-1 variables Ax, Ay, Az, Bx, By, Bz and real variable C subject to C >= 3*Ax + 1*Ay + 4*Az # load in A C >= 3*Bx + 1*By + 4*Bz # load in B Ax + Bx = 1 # one placement of x Ay + By = 1 # one placement of y Az + Bz = 1 # one placement of z Ax + Ay <= 1 # conflict between x and y in A Bx + By <= 1 # conflict between x and y in B 

这个公式并不是最优的，因为没有对称性破坏 – 本质上，LP求解器的search树被复制了一个等于背包排列数的因子。 这只是5！ 尽pipe如此，最坏的情况是120，所以可能没事。 要走的路可能是列生成主要问题，相当于正确的覆盖物品与正确数量的背包和一个子问题相当于包装一个受约束的背包，但这是不适用于Excel的范围。