1

我正在尝试用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 后跟它的权重 w

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函数。

所以它首先横切整个左分支，然后横切右分支。

在右边我只是更新值、权重列表和调用节点函数。

对于这个函数输入是

  1. value -- 问题的当前值，最初设置为零，然后它会增加
  2. 权重列表
  3. 值列表
  4. 当前容量
  5. 算法找到的当前最大值。如果这个existing_max 大于跟随一个分支可以获得的最大值，则不需要搜索那个分支。所以整个分支都被修剪了
  6. existing_nodes 是一个列表，它告诉您是否采用 (1) 或不采用 (0) 特定项目
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;

我在这上面花了几天时间，却什么也做不了。

4

0 回答 0