(B卷,200分)- 代表团坐车（Java & JS & Python & C）

题目描述

某组织举行会议，来了多个代表团同时到达，接待处只有一辆汽车，可以同时接待多个代表团，为了提高车辆利用率，请帮接待员计算可以坐满车的接待方案，输出方案数量。

约束:

一个团只能上一辆车，并且代表团人数 (代表团数量小于30，每个代表团人数小于30)小于汽车容量(汽车容量小于100)
需要将车辆坐满

输入描述

第一行代表团人数，英文逗号隔开，代表团数量小于30，每个代表团人数小于30
第二行汽车载客量，汽车容量小于100

输出描述

坐满汽车的方案数量
如果无解输出0

用例

输入	5,4,2,3,2,4,9 10
输出	4
说明	解释以下几种方式都可以坐满车，所以，优先接待输出为4 [2,3,5] [2,4,4] [2,3,5] [2,4,4]

题目解析

本题可以转化为01背包的装满背包的方案数问题。

解析可以参考：

也可以尝试下：华为校招机试 – 求和（Java & JS & Python）_伏城之外的博客-CSDN博客

2023.10.14

根据考友反馈，本题存在异常格式输入，

我猜测是类似于

华为OD机试 – 生日礼物（Java & JS & Python & C）_java生日礼物-CSDN博客

中的格式异常输入，即可能输入如下：

[5,4,2,3,2,4,9]
10

或者是类似于

华为OD机试 – 数组拼接（Java & JS & Python）_伏城之外的博客-CSDN博客

中的格式异常输入，即可能输入如下：

5,4,2,3,2,,4,9
10

具体是哪种输入格式，抽到该题的考友没有反馈，但是可以在考试时，通过提示的异常日志来看。

上面两种格式的异常处理，可以参照对应博客内的处理。

不处理输入格式异常也可得90%通过率。

Java算法源码

二维数组解法

import java.util.Arrays;
import java.util.Scanner;

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

    Integer[] nums =
        Arrays.stream(sc.nextLine().split(",")).map(Integer::parseInt).toArray(Integer[]::new);

    int bag = Integer.parseInt(sc.nextLine());

    System.out.println(getResult(nums, bag));
  }

  private static int getResult(Integer[] nums, int bag) {
    int n = nums.length;

    int[][] dp = new int[n + 1][bag + 1];
    dp[0][0] = 1;

    for (int i = 1; i <= n; i++) {
      int num = nums[i - 1];
      for (int j = 0; j <= bag; j++) {
        if (j < num) {
          dp[i][j] = dp[i - 1][j];
        } else {
          dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];
        }
      }
    }

    return dp[n][bag];
  }
}

滚动数组优化解法

import java.util.Arrays;
import java.util.Scanner;

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

    Integer[] nums =
        Arrays.stream(sc.nextLine().split(",")).map(Integer::parseInt).toArray(Integer[]::new);

    int bag = Integer.parseInt(sc.nextLine());

    System.out.println(getResult(nums, bag));
  }

  private static int getResult(Integer[] nums, int bag) {
    int n = nums.length;

    int[] dp = new int[bag + 1];
    dp[0] = 1;

    for (int i = 1; i <= n; i++) {
      int num = nums[i - 1];
      for (int j = bag; j >= num; j--) {
        dp[j] = dp[j] + dp[j - num];
      }
    }

    return dp[bag];
  }
}

JS算法源码

二维数组解法

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length == 2) {
    const nums = lines[0].split(",").map(Number);
    const bag = lines[1] - 0;
    console.log(getResult(nums, bag));
    lines.length = 0;
  }
});

function getResult(nums, bag) {
  const n = nums.length;

  const dp = new Array(n + 1).fill(0).map(() => new Array(bag + 1).fill(0));
  dp[0][0] = 1;

  for (let i = 1; i <= n; i++) {
    const num = nums[i - 1];
    for (let j = 0; j <= bag; j++) {
      if (j < num) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];
      }
    }
  }

  return dp[n][bag];
}

滚动数组优化解法

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length == 2) {
    const nums = lines[0].split(",").map(Number);
    const bag = lines[1] - 0;
    console.log(getResult(nums, bag));
    lines.length = 0;
  }
});

function getResult(nums, bag) {
  const n = nums.length;

  const dp = new Array(bag + 1).fill(0);
  dp[0] = 1;

  for (let i = 1; i <= n; i++) {
    const num = nums[i - 1];
    for (let j = bag; j >= num; j--) {
      dp[j] = dp[j] + dp[j - num];
    }
  }

  return dp[bag];
}

Python算法源码

二维数组解法

# 输入获取
nums = list(map(int, input().split(",")))
bag = int(input())


# 算法入口
def getResult():
    n = len(nums)

    dp = [[0] * (bag + 1) for _ in range(n+1)]
    dp[0][0] = 1

    for i in range(1, n + 1):
        num = nums[i - 1]
        for j in range(bag + 1):
            if j < num:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num]

    return dp[n][bag]


# 算法调用
print(getResult())

滚动数组优化解法

# 输入获取
nums = list(map(int, input().split(",")))
bag = int(input())


# 算法入口
def getResult():
    n = len(nums)

    dp = [0] * (bag + 1)
    dp[0] = 1

    for i in range(1, n + 1):
        num = nums[i - 1]
        for j in range(bag, num-1, -1):
            dp[j] = dp[j] + dp[j - num]

    return dp[bag]


# 算法调用
print(getResult())

C算法源码

二维数组解法

#include <stdio.h>

#define MAX_SIZE 30
#define MAX_ROWS 30 + 1
#define MAX_COLS 100 + 1 

int main()
{
int nums[MAX_SIZE];
int nums_size = 0;
while(scanf("%d", &nums[nums_size++])) {
if(getchar() != ',') break;
}

int bag;
scanf("%d", &bag);

printf("%dn", getResult(nums, nums_size, bag));

return 0;
}

int getResult(int* nums, int nums_size, int bag)
{
int dp[MAX_ROWS][MAX_COLS] = {0};
dp[0][0] = 1;

for(int i=1; i<=nums_size; i++) {
int num = nums[i-1];

for(int j=0; j<=bag; j++) {
if(j < num) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j] + dp[i-1][j - num];
}
}
}

return dp[nums_size][bag];
}

滚动数组优化解法

#include <stdio.h>

#define MAX_ROWS 31
#define MAX_COLS 101 

int main()
{
int nums[MAX_ROWS];
int nums_size = 0;
while(scanf("%d", &nums[nums_size++])) {
if(getchar() != ',') break;
}

int bag;
scanf("%d", &bag);

printf("%dn", getResult(nums, nums_size, bag));

return 0;
}

int getResult(int* nums, int nums_size, int bag)
{
int dp[MAX_COLS] = {0};
dp[0] = 1;

for(int i=0; i<nums_size; i++) {
int num = nums[i];

for(int j=bag; j>=num; j--) {
dp[j] = dp[j] + dp[j-num];
}
}

return dp[bag];
}

免责声明：

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

3、原文链接：https://moreit.club/?blog=b%e5%8d%b7200%e5%88%86-%e4%bb%a3%e8%a1%a8%e5%9b%a2%e5%9d%90%e8%bd%a6%ef%bc%88java-js-python-c%ef%bc%89，转载请注明出处。

2024华为OD机试题库