(C卷,200分)- 高效货运（Java & JS & Python & C）

题目描述

老李是货运公司承运人，老李的货车额定载货重量为 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

输出描述

单次满载运输的最高利润

用例

输入	10 8 36 15 7
输出	44
说明	无

输入	1 1 2 1 1
输出	2
说明	无

题目解析

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

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

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

因此，我这里提供了两种解法，一种是暴力枚举，一种是完全背包。其中完全背包解法，主要是让大家熟悉下背包问题中，需要恰好装满背包时的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 。

最后保留最大的利润即可。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 输入输出处理
void (async function () {
  let [wa, wb, wt, pa, pb] = (await readline()).split(" ").map(Number);

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

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

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

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

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

  console.log(ans);
})();

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 wt = sc.nextInt();
    int pa = sc.nextInt();
    int 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);
  }
}

Python算法源码

# 输入获取
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>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

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;

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

    printf("%dn", ans);

    return 0;
}

完全背包解法

本题可以转化为完全背包问题。

完全背包问题是指：

有 N 件物品，每件物品的重量为w[i]，价值为p[i]，数量不限。
有一个背包，背包承重为 W

问：不超出背包承重的情况下，装入背包物品的最大价值是多少？

本题中：

货物A，B => 物品
货车 => 背包
货物A，B的单件重量 => 物品的重量
货物A，B的单件利润 => 物品的价值
货车的载重 => 背包的载重

另外，本题作了如下改动：

本题要求货车上必须装入A，B货物
本题要求货车必须装满

对于改动1，我们可以预先给货车装一件A，一件B，此时：

货车承重 = wt -（wa + wb）
已获得利润 = pa + pb

即可转化为完全背包问题为：

背包承重：wt -（wa + wb）
物品重量：wa、wb
物品价值：pa、pb
物品数量：无限

对于改动2，要求装满背包，而装满背包和不装满背包的区别仅在于dp初始化：

不强制装满背包的问题，dp数组元素可以全部初始化为0，
强制装满背包的问题，dp数组元素只有dp[0][0]初始化为0，其余dp元素需要初始化为负无穷

对于要求装满背包的场景，关于dp元素（除dp[0][0）初始化为负无穷的原因，在解释之前，我们应该对dp数组有个初步的了解：

dp[i][j] 表示：从前 i 种物品选择，装满承重为 j 的背包，所能获得的最大价值，而 dp[i][j] 可以由之前的dp状态递推得到，递推公式（状态转移方程）如下：

dp[i][j] = max(dp[i-1][j], dp[i-1][j – w[i]] + p[i])

上面递推公式的含义为：

对于第 i 个物品，我们可以选择装或者不装：

如果不装的话，则 dp[i][j] = dp[i-1][j]
如果装的话，则 dp[i][j] = dp[i-1][j – w[i]] + p[i]

在前面状态转移方程中，如果我们选择装入第 i 个物品，那么：

如果 dp[i-1][j – w[i]] 等于负无穷的话，则 dp[i-1][j – w[i]] + p[i] 结果也是负无穷，即dp[i][j]为负无穷。

而dp元素值负无穷的含义是，对应物品选择范围下，不存在可以装满背包的方案。

因此如果前 i – 1 个物品选择组合，不存在可以装满 j – w[i] 承重的背包的方案，那么即使我们后面选择加入了第 i 个物品，也无法装满 j 承重的背包。

相反的，如果 dp[i-1][j – w[i]] ≥ 0 的话，则说明前 i – 1 个物品选择组合，存在可以装满 j – w[i] 承重的背包的方案，且获得的最大价值为dp[i-1][j – w[i]]。

那么我们后面选择加入第 i 个物品的话，也一定可以装满 j 承重的背包。此时 dp[i-1][j – w[i]] + p[i] 也必然 ≥ 0。

因此，dp元素值初始化为负无穷的作用就是，对于无法装满背包的情况进行标记，如果用于递推dp[i][j]的dp值无法装满背包，则dp[i][j]也必然无法装满背包。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 输入输出处理
void (async function () {
  let [wa, wb, wt, pa, pb] = (await readline()).split(" ").map(Number);

  // 背包承重, 这里减去必然需要装入的一件A货物和一件B货物
  wt -= wa + wb;

  // 物品的重量
  const w = [wa, wb];

  // 物品的价值
  const p = [pa, pb];

  // maxP是装满承重为 wt 的背包的最大价值
  const maxP = getResult(wt, 2, w, p);

  if (maxP >= 0) {
    // 如果maxP是非负数，则存在装满背包的方案，注意最后返回结果需要加上初始装上车的一件A和一件B的利润
    console.log(maxP + pa + pb);
  } else {
    // 如果maxP是负数，则说明不存在装满wt的方案，此时直接直接0
    console.log(0);
  }
})();

/**
 * 完全背包
 *
 * @param bag 背包承重
 * @param n 物品种数
 * @param w 物品的重量数组
 * @param p 物品的价值数组
 * @return 装满背包的最大价值
 */
function getResult(bag, n, w, p) {
  // dp[i]表示装满承重为 i 的背包的最大价值
  // 装满背包的背包问题，初始化时需要将除了dp[0]外的dp元素值设为负无穷
  const dp = new Array(bag + 1).fill(-Infinity);
  dp[0] = 0;

  // 遍历物品
  for (let i = 0; i < n; i++) {
    // 遍历背包承重，完全背包这里要正序遍历
    for (let j = w[i]; j <= bag; j++) {
      dp[j] = Math.max(dp[j], dp[j - w[i]] + p[i]);
    }
  }

  // 返回装满承重为bag的背包的最大价值
  return dp[bag];
}

Java算法源码

import java.util.Arrays;
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 wt = sc.nextInt();
    int pa = sc.nextInt();
    int pb = sc.nextInt();

    // 背包承重, 这里减去必然需要装入的一件A货物和一件B货物
    wt -= wa + wb;

    // 物品的重量
    int[] w = new int[] {wa, wb};

    // 物品的价值
    int[] p = new int[] {pa, pb};

    // maxP是装满承重为 wt 的背包的最大价值
    int maxP = getResult(wt, 2, w, p);

    if (maxP >= 0) {
      // 如果maxP是非负数，则存在装满背包的方案，注意最后返回结果需要加上初始装上车的一件A和一件B的利润
      System.out.println(maxP + pa + pb);
    } else {
      // 如果maxP是负数，则说明不存在装满wt的方案，此时直接直接0
      System.out.println(0);
    }
  }

  /**
   * 完全背包
   *
   * @param bag 背包承重
   * @param n 物品种数
   * @param w 物品的重量数组
   * @param p 物品的价值数组
   * @return 装满背包的最大价值
   */
  public static int getResult(int bag, int n, int[] w, int[] p) {
    // dp[i]表示装满承重为 i 的背包的最大价值
    int[] dp = new int[bag + 1];

    // 装满背包的背包问题，初始化时需要将除了dp[0]外的dp元素值设为负无穷
    Arrays.fill(dp, Integer.MIN_VALUE);
    dp[0] = 0;

    for (int i = 0; i < n; i++) { // 遍历物品
      for (int j = w[i]; j <= bag; j++) { // 遍历背包承重，完全背包这里要正序遍历
        dp[j] = Math.max(dp[j], dp[j - w[i]] + p[i]);
      }
    }

    // 返回装满承重为bag的背包的最大价值
    return dp[bag];
  }
}

Python算法源码

import sys

# 输入获取
wa, wb, wt, pa, pb = map(int, input().split())


# 算法入口
def getResult(bag, n, w, p):
    """
    完全背包
    :param bag: 背包承重
    :param n: 物品种数
    :param w: 物品的重量数组
    :param p: 物品的价值数组
    :return: 装满背包的最大价值
    """

    # dp[i]表示装满承重为 i 的背包的最大价值
    # 装满背包的背包问题，初始化时需要将除了dp[0]外的dp元素值设为负无穷
    dp = [-sys.maxsize for _ in range(bag + 1)]
    dp[0] = 0

    # 遍历物品
    for i in range(n):
        # 遍历背包承重，完全背包这里要正序遍历
        for j in range(w[i], bag + 1):
            dp[j] = max(dp[j], dp[j - w[i]] + p[i])

    # 返回装满承重为bag的背包的最大价值
    return dp[bag]


# 算法调用
# 背包承重, 这里减去必然需要装入的一件A货物和一件B货物
wt -= wa + wb

# 物品的重量
w = [wa, wb]
# 物品的价值
p = [pa, pb]

# maxP是装满承重为 wt 的背包的最大价值
maxP = getResult(wt, 2, w, p)

if maxP >= 0:
    # 如果maxP是非负数，则存在装满背包的方案，注意最后返回结果需要加上初始装上车的一件A和一件B的利润
    print(maxP + pa + pb)
else:
    # 如果maxP是负数，则说明不存在装满wt的方案，此时直接直接0
    print(0)

C算法源码

#include <stdio.h>
#include <limits.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

/**
 * 完全背包
 *
 * @param bag 背包承重
 * @param n 物品种数
 * @param w 物品的重量数组
 * @param p 物品的价值数组
 * @return 装满背包的最大价值
 */
int getResult(int bag, int n, const int w[], const int p[]) {
    // dp[i]表示装满承重为 i 的背包的最大价值
    int dp[bag + 1];

    // 装满背包的背包问题，初始化时需要将除了dp[0]外的dp元素值设为负无穷
    dp[0] = 0;
    for (int i = 1; i <= bag; i++) {
        dp[i] = INT_MIN;
    }

    // 遍历物品
    for (int i = 0; i < n; i++) {
        // 遍历背包承重，完全背包这里要正序遍历
        for (int j = w[i]; j <= bag; j++) {
            dp[j] = MAX(dp[j], dp[j - w[i]] + p[i]);
        }
    }

    // 返回装满承重为bag的背包的最大价值
    return dp[bag];
}

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

    // 背包承重, 这里减去必然需要装入的一件A货物和一件B货物
    wt -= wa + wb;

    // 物品的重量
    int w[] = {wa, wb};

    // 物品的价值
    int p[] = {pa, pb};

    // maxP是装满承重为 wt 的背包的最大价值
    int maxP = getResult(wt, 2, w, p);

    if (maxP >= 0) {
        // 如果maxP是非负数，则存在装满背包的方案，注意最后返回结果需要加上初始装上车的一件A和一件B的利润
        printf("%dn", maxP + pa + pb);
    } else {
        // 如果maxP是负数，则说明不存在装满wt的方案，此时直接直接0
        puts("0");
    }

    return 0;
}

免责声明：

1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

3、原文链接：https://moreit.club/?blog=c%e5%8d%b7200%e5%88%86-%e9%ab%98%e6%95%88%e8%b4%a7%e8%bf%90%ef%bc%88java-js-python-c%ef%bc%89，转载请注明出处。

2024华为OD机试题库