返回目录

题目描述

老李是货运公司承运人，老李的货车额定载货重量为 wt。

现有两种货物：

• 货物 A 单件重量为 wa，单件运费利润为 pa
• 货物 B 单件重量为 wb，单件运费利润为 pb

老李每次发车时载货总重量刚好为货车额定的载货重量 wt，车上必须同时有货物 A 和货物 B ，货物A、B不可切割。

老李单次满载运输可获得的最高利润是多少？

输入描述

第一列输入为货物 A 的单件重量 wa

• 0 < wa < 10000

第二列输入为货物 B 的单件重量 wb

• 0 < wb < 10000

第三列输入为货车的额定载重 wt

• 0 < wt < 100000

第四列输入为货物 A 的单件运费利润 pa

• 0 < pa < 1000

第五列输入为货物 B 的单件运费利润 pb

• 0 < pb < 1000

输出描述

单次满载运输的最高利润

示例：

题目解析

本题其实第一眼看过去就是完全背包问题，且是需要装满背包的完全背包问题。

但是具体读题后，发现这题的货物只有两种，因此使用完全背包解题反而有点复杂了。

如果货物有多种的话，那么此题用完全背包解题是非常合适的。

因此，我这里提供了两种解法，一种是暴力枚举，一种是完全背包。其中完全背包解法，主要是让大家熟悉下背包问题中，需要恰好装满背包时的dp初始化逻辑。

但是本题考试时可以选择更简单的暴力枚举方式。

暴力枚举解法

假设 x 件A货物，和 y 件B货物，可以装满货车，那么有关系式如下：

wa * x + wb * y = wt

我们可以选择其中的 x 或者 y 进行枚举可能数量，比如 A 货物的件数 x 至少有1件，至多有(wt - wb) / wa 件。

我们枚举A货物数量范围的所有值作为ｘ去尝试，那么只要 (wt - wa * x) % wb == 0（即y是整数），那么就找到了一组可能解x,y。计算此时的货物利润 pa * x + pb * y 。

Python算法源码

# 输入输出处理
if __name__ == "__main__":
    wa, wb, wt, pa, pb = map(int, input().split())

    # 装入货车的A货物数量至少1件，至多(wt - wb) / wa件
    minX = 1
    maxX = (wt - wb) // wa

    # 记录最大利润
    ans = 0

    # 枚举A货物的可能数量
    for x in range(minX, maxX + 1):
        # B货物可能的总重量
        remain = wt - wa * x

        if remain % wb == 0:
            # B货物的数量
            y = remain // wb

            # 计算利润，保留最大利润
            ans = max(ans, pa * x + pb * y)

    print(ans)

C算法源码

#include <stdio.h>

int main() {
    int wa, wb, wt, pa, pb;
    scanf("%d %d %d %d %d", &wa, &wb, &wt, &pa, &pb);

    // 装入货车的A货物数量至少1件，至多(wt - wb) / wa件
    int minX = 1;
    int maxX = (wt - wb) / wa;

    // 记录最大利润
    int ans = 0;

    // 枚举A货物的可能数量
    for (int x = minX; x <= maxX; x++) {
        // B货物可能的总重量
        int remain = wt - wa * x;

        if (remain % wb == 0) {
            // B货物的数量
            int y = remain / wb;

            // 计算利润，保留最大利润
            if (pa * x + pb * y > ans)
                ans = pa * x + pb * y;
        }
    }

    printf("%d\n", ans);
    return 0;
}

Java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int wa, wb, wt, pa, pb;
        wa = sc.nextInt();
        wb = sc.nextInt();
        wt = sc.nextInt();
        pa = sc.nextInt();
        pb = sc.nextInt();

        // 装入货车的A货物数量至少1件，至多(wt - wb) / wa件
        int minX = 1;
        int maxX = (wt - wb) / wa;

        // 记录最大利润
        int ans = 0;

        // 枚举A货物的可能数量
        for (int x = minX; x <= maxX; x++) {
            // B货物可能的总重量
            int remain = wt - wa * x;

            if (remain % wb == 0) {
                // B货物的数量
                int y = remain / wb;

                // 计算利润，保留最大利润
                ans = Math.max(ans, pa * x + pb * y);
            }
        }

        System.out.println(ans);
    }
}