(新卷,200分)- 代表团坐车（Java JS Python C）-程序员充电站

(新卷,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背包的装满背包的方案数问题。

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

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

输入如下：

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("%d\n", 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("%d\n", 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]; }