平分石头

全栈程序员站长

发布于 2022-09-15 10:58:44

1910

发布于 2022-09-15 10:58:44

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

平分石头

题目描述:

有一n个石头，它们的重量分别是 W1, …, Wn.

写一个程序，把它们分成两堆，使得两堆石头的重量差最小。

输入格式:

输入 n (1 ≤ n ≤ 20)表示石头的个数。

第二行n个石头的重量 W1, …, Wn ( 1 ≤ Wi ≤ 100000)

输出格式:

输入最小的差（绝对值）

样例输入:

样例输出:

时间限制:1000ms 空间限制:128MByte

#include <bits/stdc++.h>
using namespace std;
int a, b[25], ans = 1000000000, s = 0, t;

int dfs(int n, int l, int r)
{
    if(n > a)
    {
        if(abs(l - r) < ans) ans = abs(l - r);
        return 0;
    }
    dfs(n +1, l + b[n], r);
    dfs(n +1, l, r + b[n]);
}

int main()
{
    cin>>a;
    for(int i = 1; i <= a; i++) cin>>b[i], s += b[i];
    sort(b +1, b + a +1);
    dfs(1, 0, 0);
    cout<<ans<<endl;
    return 0;
}

转载于:https://www.cnblogs.com/abs27/p/9304764.html

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/163856.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

https