Xubx


私信TA

用户名:dotcpp0643823

访问量:1401

签 名:

种瓜得瓜,种豆得豆

等  级
排  名 21936
经  验 611
参赛次数 0
文章发表 7
年  龄 18
在职情况 学生
学  校 哈尔滨师范大学
专  业

  自我简介:

TA的其他文章

简单数学题
浏览:106

解题思路:
通过递归遍历每一种情况,并通过剪枝减少遍历次数节省时间
注意事项:
暴力求解可能得不到满分,但可以得到大多数分值
参考代码:

#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 人评分

  评论区