C语言背包问题递归算法设有一个背包可以放入的物品重量为S,现有n件物品,重量分别是w1,w2,w3,…wn.问能否从这n件物品中选择若干件放入背包中,使希望高手能讲解一下递归的思路 不要贴代码

C语言背包问题递归算法设有一个背包可以放入的物品重量为S,现有n件物品,重量分别是w1,w2,w3,…wn.问能否从这n件物品中选择若干件放入背包中,使希望高手能讲解一下递归的思路 不要贴代码
C语言背包问题递归算法
设有一个背包可以放入的物品重量为S,现有n件物品,重量分别是w1,w2,w3,…wn.问能否从这n件物品中选择若干件放入背包中,使
希望高手能讲解一下递归的思路 不要贴代码 就讲思路即可.得放入的重量之和正好为S.如果有满足条件的选择,则此背包有解,否则此背包问题无解.
第一行为物品重量S（整数）； 第二行为物品数量n,第三行为n件物品的重量的序列.
有解就输出“yes!”,没有解就输出“no!”.
20
5
1 3 5 7 9
yes!
希望高手给讲解一下递归的思路 不要光贴代码 不用代码.只要讲一下思路即可.

C语言背包问题递归算法设有一个背包可以放入的物品重量为S,现有n件物品,重量分别是w1,w2,w3,…wn.问能否从这n件物品中选择若干件放入背包中,使希望高手能讲解一下递归的思路 不要贴代码
你学过数据结构了吗?如果学过,那就比较好理解,该算法的思路和求二叉树的高度的算法的思路是十分类似的.把取这i个物体看成i个阶段,则该二叉树有i+1层.其中空背包时为根结点,左孩子则为放弃了第1个物品后的背包,右孩子为选取了第1个物品后的背包.今后在对第i个物品进行选择时,向左表示放弃,向右表示选取.则递归算法可如下：
int fun(int s, int i, int n) //s传入的是背包容量, i是进行第i个物品的选取,n为剩余物品的件数
{
if(s == 0) return 有解；
else if(剩余的每件物品都装不进|| n == 0) return 无解；
L = fun(s, i + 1, n - 1); //放弃第i个物品,则下一步的背包容量仍为s,然后看其是否有解,(递归调用进入左子树)
R = fun(s - wi, i + 1, n - 1); //选取第i个物品,则下一步的背包容量为s-wi,然后看其是否有解,(递归调用进入右子树)
return (l, r); //综合考虑左右两边,看哪边是正解或都无解.其实应该返回 return (L||R);
}