3

だから私は授業のためにナップザック問題を解かなければなりません。これまでのところ、私は次のことを考え出しました。私のコンパレータは、(対応する (value,work) タプルを見て) 2 つのサブジェクトのどちらがより良い選択肢になるかを決定する関数です。

maxWork 未満の仕事で可能な主題を反復することに決め、任意の時点でどの主題が最良の選択肢であるかを見つけるために、最新の主題をまだ使用していない他のすべての主題と比較しました。

def greedyAdvisor(subjects, maxWork, comparator):
    """
    Returns a dictionary mapping subject name to (value, work) which includes
    subjects selected by the algorithm, such that the total work of subjects in
    the dictionary is not greater than maxWork.  The subjects are chosen using
    a greedy algorithm.  The subjects dictionary should not be mutated.

    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    comparator: function taking two tuples and returning a bool
    returns: dictionary mapping subject name to (value, work)
    """

    optimal = {}
    while maxWork > 0:
        new_subjects = dict((k,v) for k,v in subjects.items() if v[1] < maxWork)
        key_list = new_subjects.keys()
        for name in new_subjects:
            #create a truncated dictionary
            new_subjects = dict((name, new_subjects.get(name)) for name in key_list)
            key_list.remove(name)
            #compare over the entire dictionary
            if reduce(comparator,new_subjects.values())==True:
                #insert this name into the optimal dictionary
                optimal[name] = new_subjects[name]
                #update maxWork
                maxWork = maxWork - subjects[name][1]
                #and restart the while loop with maxWork updated
                break
    return optimal

問題は、なぜこれが間違っているのか分からないことです。エラーが発生し、コードのどこが間違っているのかわかりません (print ステートメントを投入した後でも)。助けていただければ幸いです、ありがとう！

4

2 に答える 2

4

単純な貪欲なアルゴリズムを使用しても、OPT と比較してソリューションの品質に制限はありません。

以下は、完全に多項式の時間 (1 - イプシロン) * ナップザックの OPT 近似擬似コードです。

items = [...]  # items
profit = {...} # this needs to be the profit for each item
sizes = {...}  # this needs to be the sizes of each item
epsilon = 0.1  # you can adjust this to be arbitrarily small
P = max(items) # maximum profit of the list of items
K = (epsilon * P) / float(len(items))
for item in items:
    profit[item] = math.floor(profit[item] / K)
return _most_prof_set(items, sizes, profit, P)

ここで、最も収益性の高いセット アルゴリズムを定義する必要があります。これは動的計画法で行うことができます。しかし、最初にいくつかの定義を見てみましょう。

P がセット内で最も収益性の高い項目であり、n が項目の量である場合、nP は明らかに許容される利益の自明な上限です。{1,...,n} の各 i と {1,...,nP} の p に対して、総利益が正確にp であり、総サイズが最小化されているアイテムのサブセットを Sip で表します。次に、A(i,p) がセット Sip のサイズを表すようにします (存在しない場合は無限大)。{1,...,nP} の p のすべての値について A(1,p) が既知であることを簡単に示すことができます。近似解を返すために、動的計画問題として使用する A(i,p) を計算する再帰を定義します。

A(i + 1, p) = min {A(i,p), size(item at i + 1 position) + A(i, p - profit(item at i + 1 position))} if profit(item at i + 1) < p otherwise A(i,p)

最後に _most_prof_set を与えます

def _most_prof_set(items, sizes, profit, P):
    A = {...}
    for i in range(len(items) - 1):
        item = items[i+1]
        oitem = items[i]
        for p in [P * k for k in range(1,i+1)]:
            if profit[item] < p:
                A[(item,p)] = min([A[(oitem,p)], \
                                     sizes[item] + A[(item, p - profit[item])]])
            else:
                A[(item,p)] = A[(oitem,p)] if (oitem,p) in A else sys.maxint
    return max(A)

ソース

于 2011-04-15T23:31:00.687 に答える