求助一背包算法的变形算法代码.

Question

问题:给定n个不重复的数字(如1-30),给定一个常数M(如100),从n个数字中任选x个不重复(如7个)的数字使这x个数字的和为M,列出所有的x个数字的组合.请给出C代码,谢谢!应该用递归.

Answer 1

// 背包问题递归求解#include <stdio.h>// 从1-N中取X个数，和为M//enum{N=5,X=3,M=9};
//enum{N=7,X=3,M=12};
//enum{N=7,X=4,M=15};
enum{N=30,X=7,M=100};//计算耗时较长[我的机器55秒]int count;
int GetNum(int max,int min,int value)
{
int i;
int b=0;
for(i=max;i>0;i--)
{
if(i<value)
{
if(GetNum(i-1,min-1,value-i))
{
b=1;
printf("%2d, ",i);
}
}
if(min==1&&i==value)
{
count++;
printf("\n%2d, ",i);
return 1;
}
}
return b;
}void main(void)
{
if( GetNum(N,X,M) )
printf("\n 有解：%d\n",count);
else
printf("\n无解\n");
printf("输出说明：每行数目不足位置的数取其正下方第一数值\n");
}