解题思路:
通过递归遍历每一种情况,并通过剪枝减少遍历次数节省时间
注意事项:
暴力求解可能得不到满分,但可以得到大多数分值
参考代码:
#include
long long int n;
long long int w[10000];
long long int a[10000];
long long int e = 0;
long long int s[100][100000];
void fama(long long int i, long long int weight)
{
if(i == n)
{
//绝对值
if(weight < 0) weight = -weight;
//判断是否重复
for(long long int i = 0; i < e; i++)
{
if(a[i] == weight) return;
}
a[e] = weight;
e++;
return;
}
//同层出现,return,剪枝
if(s[i][weight]==1)
return;
s[i][weight]=1;
//放左边
fama(i + 1, weight + w[i]);
//放中间
fama(i + 1, weight);
//放右边
fama(i + 1, weight - w[i]);
}
int main()
{
scanf("%lld", &n);
for(long long int i = 0; i < n; i++)
{
scanf("%lld", &w[i]);
}
fama(0, 0);
printf("%lld", e - 1);
return 0;
}
0.0分
4 人评分
2005年春浙江省计算机等级考试二级C 编程题(3),复杂度最低的方法没有之一!!!!!浏览:850 |
C语言程序设计教程(第三版)课后习题7.2 (Java代码)浏览:691 |
简单编码 (C++代码)浏览:722 |
C语言训练-计算1~N之间所有奇数之和 (C语言代码)浏览:682 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:666 |
计算质因子 (C++代码)浏览:1777 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:880 |
数列有序 (C语言代码)浏览:967 |
青年歌手大奖赛_评委会打分 (C语言代码)浏览:2230 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:719 |