算法.S1,s2,s3是怎么得到的假设背包所能承受的物品重量为c=6,假设各物品的相应的重量为w={w1,w2,w3}={2,3,4}与重量相对应的效率为p={p1,p2,p3}={1,2,5};保证约束条件wΣ
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/27 20:11:16
算法.S1,s2,s3是怎么得到的假设背包所能承受的物品重量为c=6,假设各物品的相应的重量为w={w1,w2,w3}={2,3,4}与重量相对应的效率为p={p1,p2,p3}={1,2,5};保证约束条件wΣ
算法.S1,s2,s3是怎么得到的
假设背包所能承受的物品重量为c=6,假设各物品的相应的重量为w={w1,w2,w3}={2,3,4}与重量相对应的效率为p={p1,p2,p3}={1,2,5};保证约束条件wΣ
算法.S1,s2,s3是怎么得到的假设背包所能承受的物品重量为c=6,假设各物品的相应的重量为w={w1,w2,w3}={2,3,4}与重量相对应的效率为p={p1,p2,p3}={1,2,5};保证约束条件wΣ
上面的过程中有一点疏忽,S2={(0,0),(1,2),(3,5)} s3’={(5,4)},
应该改为:S2={(0,0),(1,2),(2,3),(3,5)} s3’={(5,4)}.
另外,S3={(0,0),(1,2),(2,3),(5,4),(3,5),(6,6),(7,7)...}后面的省略号补齐为:
S3={(0,0),(1,2),(2,3),(5,4),(3,5),(6,6),(7,7),(8,9)}
即:
S0={(0,0)} ,s1’={(1,2)}
S1={(0,0),(1,2)} s2’={(2,3)}
S2={(0,0),(1,2),(2,3),(3,5)} s3’={(5,4)}
S3={(0,0),(1,2),(2,3),(5,4),(3,5),(6,6),(7,7),(8,9)}
S0很容易明白,背包是空的,所以p和w都是0;
S1‘,S2’,S3‘也很容易明白,各物品的p和w.
下面看S1,S2,S3:
S1由S0和S1’相叠加所得,S2由S1和S2’相叠加所得,S3由S2和S3’相叠加所得
举个例子,S2由S1和S2’相叠加所得.
S1={(0,0),(1,2)} s2’={(2,3)}
那么,S1 + s2’={(2,3),(3,5)}
S2={S1,S1+S2'}
={(0,0),(1,2),(2,3),(3,5)}