python - 请为优化难题提出更好的解决方案

Question

请在下面找到一个问题、它的解决方案和它的工作实现。下面的解决方案的时间复杂度为 O(n!)(如果我错了请指正)。

我的问题:

1)请提出一个时间复杂度更好的解决方案。鉴于这是一个优化问题，动态编程或记忆化似乎是更好的选择。另请提供分析证明您的解决方案的时间复杂性。谢谢!

问题:

一家管道公司生产固定长度 n 的管道。它每天收到 k 个管道的订单，每个管道的长度在 (0,n] 之间。编写一个算法来帮助公司使用最少数量的固定长度的管道来完成订单。

解决方案1:

对于 k 阶，考虑所有排列。对于每个排列，贪婪地计算成本。选择成本最低的排列。我们需要两个数据结构:1)顺序:使用列表 2)成本:包含所有使用的管道的列表，其中值是管道的剩余长度。如果我们完全使用长度为n的单个管道，则表示成本的数据结构为[0]。

#解决方案 1 的实现

导入 itertools
n = 10

def fulfill_element_greedily(pipes_used, order):
    eligible_pipes = filter(lambda x : x - order >= 0, pipes_used)
    如果 len(eligible_pipes) == 0:
        new_pipe_used = n 阶
    别的:
        eligible_pipes.sort(反向=真)
        new_pipe_used = eligible_pipes[-1] - 顺序
        pipes_used.remove(eligible_pipes[-1])
    返回 pipes_used + [new_pipe_used]


def cost_for_greedy_fulfill(订单):
    pipes_used = []
    订单中的订单:
        pipes_used = fulfill_element_greedily(pipes_used, order)
    返回 len(pipes_used)

def min_cost(订单):
    如果(任何( map (lambda x:x > n，订单))):
        打印“订单 %s” % str(订单)
        raise ValueError("无效订单")
    返回 min(map(cost_for_greedy_fulfill,itertools.permutations(orders))) 如果 len(orders)!=0 else 0


定义测试():
    断言 0 == min_cost([])
    断言 1 == min_cost([1])
    断言 1 == min_cost([5])
    断言 1 == min_cost([10])
    断言 2 == min_cost([10,2])
    断言 2 == min_cost([2,9,7])
    断言 2 == min_cost([1,7,9,3])
    返回“测试通过”

打印测试()

Answer 1

有一个复杂度为O(k*(2^k))的动态规划算法如下:

定义一个包含以下两个成员的状态:

struct State {
  int minPipe;      // minimum number of pipes
  int remainingLen; // remaining length of last pipe
}

我们说状态a比状态b好当且仅当

(a.minPipe < b.minPipe) or (a.minPipe == b.minPipe && a.remainingLen > b.remainingLen)

问题本身可以分为2^k种状态:

State states[2^k]

其中 states[i] 表示已经产生管道 x 的最佳状态(管道的最小数量，最后一个管道的最大剩余长度)，(1<=x<=k)，其中二进制中的第 x 位i 的表示已设置。

例如，

states[0]: inital state, no pipe produced
states[1]: optimal state with only the 1st pipe produced
states[2]: optimal state with only the 2nd pipe produced
states[3]: optimal state with the 1st and 2nd pipe produced
states[4]: optimal state with only the 3rd pipe produced
...

通过处理每个状态 x 的所有先前状态:

states[x] = 所有可能的先前状态 y 的最佳状态转换，其中 x > y 并且 x 和 y 的二进制表示之间只有 1 位差异。

最终答案来自state[2^k - 1].minPipe;

复杂度:每个状态最多有 (k-1) 个之前的状态，共有 2^k 个状态，所以最终的复杂度为 O(k * 2^k)，小于 O(k!)