0-1背包问题 c语言求解

利用动态规划原理进行求解 0-1背包问题 已知背包的容量为b，有n种物件，其价格依次为w1,w2,...,wn；其容量依次为v1,v2,...,vn。 现要求在背包允许的容量内，装的物件价值达到最大,其数字模型为： max z=1 x1 + 6 x2 + 18 x3 + 22 x4 + 28 x5 1 x1 + 2 x2 + 5 x3 + 6 x4 + 7 x5 <=11 xi=0,1 i=1,2,3,4,5 S(i,j)=max{S(i-1,j),S(i-1,j-vi)+wi} S(0,j)=0 j>=0 S(i,j)=负无穷 j<0 i=1,w1=1,v1=1 S(1,1)=max{S(0,1),S(0,1-1)+1}=1 S(1,2)=max{S(0,2),S(0,2-1)+1}=1 S(1,3)=...=S(1,11)=1 i=2,w2=6,v2=2 S(2,1)=max{S(1,1),S(1,1-2)+6}=1 S(2,2)=max{S(1,1),S(1,2-2)+6}=6 S(2,3)=max{S(1,3),S(1,3-2)+6}=7 S(2,4)=...=S(2,11)=7 i=3,w3=18,v3=5 S(3,1)=max{S(2,1),S(2,1-5)+18}=1 S(3,2)=max{S(2,2),S(2,2-5)+18}=6 S(3,3)=max{S(2,3),S(2,3-5)+18}=7 S(3,4)=max{S(2,4),S(2,4-5)+18}=7 S(3,5)=max{S(2,5),S(2,5-5)+18}=18 S(3,6)=max{S(2,6),S(2,6-5)+18}=19 S(3,7)=max{S(2,7),S(2,7-5)+18}=24 S(3,8)=max{S(2,8),S(2,8-5)+18}=25 S(3,9)=S(3,10)=...=S(3,11)=25 i=4,w4=22,v4=6 S(4,1)=max{S(3,1),S(3,1-6)+22}=1 S(4,2)=max{S(3,2),S(3,2-6)+22}=6 S(4,3)=max{S(3,3),S(3,3-6)+22}=7 S(4,4)=max{S(3,4),S(3,4-6)+22}=7 S(4,5)=max{S(3,5),S(3,5-6)+22}=18 S(4,6)=max{S(3,6),S(3,6-6)+22}=22 S(4,7)=max{S(3,7),S(3,7-6)+22}=24 S(4,8)=max{S(3,7),S(3,8-6)+22}=38 S(4,9)=max{S(3,7),S(3,9-6)+22}=29 S(4,10)=max{S(3,7),S(3,10-6)+22}=29 S(4,11)=max{S(3,7),S(3,11-6)+22}=40 i=5,w5=28,v5=7 S(5,1)=max{S(4,1),S(4,1-7)+28}=1 S(5,2)=max{S(4,2),S(4,2-7)+28}=6 S(5,3)=max{S(4,3),S(4,3-7)+28}=7 S(5,4)=max{S(4,4),S(4,4-7)+28}=7 S(5,5)=max{S(4,5),S(4,5-7)+28}=18 S(5,6)=max{S(4,6),S(4,6-7)+28}=22 S(5,7)=max{S(4,7),S(4,7-7)+28}=28 S(5,8)=max{S(4,8),S(4,8-7)+28}=29 S(5,9)=max{S(4,9),S(4,9-7)+28}=34 S(5,10)=max{S(4,10),S(4,10-7)+28}=35 S(5,11)=max{S(4,11),S(4,11-7)+28}=40