Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной

Категория: Java
2012-03-06 16:45:04

У вас есть несколько камней известного веса W1, …, Wn. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной.

Исходные данные

Ввод содержит количество камней N (1 ≤ N ≤ 20) и веса камней W1, …, Wn (1 ≤ Wi ≤ 100 000) — целые, разделённые пробельными символами.

Результат

Ваша программа должна вывести одно число — минимальную разность весов двух куч.

code: #java
import java.util.*;
public class main
{
        public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int arr[] = new int[n];
        int sum = 0;
        int max = 0;
        int half;
        int k;
 
        for (int i=0; i<n; i++)
        {
                        arr[i] = in.nextInt();
                }
                Arrays.sort(arr);
                max = arr[arr.length-1];
                for (int i=0; i<n; i++)
                {
                        sum += arr[i];
                }
                half = sum/2;
 
 
                if (max <= half)
                {
                        for (int i=arr.length - 2; i>=0; i--)
                        {
                                if (max + arr[i] <= half) max+= arr[i];
                        }
                        k = sum - max;
                        System.out.println(k - max);
                } else {
                        k= sum - max;
                        System.out.println(max - k);
                }
        }
}

автор: Win4ester

Поделиться:

Похожие статьи:

теги: java se