import sys
import numpy as np
def greedy(p,weight,W):
count_weight = 0
count_p = 0
value = []
bag_list_p = []
bag_list_weight=[]
for i in range(len(p)):
t = p[i]/weight[i]
value.append(t)
for i in range(len(W)):
bag_list_p.append([])
bag_list_weight.append([])
for i in range(len(W)):
temp_p=p[:]
temp_weight=weight[:]
temp_value=value[:]
for j in range(len(p)):
x = np.array(temp_value)
y = x.argsort()
maxvalue=y[-1]
if temp_weight[maxvalue]<=W[i]:
W[i]=W[i]-temp_weight[maxvalue]
count_weight=count_weight+temp_weight[maxvalue]
count_p = count_p + temp_p[maxvalue]
bag_list_p[i].append(temp_p[maxvalue])
bag_list_weight[i].append(temp_weight[maxvalue])
p.pop(maxvalue)
weight.pop(maxvalue)
value.pop(maxvalue)
temp_p = p[:]
temp_weight = weight[:]
temp_value = value[:]
else:
temp_p.pop(maxvalue)
temp_weight.pop(maxvalue)
temp_value.pop(maxvalue)
return bag_list_p,bag_list_weight,p,weight,W,count_p
def NeighborhoodSearch(p,weight,W):
bag_list_p, bag_list_weight, p, weight ,W,count_p= greedy(p, weight, W)
change=0
for i in range(len(W)-1):
for j in range(i+1,len(W)):
for m in range(len(bag_list_p[i])):
for n in range(len(bag_list_p[j])):
if(bag_list_weight[i][m]bag_list_p[j][n]):
change=1
count_p=count_p+new_count_p
print("Find a better value: ",count_p)
x=bag_list_p[j][n]
y=bag_list_weight[j][n]
bag_list_p[j].pop(n)
bag_list_weight[j].pop(n)
bag_list_p[j].append(bag_list_p[i][m])
bag_list_weight[j].append(bag_list_weight[i][m])
bag_list_p[i].pop(m)
bag_list_weight[i].pop(m)
for q in range(len(W)):
for p in range(len(new_bag_list_weight[q])):
bag_list_p[q].append(new_bag_list_p[q][p])
bag_list_weight[q].append(new_bag_list_weight[q][p])
p=new_p
weight=new_weight
p.append(x)
weight.append(y)
W=new_W[:]
else:
count_p=count_p+bag_list_p[j][n]
W[i] = W[i] - bag_list_weight[i][m]
W[j] = W[j] + bag_list_weight[i][m] - bag_list_weight[j][n]
if(change==0):
print("No better value was found")
#sys.exit()
#test case 0: 14,没更好的
weight_0=[1,2,3,4,5,6]
value_0= [2,3,4,5,6,7]
knapsacks_0=[12]
#test case 1：14,没更好的
weight_1=[4,5,6,7,1,3]
value_1= [3,4,5,5,2,3]
knapsacks_1=[10,2,5,6,3,2]
#test case 2：6,没更好的
weight_2=[1,1,1,1,1,1]
value_2= [1,1,1,1,1,1]
knapsacks_2=[10,2,1,3]
#test case 3：20,没更好的
weight_3=[1,2,3,4,5,6]
value_3= [2,3,4,5,6,7]
knapsacks_3=[10,2,6,3]
"""#test case 4:42->44
weight_4=[1,2,3,4,5,6,1,1,5,6,7,1,3,1,1,2,3,2,1,4]
value_4= [2,3,4,5,6,7,1,1,4,5,5,2,3,1,2,3,4,4,4,9]
knapsacks_4=[10,2,5,6,3,2]"""
#test case 5
weight_5=[35,30,60,50,40,
10,25,54,26,75,
24,75,78,33,16,
65,26,56,89,58]
value_5= [10,40,30,50,35,
40,30,31,22,17,
22,56,85,33,64,
86,80,57,38,45]
knapsacks_5=[165,184,148]
w = [3,4,4,3,4,5,3,6,7,3,4,5,5,5,6]
v = [5,6,6,3,4,5,3,6,6,1,2,3,4,3,3]
p = [8,9,10,11,12]
"""Find a better value: 47
Find a better value: 48
Find a better value: 49
Find a better value: 51"""
#test case 4:
weight_4=[1,2,3,4,5,6,5,6,7,1]
value_4= [2,3,4,5,6,7,4,5,5,2]
knapsacks_4=[10,5,8]
#NeighborhoodSearch(v,w,p)
#NeighborhoodSearch(value_5,weight_5,knapsacks_5)
#NeighborhoodSearch(value_0,weight_0,knapsacks_0)
NeighborhoodSearch(value_4,weight_4,knapsacks_4)
#NeighborhoodSearch(value_1,weight_1,knapsacks_1)
#NeighborhoodSearch(value_2,weight_2,knapsacks_2)
#NeighborhoodSearch(value_3,weight_3,knapsacks_3)
