作业帮 > 数学 > 作业

算法.S1,s2,s3是怎么得到的

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/07/05 17:30:37
算法.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)}
再问: 还有s3里是怎么进行比较,从而得到最终结果,怎么知道去掉哪一个呢?
再答: S3里的比较有两个原则, 第一个比较简单,总重量不超过背包的极限,也就是说保证约束条件wΣ