Satchel problem (classic)

Question

So, I have to solve the problem with the backpack for the class. So far I have come up with the following. My comparators are functions that determine which of the two items would be the best option (by looking at the corresponding (values, working) tuples).

I decided to sort through possible subjects with work less than maxWork, and to find which subject is the best option at any moment, I compared my last subject with all the other topics that we have not yet used.

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 

The problem is that I do not know why this is wrong. I get errors, and I have no idea where my code is wrong (even after throwing in print statements). Help would be greatly appreciated, thanks!

Answer 1

Using a simple greedy algorithm will not give any restrictions on the quality of the solution compared to OPT.

Here is a fully polynomial time (1 - epsilon) * PPEP approximation for a knapsack:

 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) 

We need to determine the most profitable recruitment algorithm. We can do this with some dynamic programming. But first, let's look at some definitions.

If P is the most profitable element in the set, and n is the number of elements that we have, then nP is obviously the trivial upper bound of the allowed profit. For each I from {1, ..., n} and p in {1, ..., nP} we will denote by Sip a subset of elements whose total profit is equal to p and whose total size is minimized. Then we denote by A (i, p) the size of the set Sip (infinity if it does not exist). It is easy to show that A (1, p) is known for all values ​​of p in {1, ..., nP}. We will determine the repeatability for computing A (i, p), which we will use as a dynamic programming problem to return an approximate solution.

 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) 

Finally, we give _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) 

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)