揹包問題（經典）

Question

所以我必須解決類的揹包問題。到目前爲止，我已經提出了以下內容。我的比較器是決定哪兩個主題是更好的選項（通過查看相應（值，工作）元組）的函數。

我決定對工作量小於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 

問題是我不知道爲什麼這是錯誤的。我遇到了錯誤，並且我不知道我的代碼在哪裏出錯（即使在拋出打印語句後）。幫助將不勝感激，謝謝！

Answer 1

與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，我們讓Sip表示其總利潤爲, p並且其總尺寸被最小化的項目子集。然後我們讓A（i，p）表示Sip（無窮大，如果它不存在）的大小。我們可以很容易地證明A（1，p）對於{1，...，nP}中的所有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) 

Source

Answer 2

def swap(a,b): 
    return b,a 

def sort_in_decreasing_order_of_profit(ratio,weight,profit): 
    for i in range(0,len(weight)): 
     for j in range(i+1,len(weight)) : 
      if(ratio[i]<ratio[j]): 
       ratio[i],ratio[j]=swap(ratio[i],ratio[j]) 
       weight[i],weight[j]=swap(weight[i],weight[j]) 
       profit[i],profit[j]=swap(profit[i],profit[j]) 
    return ratio,weight,profit   
def knapsack(m,i,weight,profit,newpr): 

    if(i<len(weight) and m>0): 
     if(m>weight[i]): 
      newpr+=profit[i] 
     else: 
      newpr+=(m/weight[i])*profit[i] 
     newpr=knapsack(m-weight[i],i+1,weight,profit,newpr) 
    return newpr 
def printing_in_tabular_form(ratio,weight,profit): 

    print(" WEIGHT\tPROFIT\t RATIO") 
    for i in range(0,len(ratio)): 
     print ('{}\t{} \t {}'.format(weight[i],profit[i],ratio[i])) 

weight=[10.0,10.0,18.0] 
profit=[24.0,15.0,25.0] 
ratio=[] 
for i in range(0,len(weight)): 
    ratio.append((profit[i])/weight[i]) 
#caling function 
ratio,weight,profit=sort_in_decreasing_order_of_profit(ratio,weight,profit) 
printing_in_tabular_form(ratio,weight,profit) 

newpr=0 
newpr=knapsack(20.0,0,weight,profit,newpr)   
print("Profit earned=",newpr)