最新华为OD机试真题-A先生的货运计划(200分)

大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

感谢大家的订阅➕ 和 喜欢

在线评测链接

=> A先生的货运计划(200分) <=

评测功能需要 =>订阅专栏<= 后联系清隆解锁～

OJ题目截图

A先生的货运计划

问题描述

A先生是一家货运公司的承运人，他的货车的额定载货重量为 。现有两种货物可以运输，货物 的单件重量为 ，单件运费利润为 ；货物 的单件重量为 ，单件运费利润为 。

A先生每次发车时，货车上的货物总重量必须刚好等于额定载货重量 ，且车上必须同时装有货物 和货物 。货物 和 都是不可切割的。

请问A先生在一次满载运输中，可以获得的最高运费利润是多少？

输入格式

输入共一行，包含五个正整数，分别表示：

• 货物 的单件重量
• 货物 的单件重量
• 货车的额定载重
• 货物 的单件运费利润
• 货物 的单件运费利润

其中，，，。

输出格式

输出一个整数，表示A先生在一次满载运输中可以获得的最高运费利润。

样例输入1

10 8 36 15 7

样例输出1

44

样例输入2

1 1 2 1 1

样例输出2

2

数据范围

题解

本题可以使用枚举的方法来解决。设货车装载货物 的数量为 ，装载货物 的数量为 ，则有如下关系式：

我们可以枚举货物 的数量 ，通过上述关系式计算出货物 的数量 ，如果 是一个非负整数，则说明这种装载方案是可行的。在所有可行的装载方案中，选择运费利润最高的方案即可。

具体步骤如下：

1. 枚举货物 的数量 ，从 到 。
2. 对于每个 ，计算货物 的数量 。
3. 如果 是一个非负整数，则计算当前装载方案的运费利润 ，更新最高运费利润。
4. 输出最高运费利润。

根据题解步骤，可以得到以下参考代码：

• Python

wa, wb, w, pa, pb = map(int, input().split())

res = 0
for x in range(1, w // wa + 1):
    if (w - x * wa) % wb == 0:
        y = (w - x * wa) // wb
        res = max(res, x * pa + y * pb)

print(res)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int wa = sc.nextInt();
        int wb = sc.nextInt();
        int w = sc.nextInt();
        int pa = sc.nextInt();
        int pb = sc.nextInt();
        
        int res = 0;
        for (int x = 1; x <= w / wa; x++) {
            if ((w - x * wa) % wb == 0) {
                int y = (w - x * wa) / wb;
                res = Math.max(res, x * pa + y * pb);
            }
        }
        
        System.out.println(res);
    }
}

• Cpp

#include <iostream>
using namespace std;

int main() {
    int wa, wb, w, pa, pb;
    cin >> wa >> wb >> w >> pa >> pb;
    
    int res = 0;
    for (int x = 1; x <= w / wa; x++) {
        if ((w - x * wa) % wb == 0) {
            int y = (w - x * wa) / wb;
            res = max(res, x * pa + y * pb);
        }
    }
    
    cout << res << endl;
    
    return 0;
}

时间复杂度为 ，空间复杂度为 。