源代码:
#include <stdio.h>
#define N 8
int X[N]={0};
int W[N];
int M,NUM=0;
int main()
{
void input();
void sumofsub(int,int,int);
int s,r,k;
input();
s = r = 0;
for(k=0;k<N;k++)
r += W[k];
k = 0;
if(M > r || M < W[0])
printf("no answer!\n");
else
{
sumofsub(s,k,r);
}
return 0;
}
void input()
{
int i;
printf("input the set of W[1-%d]:",N);
for(i=0;i<N;i++)
{
scanf("%d",&W[i]);
}
printf("input the sum M = ");
scanf("%d",&M);
}
void sumofsub(int s,int k,int r)
{
void print(int);
X[k] = 1;
if(s+W[k] == M)
print(k);
else
{
if(s+W[k]+W[k+1] <= M)
sumofsub(s+W[k],k+1,r-W[k]);
}
if(s+r-W[k] >= M && s+W[k+1] <= M)
{
X[k] = 0;
sumofsub(s,k+1,r-W[k]);
}
}
void print(int k)
{
int i;
NUM++;
printf("the %dth answer is:",NUM);
for(i=0;i<=k;i++)
{
printf("%d ",X[i]);
}
for(;i<N;i++)
{
printf("%d ",0);
}
printf("\n");
}
结果:
input the set of W[1-8]:1 2 3 4 5 6 7 8
input the sum M = 8
the 1th answer is:1 1 0 0 1 0 0 0
the 2th answer is:1 0 1 1 0 0 0 0
the 3th answer is:1 0 0 0 0 0 1 0
the 4th answer is:0 1 0 0 0 1 0 0
the 5th answer is:0 0 1 0 1 0 0 0
the 6th answer is:0 0 0 0 0 0 0 1
分享到:
相关推荐
给定N个数,和一个整数M,判定是否可以从N个数中取出若干个数,使它们的和等于M。输出:YES或者NO。把N个数看成一个集合,问题就是从这个集合中选出一个子集,使这个子集满足和是M
子集和数问题,回溯法实现
很多人在算法分析中说打印子集很难 我当初用c编写的一个程序,是利用文件的打开,复制存取中间子集来实现了打印所有的子集
用回溯法实现子集和问题的完整代码
通用搜索算法及实现 状态空间树的搜索 N皇后问题 排列树的搜索 跳马问题 子集和数问题 水杯问题 。。。。。。。。。。。。
算法设计与分析 课程实验 实验1 归并排序分治策略的设计与实现 实验2 二分检索的递归与迭代算法设计 实验4_旅行消费问题 实验五_最小生成树的设计与...蛇和梯子问题 n皇后问题 组合数问题 填字游戏 子集和数问题 背包
)形成对比,后者鼓励寻找最聪明的方法来用语言表达问题以实现最佳性能。 方法 为了让我们能够比较实现完成的优化程度以及实现的绝对性能,我们设置了以下基本规则: 所有语言的基准都是“相同的”。 这是通过仅依赖...
2.3 用表和数组实现稳定匹配算法 2.4 一般运行时间的概述 2.5 更复杂的数据结构:优先队列 带解答的练习 练习 注释和进一步的阅读 第3章 图 3.1 基本定义与应用 3.2 图的连通性与图的遍历 3.3 用优先队列与栈实现图...
它基于ECMAScript的一个子集。 JSON采用完全独立于语言的文本格式,但是也使用了类似于C语言家族的习惯(包括C、C++、C#、Java、JavaScript、Perl、Python等)。这些特性使JSON成为理想的数据交换语言。 易于人阅读...
附录中的项目符号显示了使用哪些matlab函数/命令来实现各种目标。 该存储库的目标是使查找/重复使用为各种项目生成的代码变得更加容易。 某些功能还依赖或对应于的功能。 在其他存储库中:有关代码示例,请参见,和...
Perl 里的许多观点都是从自然语言中借来的,其中一条最好的观点就是只要你能把自己的意思表述清楚,那么你就可以使用这些语言的一个子集。Perl 文化可以接受任何熟练程度的成员。我们不会在你背后放个语言警察。如果...