背包问题
给定n中物品和一个容量为c的背包，物品i的重量为Wi,其价值为Vi,0-1背包问题是如何选择装入背包的物品（物品不可分割），使得装入背包的物品的价值为最大。
限界函数
| procedure BOUND( p , w, k , M)
∥p为当前效益总量; w 为当前背包重量; k 为上次去掉的物品; M 为背包容量; 返回一个新效益值∥
global n , P( 1∶n ) ,W( 1∶n)
integer k , i ; real b , c , p , w, M
b←p; c←w
for i←k + 1 to n do
c←c + W( i )
if c < M then b←b + P( i )
else return ( b + (1 - ( c - M)/ W( i) ) * P( i ) )
endif
repeat
return ( b)
end BOUND |
背包问题的回溯法求解
| procedure BKNAP1( M, n ,W, P, fw , fp , X)
∥M 是背包容量。有n 种物品, 其重量与效益分别存在数组W(1∶n) 和P(1∶n) 中; P(i)/W(i)≥P(i+1)/W(i+ 1)。fw 是背包的最后重量, fp 是背包取得的最大效益。X(1∶n) 中每个元素取0或1值。若物品k 没放入背包, 则X(k)=0 ;否则X(k)=1
integer n , k , Y(1∶n) , i , X(1∶n) ; real M,W( 1∶n) , P(1∶n) , fw , fp , cw , cp;
cw←cp←0 ; k←1; fp← -1 ∥cw 是背包当前重量;cp 是背包当前取得的效益值∥
loop
while k≤ n and cw + W(k) ≤M do ∥将物品k 放入背包∥
cw←cw + W(k) ; cp←cp + P(k) ;Y(k) ←1; k← k + 1
repeat
if k > n then fp←cp ; fw←cw;k←n;X←Y ∥修改解∥
else Y( k)←0 ∥超出M, 物品K 不适合∥
endif
while BOUND( cp、cw, k , M) ≤fp do ∥上面置了fp 后,BOUND = fp∥
while k≠0 and Y( k)≠1 do
k←k - 1 ∥找最后放入背包的物品∥
repeat
if k = 0 then return endif ∥算法在此处结束∥
Y( k) ←0; cw←cw - W( k) ; cp←cp - P( k) ∥移掉第k 项∥
repeat
k←k + 1
repeat
end BKNAP1 |
