-1

Помогите пожалуйста новичку решить задачу на языке Java: есть камни, у каждого камня есть свой вес, я хочу распределить камни на 2 кучи, что бы разница в кучах была минимальной. Данную задачу надо решить перебором всех вариантов.

Хочу решить эту задачу полным перебором вариантов. Создал один массив с "Камнями" arr и второй битовый такой же размерности a. Примерный алгоритм таков: если в a[1]=0, то arr[1] в первую кучу, если a[1]=1 то во вторую. И так перебрать все варианты. Но не могу все это написать на языке Java

2
  • А в чем конкретно проблемы? 14 окт 2016 в 22:56
  • 1
    Поясните, пожалуйста - Вы хотите чтобы мы за Вас написали решение? Тут так не работают.
    – user207618
    14 окт 2016 в 23:02

2 ответа 2

1

Как пример:

import java.util.*;

public class StonesPile {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int[] pile = new int[a];
        for (int i = 0; i < pile.length; i++) {
            pile[i] = sc.nextInt();
        }
        Arrays.sort(pile);
        int pile1 = pile[pile.length - 1];
        int pile2 = 0;
        for (int i  = pile.length - 2; i >= 0; i--){
            if (pile1 <= pile2){
                pile1 += pile[i];
            }
            else{
                pile2 += pile[i];
            }
        }
       System.out.println(Math.abs(pile1 - pile2));
    }
}
-2

Битовому массиву соответствует двоичное число. Перебирая все числа от 0 до 1 * 2^n + 1 * 2^(n-1) + ... + 1 и включая соответственные элементы, запоминая при этом лучший результат можно решить задачу.

1
  • Узнать принадлежит ли k-й элемент массиву можно так: (mask >> k) & 1, где mask - закодированная комбинация 14 окт 2016 в 23:04

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.