背包问题
上次用的Java写的，存在很大的问题。这次用Python重新写了一下。
现代优化计算方法--背包问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import xlrd
import numpy as np
from numpy import float64
''' read excel 读取价值和重量的数据'''
cnt = 0
data = xlrd.open_workbook('/home/mouye/1.xlsx')
table = data.sheets()[0]
nrows = table.nrows
ncols = table.ncols
capacity = np.array([5555])
w=np.arange(nrows,dtype=float64).reshape(1,nrows)
v=np.arange(nrows,dtype=float64).reshape(1,nrows)
c=np.zeros(nrows).reshape(1,nrows)
vw=np.arange(nrows,dtype=float64).reshape(1,nrows)
tags=np.arange(nrows).reshape(1,nrows)
''' get value/weight 性价比'''
for i in range(nrows):
w[0,i] = table.cell(i,0).value
for i in range(nrows):
v[0,i] = table.cell(i,1).value
vw[0,i] = v[0,i]/w[0,i]
tags[0,i] = i
''' sort them 冒泡排序'''
for i in range(nrows):
for j in range(i+1,nrows):
if vw[0,i]<vw[0,j]:
t=vw[0,i]
vw[0,i]=vw[0,j]
vw[0,j]=t
tag = tags[0,i]
tags[0,i] = tags[0,j]
tags[0,j] = tag
''' 贪心算法 '''
for i in range(nrows):
if capacity[0]>=0:
m=tags[0,i]
capacity[0]-=w[0,m]
c[0,tags[0,i]]=1
cnt = cnt+1
if capacity[0]<0:
c[0,tags[0,cnt-1]]=0
capacity[0]=capacity[0]+w[0,tags[0,cnt-1]]
c=c.reshape(nrows,1)
b=np.dot(v,c)
r=np.dot(w,c)
print r
print b
''' local search '''
capacity = np.array([5555])
for item in range(10000):
x=np.random.randint(0,9999)
c[x,0]=1
c[x+1,0]=0
l=np.dot(v,c)
r=np.dot(w,c)
if r[0,0]<=capacity[0]:
if l[0,0]>b[0,0]:
b[0,0]=l[0,0]
print b[0,0]
