Задайте вопрос по кодированию жизни - Как решить эту проблему

Question

Пожалуйста, помогите мне дать мне представление о том, как решить эту проблему.Моя идея - жадный подход.

Проблема заключается в следующем:

Вы работаете в Самаре, Россия, в течение нескольких дней. Каждый день взимается новая оплата за единицу работы и новые затраты за единицу питания.Работа 1 единицы стоит 1 единицу энергии, а потребление 1 единицы пищи добавляет 1 единицу энергии.Вот некоторые характеристики вашей работы:

+ Вы приехали не с деньгами, а с энергией.У вас никогда не может быть больше энергии, чем вы получаете, и она никогда не может быть отрицательной.

+ Вы можете выполнять любое количество работы каждый день (возможно, вообще не выполнять никакой работы), ограниченное только вашей энергией.Вы не можете работать, когда ваша энергия равна нулю.

+ Вы можете есть любое количество пищи каждый день (возможно, вообще не иметь никакой пищи), ограниченное деньгами, которые у вас есть.Вы не можете есть, когда ваши деньги равны нулю.

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

Например, рассмотрим трехдневное пребывание, в котором оплата за единицу работы за каждый день выглядит следующим образом: заработок = [1, 2, 4].Стоимость еды равна стоимости = [1, 3, 6].Вы начинаете с е = 5 единиц энергии.

* Первый день: 1 единица работы стоит 1, а 1 единица питания стоит 1. Нет финансовых стимулов идти на работу в этот день.

* Второй день: 1 единица работы зарабатывает 2, а 1 единица питания - 3, Таким образом, вы тратите больше на еду, чем общий заработок, поэтому нет финансовых стимулов идти на работу в этот день.

* Третийдень: Вы зарабатываете 4 единицы за единицу работы.Стоимость еды в этот день не имеет значения, так как вы уходите домой прямо с работы.Вы тратите всю свою энергию на работу, собираете зарплату: 5 x 4 = 20 единиц денег и уходите домой, не покупая обед.

Функция Описание Завершите функцию calcPropt в редакторе ниже.Функция должна возвращать целое число, представляющее максимальный заработок, который можно получить домой в конце вашего пребывания.

Мое решение до сих пор (нуждается в улучшении):

function calculateProfit(n, earning, cost, e) {
    // Write your code here

    let sum = 0

    let ef = e;

    let count = 0;

    let max = 0;

    for (let i = 0; i < n; i++){

        if (i != n - 1) {


                console.log("next day " + ef + " " + ef * earning[i + 1] + "--" + ef * cost[i]);

                if (earning[i] > cost[i]) {

                    sum += ef * earning[i];
                    e = 0;

                    max = 0;

                    if (ef * earning[i + 1] > ef * cost[i] && sum > 0) {

                        //console.log(e);
                        sum -= ef * cost[i];
                        e = ef;
                    }


                }
                else {
                    count++;
                    max = Math.max(max, earning[i]);
                }             




        }
        else {//last day

            if (earning[i] <= cost[i]) {
                count++;                
            }

            max = Math.max(max, earning[i]);

            if (e > 0)
                sum += ef * max;

        }

        console.log(i, "-", sum," max=",max);

    }

    console.log("count",count);    

    if (count == n) {
        earning.sort();
        sum = earning[n-1] * ef;
    }

    return sum;

}

Answer 1

К сожалению, разные дни нельзя рассматривать отдельно. Рассмотрим пример, когда рабочая сила и еда дорогие в первый день и дешевые во второй день. Очевидно, вы работаете в первый день и едите во второй день.

Итак, как мы можем решить это? С динамической программой. Каждый день вы должны сделать два выбора: сколько вы работаете и сколько вы едите? В конце дня у вас есть общий заработок и определенное количество энергии. Это количество энергии может иметь только несколько различных значений между 0 и максимальной энергией.

Давайте разделим два решения и будем отслеживать максимальный заработок для каждого оставшегося уровня энергии. Пусть E_afterWork(day: i, energy: e) будет максимальным заработком, который вы можете получить после работы в день i и оставшейся энергии e. Точно так же, E_afterEat(day: i, energy: e) - это максимальный заработок после еды в день i. Мы будем отслеживать эти значения в течение нескольких дней. В итоге нас интересует E_afterWork(day: totalDays - 1, energy: 0). Это сумма денег, которую мы оставляем.

Для первого дня мы можем сразу установить E_afterWork как:

E_afterWork(day: 0, energy: e) = earning[0] * (maxEnergy - e)

Мы делаем это для всех уровней энергии.

Затем мы должны постепенно обновлять E_afterEat и E_afterWork. Это:

E_afterEat(day: i, energy: e) = maximum over possible previous energy pe (E_afterWork(day: i, energy: pe) - cost[i] * (e - pe))

Мы должны проверить все значения pe, которые меньше или равны e и где мы можем позволить себе еду, то есть результат положительный. Последнее должно выполняться автоматически, не делая ничего особенного.

Что мы здесь делаем? Мы проверяем все возможные результаты текущего дня (после работы) и стараемся есть различное количество пищи. Мы сохраняем выбор, который дает нам максимальный заработок (вычисляя заработок как заработок после окончания работы за вычетом затрат на еду).

Теперь как обновить E_afterWork? На самом деле это очень просто:

E_afterWork(day: i, energy: e) = maximum over possible previous energy pe (E_afterEat(day: i-1, energy: pe) + earning[i] * (pe - e))

Та же идея здесь.

Давайте сделаем ваш пример:

earning=[7, 2, 4]
cost=[7, 3, 6]
maxEnergy=5

Давайте инициализируем. Я сокращу E_afterWork с AW и E_afterEat с AE:

e | AW(0, e)
--+----------
5 |    0
4 |    7
3 |   14
2 |   21
1 |   28
0 |   35

Теперь обновите AE. Для первой записи мы вычислим:

AE(0, 5) = min (0 - 0 * 7, 7 - 1 * 7, 14 - 2 * 7, 21 - 3 * 7, …) = 0

e | AW(0, e)  AE(0, e)
--+--------------------
5 |    0         0   
4 |    7         7
3 |   14        14
2 |   21        21
1 |   28        28
0 |   35        35

следующий рабочий день:

e | AW(0, e)  AE(0, e)  AW(1, e)
--+-----------------------------
5 |    0         0         0
4 |    7         7         7 = max(0 + 1 * 2, 7 + 0 * 2)
3 |   14        14        14 = max(0 + 2 * 2, 7 + 1 * 2, 14 + 0 * 2)
2 |   21        21        21
1 |   28        28        28
0 |   35        35        35

Питание:

e | AW(0, e)  AE(0, e)  AW(1, e)  AE(1, e)
--+---------------------------------------
5 |    0         0         0        20
4 |    7         7         7        23
3 |   14        14        14        26
2 |   21        21        21        29 = max(21 - 0 * 3, 28 - 1 * 3, 35 - 2 * 3)
1 |   28        28        28        32 = max(28 - 0 * 3, 35 - 1 * 3)
0 |   35        35        35        35

Работа:

e | AW(0, e)  AE(0, e)  AW(1, e)  AE(1, e)  AW(2, e)
--+-------------------------------------------------
5 |    0         0         0        20       20
4 |    7         7         7        23       24 = max(20 + 1 * 4, 23 + 0 * 4)
3 |   14        14        14        26       28
2 |   21        21        21        29       32
1 |   28        28        28        32       36
0 |   35        35        35        35       40

Таким образом, вы можете заработать в общей сложности 40 , работая в первый день, во второй день и снова работая в последний день.