Разделите N торт на M людей с минимальными отходами

Ответ 1

Итак, вот алгоритм, который, как я думал, будет работать:

• Сортировка томов от наибольшего до наименьшего.
• Разделите самый большой торт на 1... k человек, т.е. target = volume [0]/i, где я = 1,2,3,4,..., k
• Если цель приведет к общему количеству кусков, больших k, уменьшите число я и повторите попытку.
• Найдите первое число i, которое приведет к общему количеству элементов, больших или равных K, но (i-1) приведет к общему количеству тортов меньше k. Запишите этот том как baseVolume.
• Для каждого оставшегося торта найдите наименьшую долю оставшегося объема по количеству людей, т.е. деление = (V_cake - (baseVolume * (Math.floor(V_cake/baseVolume))/Math.floor(V_cake/baseVolume )
• Добавьте эту сумму в baseVolume (baseVolume + = division) и пересчитайте общие части, которые могут разделять все тома. Если новый том уменьшится, верните предыдущее значение, в противном случае повторите шаг 6.

Вот коды java:

public static int getKonLagestCake(Integer[] sortedVolumesList, int k) {
    int result = 0;
    for (int i = k; i >= 1; i--) {
        double volumeDividedByLargestCake = (double) sortedVolumesList[0]
                / i;
        int totalNumber = totalNumberofCakeWithGivenVolumn(
                sortedVolumesList, volumeDividedByLargestCake);
        if (totalNumber < k) {
                result = i + 1;
                break;
        }
    }
    return result;
}


public static int totalNumberofCakeWithGivenVolumn(
        Integer[] sortedVolumnsList, double givenVolumn) {
    int totalNumber = 0;
    for (int volume : sortedVolumnsList) {
        totalNumber += (int) (volume / givenVolumn);
    }
    return totalNumber;
}

public static double getMaxVolume(int[] volumesList, int k) {
    List<Integer> list = new ArrayList<Integer>();
    for (int i : volumesList) {
        list.add(i);
    }

    Collections.sort(list, Collections.reverseOrder());
    Integer[] sortedVolumesList = new Integer[list.size()];
    list.toArray(sortedVolumesList);

    int previousValidK = getKonLagestCake(sortedVolumesList, k);
    double baseVolume = (double) sortedVolumesList[0] / (double) previousValidK;

    int totalNumberofCakeAvailable = totalNumberofCakeWithGivenVolumn(sortedVolumesList, baseVolume);

    if (totalNumberofCakeAvailable == k) {
        return baseVolume;
    } else {
        do
        {
            double minimumAmountAdded = minimumAmountAdded(sortedVolumesList, baseVolume);

            if(minimumAmountAdded == 0)
            {
                return baseVolume;
            }else
            {
                baseVolume += minimumAmountAdded;
                int newTotalNumber = totalNumberofCakeWithGivenVolumn(sortedVolumesList, baseVolume);

                if(newTotalNumber == k)
                {
                    return baseVolume;
                }else if (newTotalNumber < k)
                {
                    return (baseVolume - minimumAmountAdded);
                }else
                {
                    continue;
                }
            }

        }while(true);
    }

}

public static double minimumAmountAdded(Integer[] sortedVolumesList, double volume)
{
    double mimumAdded = Double.MAX_VALUE;
    for(Integer i:sortedVolumesList)
    {
        int assignedPeople = (int)(i/volume);
        if (assignedPeople == 0)
        {
            continue;
        }
        double leftPiece = (double)i - assignedPeople*volume;

        if(leftPiece == 0)
        {
            continue;
        }

        double division = leftPiece / (double)assignedPeople;
        if (division < mimumAdded)
        {
            mimumAdded = division;
        }
    }

    if (mimumAdded == Double.MAX_VALUE)
    {
        return 0;
    }else
    {
        return mimumAdded;
    }
}

Любые комментарии будут оценены. Благодаря

Ответ 2

Это несколько классическая проблема программирования-конкурса.

Ответ прост: выполните базовый двоичный поиск на томе V (окончательный ответ).

(Обратите внимание, что название говорит о людях, но описание проблемы говорит К. Я буду использовать M)

Учитывая объем V во время поиска, вы повторяете все торты, подсчитывая, сколько человек каждый пирог может "кормить" кусочками с одним ароматом (fed += floor(Vi/V)). Если вы достигнете M (или "K" ), люди "кормятся" до того, как вы вышли из пирожных, это означает, что вы, очевидно, также можете кормить людей M с любым объемом < V с целыми фрагментами с одним ароматом, просто потребляя столько же (меньших) ломтиков от каждого пирога. Если у вас заканчиваются торты до достижения ломтиков M, это означает, что вы не можете кормить людей любым объемом > V, так как это будет потреблять еще больше пирога, чем то, с чем вы уже не справились. Это удовлетворяет условию двоичного поиска, который приведет вас к наивысшему объему V фрагментов с одним ароматом, которые могут быть предоставлены M людям.

Сложность O(n * log((sum(Vi)/m)/eps) ). Разбивка: бинарный поиск берет log ((сумма (Vi)/m)/eps) итераций, учитывая верхнюю грань sum(Vi)/m торта для каждого человека (когда все торты полностью потребляются). На каждой итерации вы должны пройти не более всех N тортов. eps - это точность вашего поиска и должна быть установлена ​​достаточно низко, не выше минимальной ненулевой разницы между объемом двух тортов, деленной на M*2, чтобы гарантировать правильный ответ. Обычно вы можете просто установить его на абсолютную точность, например 1e-6 или 1e-9.

Чтобы ускорить работу в среднем случае, вы должны сортировать торты в порядке убывания, так что при попытке большого объема вы мгновенно отбрасываете все торты с общим объемом < V (например, у вас есть один торт объемом 10^6, за которым следует куча томов объемом 1.0. Если вы тестируете объем среза 2.0, как только вы достигнете первого торта с объемом 1.0 вы уже можете вернуть, что этот запуск не смог обеспечить M срезы)

Изменить:

Поиск выполняется фактически с номерами с плавающей запятой, например:

double mid, lo = 0, hi = sum(Vi)/people;
while(hi - lo > eps){
    mid = (lo+hi)/2;
    if(works(mid)) lo = mid;
    else hi = mid;
}
final_V = lo;

В конце, , если вам действительно нужна более высокая точность, чем выбранный eps, вы можете просто выполнить дополнительный шаг O (n):

// (this step is exclusively to retrieve an exact answer from the final
// answer above, if a precision of 'eps' is not acceptable)
foreach (cake_volume vi){
   int slices = round(vi/final_V);
   double difference = abs(vi-(final_V*slices));
   if(difference < best){
       best = difference;
       volume = vi;
       denominator = slices;
   }
}
// exact answer is volume/denominator

Ответ 3

Здесь подход, который я бы рассмотрел:

Предположим, что все наши торты отсортированы в порядке неубывающего размера, что означает, что Vn - самый большой торт, а V1 - наименьший торт.

• Создайте первое промежуточное решение, разделив только самый большой торт между всеми k людьми. То есть V = Vn / k.
• Немедленно отбросить все торты меньшие, чем V - любое промежуточное решение, которое включает эти торты, гарантированно будет хуже нашего промежуточного решения с шага 1. Теперь мы остаемся с пирожными Vb, ..., Vn, где b больше или равно 1.
• Если все торты были отброшены, кроме самого большого, мы закончили. V является решением. END.
• Так как у нас осталось несколько лепешек, улучшите наше промежуточное решение, перераспределив часть срезов на второй самый большой торт Vn-1, т.е. найдем наибольшее значение V, чтобы floor(Vn / V) + floor(Vn-1 / V) = k. Это можно сделать, выполнив двоичный поиск между текущим значением V и верхним пределом (Vn + Vn-1) / k или чем-то более умным.
• Опять же, как и на шаге 2, немедленно отбросьте все торты, меньшие, чем V - любое промежуточное решение, которое включает эти торты, гарантированно будет хуже нашего промежуточного решения с шага 4.
• Если все торты были отброшены, за исключением двух самых больших, то мы закончили. V является решением. END.
• Продолжайте привлекать новые "большие" торты в направлении справа налево, улучшайте промежуточное решение и продолжайте отбрасывать "маленькие" торты влево-вправо, пока все оставшиеся торты не будут израсходованы.

P.S. Сложность этапа 4, по-видимому, эквивалентна сложности всей проблемы, а это означает, что приведенное выше можно рассматривать как подход к оптимизации, но не реальное решение. Ну ладно, за что это стоит...:)

Ответ 4

Здесь один подход к более эффективному решению. Ваше решение грубой силы по существу генерирует неявные возможные объемы, фильтрует их по возможности и возвращает наибольшее. Мы можем немного изменить его, чтобы материализовать список и отсортировать его так, чтобы первое возможное решение было самым большим.

Первая задача для вас: найти способ создания отсортированного списка по запросу. Другими словами, мы должны выполнить O (n + m log n), чтобы сгенерировать первые m элементов.

Теперь предположим, что тома, отображаемые в списке, попарно различны. (Мы можем удалить это предположение позже.) Интересный факт о том, сколько людей обслуживается объемом в позиции k. Например, с томами 11, 13, 17 и 7 человек список - 17, 13, 11, 17/2, 13/2, 17/3, 11/2, 13/3, 17/4, 11/3, 17/5, 13/4, 17/6, 11/4, 13/5, 17/7, 11/5, 13/6, 13/7, 11/6, 11/7.

Вторая задача для вас: имитировать алгоритм грубой силы в этом списке. Эксплуатируйте то, что вы заметили.