| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 817 人关注过本帖
标题:一个oj的题目。有一部没看懂 ,还请各位帮忙看下
只看楼主 加入收藏
花脸
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:9
帖 子:788
专家分:907
注 册:2017-1-4
结帖率:95.37%
收藏
已结贴  问题点数:20 回复次数:2 
一个oj的题目。有一部没看懂 ,还请各位帮忙看下
#include <stdio.h>  
#include <cmath>  
#include <algorithm>  
using namespace std;  

int a[21],total,n,m;
 
void DFS(in    t s,int i)  
{  
    if(i==n)
        return;  
    if(fabs(2*s-total)<m)   
        m = fabs(2*s-total);
   
    DFS(s+a[i],i+1);  
    DFS(s,i+1);              //为什么要用两次递归
    return;  

}  

int main()  
{  
    int i,j;  
    while(~scanf("%d",&n))  
    {  
        total = 0,m = 0x3f3f3f3f;  
        for(i = 0;i<n;i++)  
        {  
            scanf("%d",&a[i]);  
            total += a[i];  
        }  
        DFS(0,0);  
        printf("%d\n",m);  
    }  
    return 0;  
}

今天是阴历七月初五,acm队员zb的生日。zb正在和C小加、never在武汉集训。他想给这两位兄弟买点什么庆祝生日,经过调查,zb发现C小加和never都很喜欢吃西瓜,而且一吃就是一堆的那种,zb立刻下定决心买了一堆西瓜。当他准备把西瓜送给C小加和never的时候,遇到了一个难题,never和C小加不在一块住,只能把西瓜分成两堆给他们,为了对每个人都公平,他想让两堆的重量之差最小。每个西瓜的重量已知,你能帮帮他么?
输入
多组测试数据(<=1500)。数据以EOF结尾
第一行输入西瓜数量N (1 ≤ N ≤ 20)
第二行有N个数,W1, …, Wn (1 ≤ Wi ≤ 10000)分别代表每个西瓜的重量
输出
输出分成两堆后的质量差
搜索更多相关主题的帖子: include int return scanf 生日 
2018-01-06 21:15
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:20 
这个不就是典型的dp问题么~你这样用组合穷举也行~
调用两次就是穷举所有s和s+a[i]的所有可能~
我知道另一种解法可以参考n个数之和是否等于k这类的问题,具体解法类似于0 -1背包那样动规就可以了~
开一个数组记录数据然后查表在中间向两边寻找差值最小的就可以了~
2的20次方约摸为100万,西瓜总和最大据题意为20万,然后时间复杂度为20万乘以20个元素为400万,所以综合比较还是递归简单~

[此贴子已经被作者于2018-1-7 00:49编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-01-07 00:47
花脸
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:9
帖 子:788
专家分:907
注 册:2017-1-4
收藏
得分:0 
回复 2楼 九转星河
谢谢。
2018-01-07 15:07
快速回复:一个oj的题目。有一部没看懂 ,还请各位帮忙看下
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016751 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved