设S是一个具有n个元素的集合s={a1,a2,…,an},现将s集合划分成K个满足下列条件的子集s1,s2,…,sk:
1.si 不能为空
2si与sj的交集为空
3.所有子集的并集为S
则称s1,s2,…,sn是s的一个划分.它相当于把s集合中的n个a1,…an放入k个无标号的盒子中,使得没有一个盒子为空,试确定n个a1…an放入k 个无标号盒子的s(n,k)
有两种互不相容的情况:
1){an}是k个子集中的一个:s(n-1,k-1)
2) ){an}不是k个子集中的一个:k*s(n-1,k)
递归关系为:
s(n,k)=s(n-1,k-1)+k*s(n-1,k)  (n>k,k>=1)
s(n,k)=0                (n<k)或(k=n<n)
s(n,k)=1                (k=1)或(k=n)

背包问题
设有一个背包,可以放入的重量为s.现有n件物品重量分别为w1,w2,…,wn,并假设wi(1<=i<=n)均为正整数,且顺序存放在w中(w:array[1..n] of intteger).现要求设计一个布尔函数knap(s0,n0),如果从这n件物品中选择n0件放入此背包,使得放入的重量之和正好为s0,函数返回true,并输出一组被选中的各物品的重量.否则函数返回false.
边界条件:
只要不选任何物品放入包:
        s=0  kanp(s,n)=true
无论如何选,不能使重量为负:
        s<0 kanp(s,n)=false
不取任何东西不可能重量为负:
        s>0且n<1 kanp(s,n)=false
递归体:
当选择的物品中不包含Wn
        kanp(s,n)= knap(s,n-1)
当选择的物品中包含Wn,即knap(s-w[n],n-1)=true:
        kanp(s,n)= knap(s-wn,n-1)

评论