Databases
StackOverflow2013
Postsdbo
POknapsack algorithm not returning optimal value
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POknapsack algorithm not returning optimal value
    primarykey
    data
    text
    <p>I am trying to write an algorithm in python for knapsack problem. I did quite a few iterations and came to the following solution. It seems perfect for me. When I ran it on test sets, </p> <ul> <li>it does not output optimal value</li> <li>and sometimes gives maximum recursion depth error. </li> </ul> <blockquote> <p>after changing the maxValues function it is outputting the optimal value, But it takes very very long time for datasets having more points. how to refine it</p> </blockquote> <p>For the second problem, I have inspected the data for which it gives the error. The data is like huge and only just couple of them exceeds and the knapsack capacity. So it unnecessarily goes through the entire list.</p> <p>So what I planned to do is at the start of running my recursive function, I tried to see the entire weights list where each weight is less than the current capacity and prune the rest. The following is the code I am planning to implement. </p> <pre><code>#~ weights_jump = find_indices(temp_w, lambda e: e &lt; capacity) #~ if(len(weights_jump)&gt;0): #~ temp_w[0:weights_jump[0]-1] = [] #~ temp_v[0:weights_jump[0]-1] = [] </code></pre> <p>My main problem remains that why it is not outputting the optimal value. Please help me in this regards and also to integrate the above code into the current algorithm</p> <p>The following is the main function. the input for this function is as follows,</p> <p>A knapsack input contains n + 1 lines. The first line contains two integers, the first is the number of items in the problem, n. The second number is the capacity of the knapsack, K. The remaining lines present the data for each of the items. Each line, i ∈ 0 . . . n − 1 contains two integers, the item’s value vi followed by its weight wi </p> <pre><code>eg input: n K v_0 w_0 v_1 w_1 ... v_n-1 w_n-1 def solveIt(inputData): # parse the input lines = inputData.split('\n') firstLine = lines[0].split() items = int(firstLine[0]) capacity = int(firstLine[1]) K = capacity values = [] weights = [] for i in range(1, items+1): line = lines[i] parts = line.split() values.append(int(parts[0])) weights.append(int(parts[1])) items = len(values) #end of parsing value = 0 weight = 0 print(weights) print(values) v = node(value,weights,values,K,0,taken); # prepare the solution in the specified output format outputData = str(v[0]) + ' ' + str(0) + '\n' outputData += ' '.join(map(str, v[1])) return outputData </code></pre> <p>The following is the recursive function</p> <p>I'will try to explain this recursive function. Let's say I 'm starting off with root node and now I ill have two decisions to make either to take the first element or not. </p> <p>before this I will call maxValue function to see the maximum value that can be obtained following this branch. If it is less than existing_max no need to search, so prune.</p> <p>i will follow left branch if the weight of the first element is less than capacity. so <code>append(1)</code>. updating values,weights list etc and again call <code>node</code> function.</p> <p>so it first transverses entire left branch and then transverses right branch.</p> <p>in the right im just updating the values,weights lists and calling node function.</p> <p>For this function inputs are </p> <blockquote> <ol> <li>value -- The current value of the problem, It is initially set to zero and is it goes it gets increased</li> <li>weights list</li> <li>values list</li> <li>current capacity</li> <li>current max value found by algo. If this existing_max is greater than the maximum value that can be obtained by following a branch, there is no need to search that branch. so entire branch is pruned</li> <li>existing_nodes is the list which tells whether a particular item is taken (1) or not (0)</li> </ol> </blockquote> <pre><code>def node(value,weights,values,capacity,existing_max,existing_nodes): v1=[];e1=[]; #values we get from left branch v2=[];e2=[]; #values we get from right branch e=[]; e = existing_nodes[:]; temp_w = weights[:] temp_v = values[:]; #first check if the list is empty if(len(values)==0): r = [value,existing_nodes[:]] return r; #centre check if this entire branch could be pruned. it checks for max value that can be obtained is more than the max value inputted to this max_value = value+maxValue(weights,values,capacity); print('existing _max is '+str(existing_max)) print('weight in concern '+str(weights[0])+' value is '+str(value)) if(max_value&lt;=existing_max): return [0,[]]; #Transversing the left branch #Transverse only if the weight does not exceed the capacity print colored('leftbranch','red'); #search for indices of weights where weight &lt; capacity #~ weights_jump = find_indices(temp_w, lambda e: e &lt; capacity) #~ if(len(weights_jump)&gt;0): #~ temp_w[0:weights_jump[0]-1] = [] #~ temp_v[0:weights_jump[0]-1] = [] if(temp_w[0]&lt;=capacity): updated_value = temp_v[0]+value; k = capacity-temp_w[0]; temp_w.pop(0); temp_v.pop(0); e1 =e[:] e1.append(1); print(str(updated_value)+' '+str(k)+' ') raw_input('press ') v1= node(updated_value,temp_w,temp_v,k,existing_max,e1); #after transversing left node update existing_max if(v1[0]&gt;existing_max): existing_max = v1[0]; else: v1 = [0,[]] #Transverse the right branch #it implies we are not including the current value so remove that from weights and values. print('rightbranch') #~ print(str(value)+' '+str(capacity)+' ') raw_input("Press Enter to continue...") weights.pop(0); values.pop(0); e2 =e[:]; e2.append(0); v2 = node(value,weights,values,capacity,existing_max,e2); if(v1[0]&gt;v2[0]): return v1; else: return v2; </code></pre> <p>The following is the helper function <code>maxValue</code> which is called from recursive function</p> <pre><code>def maxValues(weights,values,K): weights = weights; values = values; a=[]; l = 0; #~ print('hello'); items = len(weights); #~ print(items); max = 0;k = K; for i in range(0,items): t = (i,float(values[i])/weights[i]); a.append(t); #~ print(i); a = sorted(a,key=operator.itemgetter(1),reverse=True); #~ print(a); length = len(a); for (i,v) in a: #~ print('this is loop'+str(l)+'and k is '+str(k)+'weight is '+str(weights[i]) ); if weights[i]&lt;=k: max = max+values[i]; w = weights[i]; #~ print('this'+str(w)); k = k-w; if(k==0): break; else: max = max+ (float(k)/weights[i])*values[i]; w = k k = k-w; #~ print('this is w '+str(max)); if(k==0): break; l= l+1; return max; </code></pre> <p>I spent days on this and could not do anything.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USKrishna Deepak
    1. USKrishna Deepak
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. POknapsack algorithm not returning optimal value
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIt is well known and expected that the greedy algorithm quite often does not maximize the value of the knapsack. You know that, right? https://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approximation_algorithm
      singulars
      1. POknapsack algorithm not returning optimal value
      1. USPaul
    2. COis this a greedy algoritm?
      singulars
      1. POknapsack algorithm not returning optimal value
      1. USKrishna Deepak
    3. COIt is late and I am not following this code precisely. The greedy algorithm is mentioned in the comments of solveIt(), the greedy algorithm typically picks items with the highest value per unit weight until the knapsack is full. maxValue() seems to be doing some of that. ----- Did you know lp_solve will solve knapsacks if you state them as maximizations subject to integer inequalities? http://lpsolve.sourceforge.net/5.5/
      singulars
      1. POknapsack algorithm not returning optimal value
      1. USPaul
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload