Chia của

Points: 2

Time limit: 1.0s

Memory limit: 1000M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, ~~Classical~~, COBOL, ~~Coffee~~, CSC, D lang, DART, F95, FORTH, Fortrn, ~~GAS32~~, GO, Haskell, Itercal, Java, ~~kotlin~~, ~~LEAN~~, LISP, LUA, MONOVB, ~~Nasm~~, ~~OCAML~~, Pascal, Perl, php, PIKE, ~~prolog~~, Pypy, Python, ~~Ruby 2~~, RUST, Scala, SCM, SED, ~~SWIFT~~, TCL, ~~TUR~~, ~~V8JS~~, VB, ZIG

Một ông bố có n tài sản có giá trị lần lượt là a1,a2,…,an. Ông chỉ có hai người con ông muốn đem chia n tài sản này cho 2 người con sao cho chênh lệch giữa 2 người là ít nhất có thể.

Input

Dòng thứ nhất số nguyên dương n là tài sản ( 1 ≤ n ≤ 20)

Dòng thứ hai chứa n số nguyên dương có giá trị tuyệt đối không quá 10^4

Output

Một số nguyên là độ chênh ít nhất có thể của hai người con

Example 1

Input

3
8 4 6

Output

Giải thích: Một người nhận 8 một người nhận 4+6=10 nên chênh lệch ít nhất 2

Example 2

Input

5
10 7 9 6 6

Output

Giải thích: Một người nhận 10+9 =19 một người nhận 7+6+6=19 nên chênh lệch ít nhất 0

tichpx

Comments

0

anhdungyenchau commented on Jan. 29, 2026, 8:05 a.m.

include<bits/stdc++.h>

using namespace std;

int n, res = 1e6; vector<int> b(21); vector<int> a(21);

void check() { int s1 = 0, s2 = 0; for (int i = 1; i <= n; i++) { if (b[i] == 0) s1 += a[i]; else s2 += a[i]; } res = min(res, abs(s1 - s2)); }

void backtrack(int t) { if (t == n+1) { check(); return; } for (int i = 0; i <= 1; i++) { b[t] = i; backtrack(t+1); } }

int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } backtrack(1); cout << res; }

-1

kienduy1221 commented on April 19, 2025, 4:05 a.m.

include<bits/stdc++.h>

using namespace std;
//code by Kien - chia cua BACKTRACKING
int n, x[100];
int a[100];
int min_chenh= INT_MAX;

void In(){
    int A=0, B=0;
    for(int i=1;i<=n;i++){
        if(x[i]==0) A=A+a[i];
        else if(x[i]==1) B=B+a[i];
    } 
    int chenh= abs(A-B);
    min_chenh= min(min_chenh,chenh);
}
void Try(int i){
    for(int j=0; j<=1; j++){
        x[i] = j;
        if(i==n) In();
        else Try(i+1);
    }
}
int main()
{
    cin>>n;
    for(int i=1; i<=n;i++) cin>>a[i];
    Try(1);
    cout<<min_chenh;
}

-3

thien201206512CNTT4K61 commented on Dec. 2, 2021, 9:20 a.m. ← edited →

#include<bits/stdc++.h>
using namespace std;

int a[100],h[100],n,s;
int d[100][10000],pre[100][10000];

void inp(int a[],int &n,int &s)
{
    scanf("%d",&n);
    s=0;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s+=a[i];
    }
}

void init()
{
    for (int i=1;i<=n;i++)
    {
        d[i][a[i]]=1;
        pre[i][a[i]]=i;
    }
}

void solve()
{
    for (int i=2;i<=n;i++)
    for (int j=0;j<=s;j++)
        if (d[i-1][j]==1)   d[i][j]=1;
        else
            if ((j-a[i]>=0) && (d[i-1][j-a[i]]==1))
            {
                d[i][j]=1;
                pre[i][j]=i;
            }
}

void truyhoi(int n,int s)
{
    if ((n!=0)&&(s!=0))
    {
        if (pre[n][s]!=0)
        {
            truyhoi(n-1,s-a[pre[n][s]]);
            h[n]=1;
        }
        else
        if (d[n-1][s]=1)
            truyhoi(n-1,s);
    }
}

void out(int s1)
{
    truyhoi(n,s1);
    printf("%d",s-s1*2);
}

int main()
{
    inp(a,n,s);
    init();
    solve();
    for (int s1=s/2;s1>0;s1--)
        if (d[n][s1]==1) 
        {
            out(s1);
            break;
        }
    return 0;   
}