解题思路:
通过递归遍历每一种情况,并通过剪枝减少遍历次数节省时间
注意事项:
暴力求解可能得不到满分,但可以得到大多数分值
参考代码:
#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 人评分
A+B for Input-Output Practice (V) (C++代码)浏览:464 |
【亲和数】 (C语言代码)浏览:506 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:763 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:622 |
WU-输出九九乘法表 (C++代码)浏览:1702 |
DNA (C语言代码)浏览:546 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:420 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:650 |
数列有序 (C语言代码)浏览:938 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:475 |