请建议一个更好的解决方案，以优化混乱

Question

请找出下面的一个问题，它的解决办法和它的工作实施。下面的解决方案的时间复杂度为O（n！）（如果我错了，请纠正我）。你知道吗

我的问题是：

1）请建议一个时间复杂度更好的解决方案。考虑到这是一个优化问题，动态规划或记忆似乎是一个更好的选择。另外，请提供一个分析来证明你的解决方案的时间复杂性。谢谢！你知道吗

问题：

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

解决方案1：

对于k阶，考虑所有排列。对于每个排列，贪婪地计算成本。以最小代价选择置换。 我们需要两个数据结构：1）顺序：使用列表2）成本：包含所有使用的管道的列表，其中值是管道的剩余长度。 如果我们完全使用长度为n的单个管道，那么表示成本的数据结构是[0]。你知道吗

#IMPLEMENTATION OF Solution1

import itertools
n = 10

def fulfill_element_greedily(pipes_used, order):
    eligible_pipes = filter(lambda x : x - order >= 0, pipes_used)
    if len(eligible_pipes) == 0:
        new_pipe_used = n-order
    else:
        eligible_pipes.sort(reverse=True)
        new_pipe_used = eligible_pipes[-1] - order
        pipes_used.remove(eligible_pipes[-1])
    return pipes_used + [new_pipe_used]   


def cost_for_greedy_fulfill(orders):
    pipes_used = []
    for order in orders:
        pipes_used = fulfill_element_greedily(pipes_used, order)
    return len(pipes_used)

def min_cost(orders):
    if(any(map(lambda x : x > n,orders))):
        print "Orders %s" % str(orders)
        raise ValueError("Invalid orders")
    return min(map(cost_for_greedy_fulfill,itertools.permutations(orders))) if len(orders)!=0 else 0


def test():
    assert 0 == min_cost([])
    assert 1 == min_cost([1])
    assert 1 == min_cost([5])
    assert 1 == min_cost([10])
    assert 2 == min_cost([10,2])
    assert 2 == min_cost([2,9,7])
    assert 2 == min_cost([1,7,9,3])
    return "tests passed"

print test()

Answer 1

有一种复杂度为O（k*（2^k））的动态规划算法，如下所示：

定义包含以下2个成员的状态：

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]

其中状态[i]表示已经产生管道x（1<；=x<；=k）的最佳状态（最小管道数，即最后一个管道的最大剩余长度），其中设置了i的二进制表示中的第x位。你知道吗

例如

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位的差异

最后的答案来自[2^k-1]状态

复杂性：每个状态最多有（k-1）个以前的状态，有2^k个状态，所以最后的复杂性是O（k*2^k），小于O（k！）你知道吗