解题思路:
通过递归遍历每一种情况,并通过剪枝减少遍历次数节省时间
注意事项:
暴力求解可能得不到满分,但可以得到大多数分值
参考代码:
#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语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:546 |
用筛法求之N内的素数。 (C++代码)浏览:692 |
有关字符,字符串的输入输出函数说明浏览:476 |
核桃的数量 (C语言代码)浏览:870 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:573 |
回文数(一) (C语言代码)浏览:1114 |
C语言训练-斐波纳契数列 (C语言代码)浏览:503 |
统计立方数 (C语言代码)浏览:861 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:612 |
字符串的修改 (C++代码)浏览:2853 |