灵鹊做题网编程之美一道思考题的延伸,C语言代码或算法均可
来源：学生作业帮 编辑：灵鹊做题网作业帮 分类：综合作业 时间：2024/05/04 22:48:28
编程之美一道思考题的延伸,C语言代码或算法均可
一个数组,arr[n]={1……n},给定一个数m,在数组中找一个子集合,使其和恰好等于这个数m,求,这样的子集合一共有多少
例如：
n=7 数组为｛1,2,3,4,5,6,7｝
m=14
得到的子集合为
{1,6,7} {2,3,4,5}
{2,5,7} {1,3,4,6}
{3,4,7} {1,2,5,6}
则m=8
{1,2,4,7} 和 {3,5,6}
一个数组,arr[n]={1……n},给定一个数m,在数组中找一个子集合,使其和恰好等于这个数m,求,这样的子集合一共有多少
例如：
n=7 数组为｛1,2,3,4,5,6,7｝
m=14
得到的子集合为
{1,6,7} {2,3,4,5}
{2,5,7} {1,3,4,6}
{3,4,7} {1,2,5,6}
则m=8
{1,2,4,7} 和 {3,5,6}
背包算法.
再问： 是动态规划么？能具体一点么？？
再答： 用F[i,j]表示前i个数组成和为j的种数，最终结果F[n,m]即为所求，转移方程： F[i,j]=F[i-1,j]+F[i-1,j-arr[i]]。
再问： 是动态规划么？能具体一点么？？
再答： 用F[i,j]表示前i个数组成和为j的种数，最终结果F[n,m]即为所求，转移方程： F[i,j]=F[i-1,j]+F[i-1,j-arr[i]]。