任务内容
Description
水果销售公司接了一个单子，现要从公司将货运到火车站。水果都用箱子装好 了，现有三种型号的，分别重量为910、462、和235kg的。现在有不同装载量的货车，请根据装载量给不同货车设计配载方案，使装载的重量总和最大。
Input
多个测试案例，每个一行，输入货车的最大装载量m(m不超过20000），最后一 行是0,不需要处理
Output
每个测试案例输出分2行 第一行输出"Solution A is:",然后是三种箱子各多少个， 中间用一个空格隔开 第二行输出"Load A is:",然后是总载重量 其中A是第几个测试 案例。
#include<stdio.h>
#include<string.h> // 引入字符串处理头文件，用于使用memset函数进行内存初始化操作
#include<stdbool.h> // 引入布尔类型头文件，用于定义布尔变量// 二维数组f用于存储在不同总重量下，三种不同重量物品（箱子）的数量组合情况
// 例如，f[m][0]、f[m][1]、f[m][2]分别表示总重量为m时，三种不同重量箱子的个数
int f[20001][3];
// 布尔类型数组v用于标记某个总重量是否可以通过三种物品的组合达到
// v[i]为true表示总重量i可以通过物品组合达到，为false则表示不能达到
bool v[20001];int main()
{int i, j, l, n, cas = 0; // i、j、l用于循环计数，n用于存储每次输入的货车最大装载量，cas用于记录测试案例的编号int w[3] = { 235, 462, 910 }; // 定义数组w存储三种箱子各自的重量// 使用while循环不断读取输入的整数n，只要能成功读取且n不等于0，就对该输入数据进行处理while (scanf("%d", &n) && n != 0){cas++; // 每处理一组新的测试案例，编号加1// 如果输入的货车最大装载量n小于最小的箱子重量235，说明无法装载任何箱子// 直接输出对应的无装载方案信息，并继续下一次循环读取下一组测试案例的数据if (n < 235){printf("Solution %d is: 0 0 0\nLoad %d is: 0\n", cas, cas);continue;}// 使用memset函数将布尔数组v的所有元素初始化为false，表示初始时所有重量状态都未被标记为可达memset(v, false, sizeof(v));// 使用memset函数将二维数组f的所有元素初始化为0，即初始化三种箱子在各重量下的数量为0memset(f, 0, sizeof(f));v[0] = true; // 将总重量为0的状态标记为可达，这是初始状态// 三层嵌套循环，用于遍历三种不同重量的箱子，尝试通过已有的可达状态推导出新的可达状态for (i = 0; i < 3; i++){for (j = w[i]; j <= n; j++){// 如果当前总重量减去当前箱子重量的状态是可达的（v[j - w[i]]为true），// 且当前总重量j的状态还未被标记为可达（!v[j]为true）if (v[j - w[i]] && !v[j]){// 遍历三种箱子，更新在总重量为j时三种箱子的数量for (l = 0; l < 3; l++){// 如果当前遍历到的箱子类型与正在考虑添加的箱子类型相同（l == i）// 则在当前总重量j下，该类型箱子的数量等于减去该箱子重量的那个可达状态下此类型箱子数量加1if (l == i)f[j][l] = f[j - w[i]][l] + 1;else// 如果不是正在考虑添加的箱子类型，那么在当前总重量j下，该类型箱子的数量保持不变，// 等于减去该箱子重量的那个可达状态下此类型箱子的数量f[j][l] = f[j - w[i]][l];}v[j] = true; // 将当前总重量j的状态标记为可达，表示通过添加箱子达到了这个新状态}}}// 从输入的货车最大装载量n开始递减，寻找第一个被标记为可达的总重量状态for (n; n >= 235; n--){if (v[n]){// 输出当前测试案例的装载方案信息，包括方案编号、三种箱子的数量以及总负载重量printf("Solution %d is: %d %d %d\nLoad %d is: %d\n", cas, f[n][2], f[n][1], f[n][0], cas, n);break; // 找到并输出后，跳出循环，结束当前测试案例的处理}}}return 0;
}解题思路详细解释
- 整体思路概述：
- 本题的目标是针对不同货车的最大装载量，设计出使用三种不同重量箱子（分别为 235kg、462kg、910kg）的配载方案，使得装载的总重量最大。程序采用动态规划的思想来解决这个问题，通过逐步构建不同总重量下的可行装载方案，最终找出给定最大装载量下的最优方案并输出。
- 变量与数组初始化部分：
- 定义了多个变量，其中
cas用于记录测试案例的编号，从 1 开始递增；n用于接收每次输入的货车最大装载量；i、j、l主要用于循环计数。数组w存储了三种箱子的重量，方便在循环中使用。二维数组f用于记录在不同总重量下，三种箱子各自的数量组合情况，而布尔数组v用于标记某个总重量是否可以通过箱子组合达到，初始时将v数组所有元素设为false（表示都不可达），f数组所有元素设为0（表示初始时各箱子数量为 0），并将v[0]设为true，因为总重量为 0 是初始的可达状态。
- 定义了多个变量，其中
- 处理输入与特殊情况判断部分：
- 通过
while循环不断读取输入的货车最大装载量n，只要读取成功且n不为 0，就进入当前测试案例的处理流程。首先判断如果n小于最小箱子的重量 235，意味着无法装载任何箱子，此时直接输出对应无装载的方案信息（即三种箱子数量都为 0，总负载为 0），然后通过continue语句跳过后续当前测试案例的其他处理步骤，直接开始下一次循环读取新的测试案例数据。
- 通过
- 动态规划状态转移部分（核心逻辑）：
- 使用三层嵌套的
for循环来实现动态规划的状态转移过程。最外层循环遍历三种不同重量的箱子类型（通过i控制），中间层循环从当前箱子的重量开始到输入的最大装载量n（通过j控制），表示尝试在不同的总重量下添加当前类型的箱子。对于每个j（总重量），内层if判断语句检查如果当前总重量减去当前箱子重量（j - w[i]）的状态是可达的（v[j - w[i]]为true），并且当前总重量j的状态还未被标记为可达（!v[j]为true），说明可以通过添加当前箱子从之前的可达状态转移到当前状态。 - 当满足上述条件时，再通过内层的
for循环（通过l控制）来更新在总重量为j时三种箱子的数量。如果当前遍历到的箱子类型（l）与正在考虑添加的箱子类型（i）相同，就在当前总重量j下，该类型箱子的数量等于减去该箱子重量的那个可达状态下此类型箱子数量加 1（即f[j][l] = f[j - w[i]][l] + 1）；如果不是正在考虑添加的箱子类型，那么该类型箱子的数量保持不变，等于减去该箱子重量的那个可达状态下此类型箱子的数量（即f[j][l] = f[j - w[i]][l]）。最后将当前总重量j的状态标记为可达（v[j] = true），表示成功通过添加箱子达到了这个新的状态，完成一次状态转移。
- 使用三层嵌套的
- 查找并输出最优方案部分：
- 在完成动态规划的状态转移构建所有可达状态后，从输入的最大装载量
n开始递减（通过循环for (n; n >= 235; n--)），寻找第一个被标记为可达的总重量状态（通过if (v[n])判断）。一旦找到，就说明找到了在当前货车最大装载量下的一种可行装载方案，此时输出该测试案例的装载方案信息，包括方案编号、三种箱子的数量（按照重量从大到小对应的顺序输出，即f[n][2]、f[n][1]、f[n][0]分别对应 910kg、462kg、235kg 箱子的数量）以及总负载重量n，然后通过break语句跳出循环，结束当前测试案例的处理，继续处理下一组输入的测试案例数据（回到while循环继续读取新的n值）。
- 在完成动态规划的状态转移构建所有可达状态后，从输入的最大装载量
