4

Имеется список чисел:

List<Float> weight

Нужно посчитать, на сколько различных комбинаций суммой до 10.0 можно разбить эти числа. Комбинации с переставленными слагаемыми являются одной и той же комбинацией.

Например, [ 1.1, 2.2, 9.9 ] выдаст ответ 2, т.к. возможно 2 комбинации суммой до 10 включительно: 9,9 и 1.1 + 2.2 = 2.3.


Сделал код:

public static int efficientJanitor(List<Float> weight) {
    Collections.sort(weight, Collections.reverseOrder());
    int count = 1;

    for (int i = weight.size() - 1; i > 0; i--) {
        if (weight.get(i) + weight.get(i - 1) <= 3.0) {
            weight.set(i - 1, weight.get(i) + weight.get(i - 1));                    
        } else {
            count++;       
        }
    }

    return count;
}

На малых количествах считает всё верно, однако при запуске более крупных тест-кейсов начал выдавать ошибки.

Что может быть не так? Предел для суммы я установил 3.0.

2
  • Не нужно публиковать как ответ. Вы можете внести правки в свой вопрос (: 25 июл 2019 в 17:57
  • не самый оптимальный вариант использовать здесь сортировку, поскольку ты вначале забьешь "контейнеры" маленькими значениями и что делать дальше с большими - уже вопрос
    – Ep1demic
    25 июл 2019 в 17:58

1 ответ 1

0

Эту задачу можно решить с помошью Динамического программирования

Пример кода (правда это больше расчитанно на int значения)

public int combinationSum(List<Float> weights, int target) {
    int[] dp = new int[target + 1];

    dp[0] = 1;
    for (int j = 1; j <= target; j++) {
        for (float weight : weights) {
            int k = j - (int) weight;
            if (k >= 0) {
                dp[j] += dp[k];
            }
        }
    }
    return dp[target];
}
2
  • не совсем понятно, для чего в вашем коде служит переменная 'target`
    – Ep1demic
    26 июл 2019 в 7:43
  • @Ep1demic это и будет 'суммой до 10.0' из условия 26 июл 2019 в 16:28

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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