设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)

评论