引导生活编码问题 - 如何解决此类问题

Question

我正在寻求如何解决这个问题的想法。我的想法是贪婪的方法。

问题是：

你在俄罗斯萨马拉工作了几天，每天都有新的单位工作工资和新的单位食品成本。工作 1 单位消耗 1 单位能量，吃 1 单位食物增加 1 单位能量。以下是您的工作的一些规格：

+你到达时没有钱，但有能量。你的能量永远不会超过你到达时的能量，它永远不会是消极的。

+您每天可以做任何数量的工作（可能根本不做任何工作），仅受您的精力限制。当你的能量为零时，你无法工作。

+您每天可以吃任意数量的食物（可能根本没有任何食物），受您拥有的钱的限制。当你的钱为零时，你不能吃饭。

+您可以在一天结束时进食，进食后无法返回工作。您可以在第二天返回工作。你的真正目标是带着尽可能多的钱回家。计算您可以带回家的最大金额。

例如，考虑 3 天的住宿，其中每天的单位工作报酬如下：收入=[1, 2, 4]。食物的成本是 cost=[1, 3, 6]。你从 e=5 能量单位开始。

*第一天：1 单位工作值 1，1 单位食品成本 1。这一天上班没有经济激励。

*第二天：1 单位工作赚 2，1 单位食品成本 3，因此你花在吃饭上的钱比总收入多，所以这一天没有去上班的经济激励。

*第三天：您每工作单位赚取 4 个单位。今天，食物的成本无关紧要，因为您将直接下班回家。你把所有的精力都花在工作上，收取你的工资：5 x 4 = 20 个单位的钱，然后不买晚饭就回家了。

功能描述 在下面的编辑器中完成功能calculatePro?t。该函数必须返回一个整数，表示在您入住结束时可以带回家的最大收入。

到目前为止我的解决方案（需要改进）：

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) = max (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。