解题思路:
通过递归遍历每一种情况,并通过剪枝减少遍历次数节省时间
注意事项:
暴力求解可能得不到满分,但可以得到大多数分值
参考代码:
#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 人评分
C二级辅导-温度转换 (C语言代码)浏览:542 |
化学品问题 (C语言代码)浏览:1378 |
C语言训练-求具有abcd=(ab+cd)2性质的四位数 (C语言代码)浏览:1388 |
C语言程序设计教程(第三版)课后习题8.9 (Java代码)浏览:1390 |
C语言程序设计教程(第三版)课后习题1.5 (C++代码)浏览:1108 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:681 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:675 |
a+b浏览:447 |
图形输出 (C语言代码)浏览:1416 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:740 |