动态规划法解0-1背包问题举例

0-1背包问题举例：

设n=6，c=20，

w={4，5，3，8，6，10},

v={20，10，8，18，15，12}

解：

p[7]={(0,0)}

q[7]=p[7]⊕(10,12)={ (10,12)}

p[6]={(0,0), (10,12)}

q[6]=p[6]⊕(6,15)={ (6,15),(16, 27)}

p[5]= {(0,0), (6,15),(16, 27)}

q[5]=p[5]⊕(8,18)={ (8,18),(14, 33)}

p[4]= {(0,0), (6,15), (8,18),(14, 33) }

q[4]=p[4]⊕(3,8)={(3,8),(9,23),(11,26),(17, 41)}

p[3]= {(0,0),(3,8),(6,15),(8,18),(9,23),(11,26),(14, 33),(17, 41)}

q[3]=p[3]⊕(5,10)={(5,10),(8,18),(11,25),(13, 28),(14,33),(16,36),(19, 43)}

p[2]= {(0,0),(3,8),(5,10),(6,15),(8,18),(9,23),(11,26),(13, 28),(14, 33),(16,36),(17, 41),(19,43)}q[2]=p[2]⊕(4,20)={(4,20),(7,28),(9,30),(10,35),(12,38),(13,43),(15,46),(17, 48),(18,

53),(20,56)}p[1]={(0,0),(3,8),(4,20),(7,28),(9,30),(10,35),(12,38),(13,43),(15,46),(17, 48),(18, 53),(20,56)}构造最优解：

i

1

2

4

5

6

X={1，1，1，1，0，0}。(bagc,bagv)-(w i,v

i)∈p[i+1]?

(20,56)-(4,20)∈p[2]

(16,36)-(5,10)∈p[3]

(11,26)-(3,8)∈p[4]

(8,18)-(8,18)∈p[5]

(0,0)-(6,15)∈p[6]

(0,0)-(10,12)∈p[7](w

i,v

i)

(4,20)

(5,10)

(3,8)

(8,18)

(6,15)x

i

1

1

1

0 (10,12)0