|
|
结果的最优解x莫名其妙就被改了，看了好几遍都不知道在哪里改的 
完整代码：
def bound(cv, cw, w, v, k, dw, n): #对剩余物品做贪心选择
b = cv #当前价值总量
c = cw #当前背包已用容量
for i in range(k+1, n):
if c+w <= dw:
c = c + w
b = b + v
else:
b = b + v*((dw-c)/w)
break
return b
def bt_Knapsack(dw, n, w, v, fw, fv, x):
cw = cv = 0
k = 0 #表示第k+1件物品
y = [0 for i in range(n)] #设置临时解向量
while(1):
while k<n and (cw+w[k])<=dw:
cw = cw + w[k]
cv = cv + v[k]
y[k] = 1
k = k + 1
if k>=n: #全部考查完，找到可行解
fv = cv
print('value:',fv)
fw = cw
x = y
print('solution x:', x) # 最优解
k = n-1
else: #k超重，不能装入
y[k] = 0
while bound(cv, cw, w, v, k, dw, n) <= fv: #无更优解
while k != -1 and y[k] != 1: # 回溯
k = k - 1
if k == -1:
break
y[k] = 0
cw = cw - w[k]
cv = cv - v[k]
if k == -1:
break
k = k + 1
print('maxValue:', fv) # 最优值
print('solution:', x) # 最优解
n = 8
dw = 110
w = [1,11,21,23,33,43,45,55]
v = [11,21,31,33,43,53,55,65]
x = [0 for i in range(n)]
fw = 0
fv = -1 #已找到的某个可行解的最大价值。求最大，初值为-1
bt_Knapsack(dw, n, w, v, fw, fv, x)
|
|
