分数背包的最佳案例

Question

fractional knapsack的最坏情况运行时间是O(n)，那么它最好的情况应该是什么？是 O(1) 吗，因为如果重量限制为 16，并且您得到第一个有价值的物品，对吗？？

Answer 1

(和@Shasha99讨论后编辑改写，感觉2016-12-06之前的回答有点骗人)

总结

O(1) 如果项目已经排序，最好的情况是可能的。否则最好的情况是 O(n).

讨论

如果物品没有排序，你需要找到最好的物品（对于一件物品已经装满背包的情况），仅此一项就需要 O(n)，因为你必须检查所有物品他们。因此，最好的情况 O(n).

在另一端，你可以放一个背包，里面装下所有物品。不需要搜索最好的，但是你需要把全部放进去，所以它仍然是O(n).

更多分析

有趣的是，O(n) 最坏的情况并不意味着项目正在排序。显然来自 http://algo2.iti.kit.edu/sanders/courses/algdat03/sol12.pdf 的想法与快速中位数选择算法（加权中位数或中位数的中位数？）配对。感谢@Shasha99 找到这个算法。

请注意，普通 quickselect 是 O(n) 预期的，O(n*n) 最差，但如果您使用中位数中位数，则变成 O(n) 最坏情况。缺点是算法比较复杂。

我会对任何算法的有效实现感兴趣。更多（希望简单）算法的来源也不会受到伤害。

Answer 2

True if you assume that input is given in sorted order of value !!!

但根据定义，该算法也应采用未排序的输入。 see this.

如果您正在考虑可能排序也可能不排序的正常输入。那么解决问题的方法有两种：

对输入进行排序。即使在最好的情况下，如果您使用 bubble/insertion 排序，也不能小于 O(n)。这看起来完全愚蠢，因为这两种排序算法都具有 O(n^2) avarage/worst 案例性能。
使用 weighted medians 方法。这将花费您 O(n)，因为找到加权中位数将花费 O(n)。下面给出了这种方法的代码。

分数背包的加权中位数方法：

我们将在以下代码中处理每件商品的价值。该代码将首先找到中间值（即，如果按排序顺序给出，则每单位项目值的中间值）并将其放置在正确的位置。我们将为此使用快速排序分区方法。一旦我们得到中间的（称之为mid）元素，需要考虑以下两种情况：

当mid右侧所有项目的权重之和大于W的值时，我们需要在mid右侧搜索答案.
else 将 mid 右侧的所有值相加（称为 v_left）并在 mid 左侧搜索 W-v_left（也包括 mid）。

以下是python中的实现（到处只使用浮点数）：

请注意，我没有为您提供生产级别的代码，并且在某些情况下也会失败。想想什么会导致最糟糕的 case/failure 在数组中找到第 k 个最大值（当所有值都相同时可能是）。

def partition(weights,values,start,end):
    x = values[end]/weights[end]
    i = start
    for j in range(start,end):
        if values[j]/weights[j] < x:
            values[i],values[j] = values[j],values[i]
            weights[i], weights[j] = weights[j],weights[i]
            i+=1 


    values[i],values[end] = values[end],values[i]
    weights[i], weights[end] = weights[end],weights[i]

    return i


def _find_kth(weights,values,start,end,k):
    ind = partition(weights,values,start,end)
    if ind - start == k-1:
        return ind
    if ind - start > k-1:
        return _find_kth(weights,values,start,ind-1,k)
    return _find_kth(weights,values,ind+1,end,k-ind-1)

def find_kth(weights,values,k):
    return _find_kth(weights,values,0,len(weights)-1,k)


def fractional_knapsack(weights,values,w):
    if w == 0 or len(weights)==0:
        return 0

    if len(weights) == 1 and weights[0] > w:
        return w*(values[0]/weights[0])

    mid = find_kth(weights,values,len(weights)/2)

    w1 = reduce(lambda x,y: x+y,weights[mid+1:])
    v1 = reduce(lambda x,y: x+y, values[mid+1:])

    if(w1>w):
        return fractional_knapsack(weights[mid+1:],values[mid+1:],w)


    return v1 + fractional_knapsack(weights[:mid+1],values[:mid+1],w-w1)

分数背包的最佳案例

Best case of fractional knapsack

algorithm

knapsack-problem

time-complexity