背包算法不能返回最优值
我想在python中为背包问题编写一个算法。 我做了不少迭代，并提出以下解决方案。 这对我来说似乎很完美。 当我在测试集上运行它时，
在改变maxValues函数后，它正在输出最佳值，但对于具有更多点的数据集来说，它需要非常长的时间。 如何改进它
对于第二个问题，我检查了它给出错误的数据。 这些数据非常庞大，只有他们中的几个人超过了背包容量。 所以它不必要地通过整个列表。
所以我打算做的是在开始运行我的递归函数时，我试着看到每个权重小于当前容量的整个权重列表，并修剪剩下的部分。 以下是我计划实施的代码。
#~ 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] = []
我的主要问题仍然是为什么它不输出最佳值。 请在这方面帮助我，并将上述代码集成到当前算法中
以下是主要功能。 该功能的输入如下，
背包输入包含n + 1行。 第一行包含两个整数，第一行是问题中的项目数，n。 第二个数字是背包的容量，K。其余的行显示每个项目的数据。 每行，i∈0。 。 。 n - 1包含两个整数，该项的值vi后跟其权重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
以下是递归函数
我会试着解释这个递归函数。 比方说，我从根节点开始，现在我有两个决定要做第一个元素。
在此之前，我会调用maxValue函数来查看该分支之后可以获得的最大值。 如果它小于existing_max不需要搜索，那么修剪。
如果第一个元素的权重小于容量，我将跟随左侧分支。 所以append(1) 。 更新值，权重列表等，并再次调用node功能。
所以它首先遍历整个左分支然后横贯右分支。
在正确的我只是更新值，权重列表和调用节点功能。
对于这个功能输入是
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;
以下是从递归函数调用的帮助函数maxValue
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;
我花了几天时间，无法做任何事情。
链接地址: http://www.djcxy.com/p/59941.html