multiple-knapsack-solver

多背包求解器 会议调度问题是一个有 2 个背包的多背包问题。 我用来解决这个问题的方法是贪婪和动态规划的结合。 将上午 9 点至下午 12 点视为间隔 1，将下午 1 点至晚上 9 点视为间隔2。 我把 interval1 当作背包来求解。 然后我从谈话列表中删除为 interval1 选择的谈话，并像另一个背包一样解决 interval2。 这给了我一种可能的解决方案。 然后我翻转间隔的顺序，即，我首先考虑 interval2 并解决它，然后是 interval1。 所以我有两种可能的解决方案，最好的一种是得票最多的一种。 这种方法的复杂度为 O(n*K!**(所有区间容量的总和))，其中 n 是谈话次数，K 是背包或不相交区间的数量。 这种方法的权衡是运行时间随着间隔数量的阶乘时间而增长。 如果我们推广到 K 背包，最好使用讨论的算法。