有效地做到这一点(有点)的诀窍是使用前 k 个项目创建具有相同权重的元素集。
从 k=0 处的空集开始,然后使用 k-1 中的组合创建 k 组合。除非您可以有负权重,否则您可以修剪总权重大于 W 的组合。
以下是使用您的示例的结果:
comb[k,w] 是使用前 k 个元素的总权重为 w 的元素集合。
大括号用于集合。
S+e 是通过将元素 e 添加到 S 的每个成员而创建的集合的集合。
comb[0,0]={}
comb[1,0]={comb[0,0]}
comb[1,2]={comb[0,0]+'A'}
comb[2,0]={comb[1,0]}
comb[2,1]={comb[1,0]+'B'}
comb[2,2]={comb[1,2]}
comb[2,3]={comb[1,2]'B'}
comb[3,0]={comb[2,0]}
comb[3,1]={comb[2,1]}
comb[3,2]={comb[2,2]}
comb[3,3]={comb[2,3],comb[2,0]+'C'}
comb[3,4]={comb[2,3]+'C'}
comb[4,0]={comb[3,0]}
comb[4,1]={comb[3,1]}
comb[4,2]={comb[3,2],comb[3,0]+'D'}
comb[4,3]={comb[3,3],comb[3,1]+'D'}
comb[4,4]={comb[3,4],comb[3,2]+'D'}
comb[5,0]={comb[4,0]}
comb[5,1]={comb[4,1],comb[4,0]+'E'}
comb[5,2]={comb[4,2],comb[4,1]+'E'}
comb[5,3]={comb[4,3],comb[4,2]+'E'}
comb[5,4]={comb[4,4],comb[4,3]+'E'}
答案是comb[5,4],它简化为:
{
{{'B'}+'C'},
{{'A'}+'D'},
{
{{'A'}+'B'},
{'C'},
{'B'}+'D'
}+'E'
}
给出所有的组合。