knapsack algorithm not returning optimal value
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,
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
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.
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.
#~ weights_jump = find_indices(temp_w, lambda e: e < capacity)
#~ if(len(weights_jump)>0):
#~ temp_w[0:weights_jump[0]-1] = []
#~ temp_v[0:weights_jump[0]-1] = []
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
The following is the main function. the input for this function is as follows,
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
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
The following is the recursive function
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.
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.
i will follow left branch if the weight of the first element is less than capacity. so append(1) . updating values,weights list etc and again call node function.
so it first transverses entire left branch and then transverses right branch.
in the right im just updating the values,weights lists and calling node function.
For this function inputs are
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<=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 < capacity
#~ weights_jump = find_indices(temp_w, lambda e: e < capacity)
#~ if(len(weights_jump)>0):
#~ temp_w[0:weights_jump[0]-1] = []
#~ temp_v[0:weights_jump[0]-1] = []
if(temp_w[0]<=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]>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]>v2[0]):
return v1;
else:
return v2;
The following is the helper function maxValue which is called from recursive function
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]<=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;
I spent days on this and could not do anything.
链接地址: http://www.djcxy.com/p/59942.html上一篇: 背包恢复解决方案的复杂性
下一篇: 背包算法不能返回最优值