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

Question

假设背包所能承受的物品重量为c=6，假设各物品的相应的重量为w={w1，w2，w3}={2,3,4}与重量相对应的效率为p={p1，p2，p3}={1,2,5}；保证约束条件wΣ<=c,求pΣ的最大为多少？
动态规划：
分析：（pj，wj）
S0={(0,0)} ,s1’={(1,2)}
S1={(0,0),(1,2)} s2’={(2,3)}
S2={(0,0),(1,2),(3,5)} s3’={(5,4)}
S3={(0,0),(1,2),(2,3),(5,4),(3,5),(6,6),(7,7)...}
因为（5,4）明显是优于（3,5）的。故（3,5）的存在无价值
因为（7,7）。。明显是超重的，故将其舍去
综上：s3={(0,0),(1,2),(2,3),(5,4),(6,6)}

Answer 1

上面的过程中有一点疏忽，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Σ<=c，因此(7,7),(8,9)不满足条件，被舍去；
第二个原则是对其中的组合方式进行两两比较，将明显较差的舍去。
比如，（5,4）明显是优于（3,5）的，故（3,5）的存在无价值。

这里为什么说（5,4）明显是优于（3,5）的呢？

因为，（5,4）的背包重量只有4，效率却有5，而（3,5）的背包重量为5，效率却只有3，

可以看出，（5,4）明显是优于（3,5）。