NOIP2026复赛背包问题01完全多重综合练习

NOIP2026复赛背包问题（01/完全/多重）综合练习01背包问题（3题，每题10分）题目1（10分）：物资调配优化背景：某物流公司需要将一批物资从仓库运往多个目的地。仓库中有N种物资，每种物资有若干件，且每种物资的体积不同。物流公司有M辆卡车，每辆卡车的最大载重为C。为了最大化运输效益，需要选择合适的物资装在卡车上，使得总运输体积尽可能接近卡车的总载重，但不能超过每辆车的载重限制。问题描述：给定N种物资的体积和数量，以及M辆卡车的最大载重C，请计算如何分配物资到卡车中，使得所有卡车的总运输体积之和最大，但不能超过每辆车的载重限制。输入：第一行包含三个整数N，M，C，分别表示物资种类数、卡车数量和每辆卡车的最大载重。接下来N行，每行包含两个整数Vi和Qi，分别表示第i种物资的体积和数量。输出：输出一个整数，表示最大总运输体积。示例：输入：3210342552输出：10解析：选择体积为3的物资2件（体积6）和体积为2的物资2件（体积4），总运输体积为10，刚好满足两辆卡车的载重限制。题目2（10分）：装箱问题背景：某电商公司需要将一批商品装箱发货。仓库中有N种商品，每种商品有若干件，且每种商品的体积不同。物流公司有M个箱子，每个箱子的最大容积为V。为了最大化装箱效率，需要选择合适的商品装入箱子中，使得总装箱体积尽可能接近箱子的总容积，但不能超过每个箱子的容积限制。问题描述：给定N种商品的体积和数量，以及M个箱子的最大容积V，请计算如何分配商品到箱子中，使得所有箱子的总装箱体积之和最大，但不能超过每个箱子的容积限制。输入：第一行包含三个整数N，M，V，分别表示商品种类数、箱子数量和每个箱子的最大容积。接下来N行，每行包含两个整数Vi和Qi，分别表示第i种商品的体积和数量。输出：输出一个整数，表示最大总装箱体积。示例：输入：431553348225输出：15解析：选择体积为5的商品1件（体积5）、体积为3的商品2件（体积6）和体积为2的商品2件（体积4），总装箱体积为15，刚好满足三个箱子的容积限制。题目3（10分）：资源分配问题背景：某科技公司需要将一批设备分配到多个实验室中。实验室中有N种设备，每种设备有若干台，且每种设备的体积不同。公司有M个实验室，每个实验室的最大容积为V。为了最大化资源利用效率，需要选择合适的设备分配到实验室中，使得总分配体积尽可能接近实验室的总容积，但不能超过每个实验室的容积限制。问题描述：给定N种设备的体积和数量，以及M个实验室的最大容积V，请计算如何分配设备到实验室中，使得所有实验室的总分配体积之和最大，但不能超过每个实验室的容积限制。输入：第一行包含三个整数N，M，V，分别表示设备种类数、实验室数量和每个实验室的最大容积。接下来N行，每行包含两个整数Vi和Qi，分别表示第i种设备的体积和数量。输出：输出一个整数，表示最大总分配体积。示例：输入：54204362533425输出：20解析：选择体积为4的商品1件（体积4）、体积为6的商品1件（体积6）、体积为5的商品1件（体积5）和体积为2的商品2件（体积4），总分配体积为20，刚好满足四个实验室的容积限制。完全背包问题（3题，每题10分）题目4（10分）：物品购买背景：某超市正在促销，其中N种商品可以无限次购买。每种商品的价格和重量不同。小王有预算M，且手提袋的承重限制为C。为了最大化购买的商品总价值，小王需要选择合适的商品进行购买，使得总重量不超过手提袋的承重限制，且总花费不超过预算。问题描述：给定N种商品的价格和重量，以及预算M和手提袋的承重限制C，请计算如何购买商品，使得总价值最大，但不能超过预算和承重限制。输入：第一行包含三个整数N，M，C，分别表示商品种类数、预算和手提袋的承重限制。接下来N行，每行包含两个整数Pi和Wi，分别表示第i种商品的价格和重量。输出：输出一个整数，表示最大总价值。示例：输入：450101025115372输出：45解析：购买体积为1的商品5件（价值5）、体积为2的商品2件（价值12），总价值为45，总重量为8，总花费为50，满足条件。题目5（10分）：投资组合背景：某投资公司有N种投资项目，每种项目可以无限次投资。每种项目的预期收益和投资额不同。公司有资金M，且投资组合的风险承受能力为C。为了最大化投资组合的总收益，公司需要选择合适的项目进行投资，使得总投资额不超过资金限制，且总风险不超过风险承受能力。问题描述：给定N种项目的预期收益和投资额，以及资金M和风险承受能力C，请计算如何投资项目，使得总收益最大，但不能超过资金限制和风险承受能力。输入：第一行包含三个整数N，M，C，分别表示项目种类数、资金和风险承受能力。接下来N行，每行包含两个整数Pi和Wi，分别表示第i种项目的预期收益和投资额。输出：输出一个整数，表示最大总收益。示例：输入：3100203010405208输出：140解析：投资体积为5的项目4件（收益40）、体积为8的项目1件（收益20），总收益为140，总投资额为100，总风险为20，满足条件。题目6（10分）：任务分配背景：某公司有N个任务需要分配给员工完成。每个任务可以分配给多个员工，但每个员工最多只能完成一定数量的任务。公司有M个员工，每个员工的最大任务数量为C。为了最大化完成任务的总收益，公司需要选择合适的任务分配给员工，使得总任务数量不超过员工的任务限制，且总收益最大。问题描述：给定N个任务的任务收益和任务数量，以及M个员工和每个员工的最大任务数量C，请计算如何分配任务给员工，使得总收益最大，但不能超过员工的任务限制。输入：第一行包含三个整数N，M，C，分别表示任务种类数、员工数量和每个员工的最大任务数量。接下来N行，每行包含两个整数Pi和Qi，分别表示第i个任务的任务收益和任务数量。输出：输出一个整数，表示最大总收益。示例：输入：543202301103402501输出：100解析：分配任务收益为30的任务1件（收益30）、任务收益为40的任务1件（收益40）、任务收益为20的任务2件（收益40），总收益为100，总任务数量为4，满足员工任务限制。多重背包问题（3题，每题10分）题目7（10分）：食材采购背景：某餐厅需要采购一批食材。仓库中有N种食材，每种食材的数量有限，且每种食材的重量不同。餐厅有M辆货车，每辆货车的最大载重为C。为了最大化采购的食材总价值，餐厅需要选择合适的食材装在货车上，使得总运输重量尽可能接近货车的总载重，但不能超过每辆车的载重限制，且每种食材的数量不能超过库存。问题描述：给定N种食材的重量、价值和数量，以及M辆货车的最大载重C，请计算如何分配食材到货车中，使得所有货车的总运输重量之和最大，但不能超过每辆车的载重限制，且每种食材的数量不能超过库存。输入：第一行包含四个整数N，M，C，W，分别表示食材种类数、货车数量、每辆货车的最大载重和每种食材的数量。接下来N行，每行包含三个整数Wi，Pi和Qi，分别表示第i种食材的重量、价值和数量。输出：输出一个整数，表示最大总价值。示例：输入：32105253372491输出：24解析：选择重量为2的食材2件（价值10）、重量为3的食材1件（价值7），总价值为24，总重量为10，满足两辆货车的载重限制。题目8（10分）：货物装载背景：某物流公司需要将一批货物装载到多辆货车上。仓库中有N种货物，每种货物有若干件，且每种货物的体积不同。物流公司有M辆货车，每辆货车的最大容积为V。为了最大化装载的货物总价值，物流公司需要选择合适的货物装载到货车上，使得总装载体积尽可能接近货车的总容积，但不能超过每辆车的容积限制，且每种货物的数量不能超过库存。问题描述：给定N种货物的体积、价值和数量，以及M辆货车的最大容积V，请计算如何分配货物到货车中，使得所有货车的总装载体积之和最大，但不能超过每辆车的容积限制，且每种货物的数量不能超过库存。输入：第一行包含四个整数N，M，V，W，分别表示货物种类数、货车数量、每辆货车的最大容积和每种货物的数量。接下来N行，每行包含三个整数Vi，Pi和Qi，分别表示第i种货物的体积、价值和数量。输出：输出一个整数，表示最大总价值。示例：输入：43155533344822255输出：24解析：选择体积为5的货物1件（价值3）、体积为3的货物2件（价值8）、体积为2的货物2件（价值10），总价值为24，总体积为15，满足三辆货车的容积限制。题目9（10分）：资源分配背景：某科技公司需要将一批设备分配到多个实验室中。实验室中有N种设备，每种设备有若干台，且每种设备的体积不同。公司有M个实验室，每个实验室的最大容积为V。为了最大化资源利用效率，需要选择合适的设备分配到实验室中，使得总分配体积尽可能接近实验室的总容积，但不能超过每个实验室的容积限制，且每种设备的数量不能超过库存。问题描述：给定N种设备的体积、价值和数量，以及M个实验室的最大容积V，请计算如何分配设备到实验室中，使得所有实验室的总分配体积之和最大，但不能超过每个实验室的容积限制，且每种设备的数量不能超过库存。输入：第一行包含四个整数N，M，V，W，分别表示设备种类数、实验室数量、每个实验室的最大容积和每种设备的数量。接下来N行，每行包含三个整数Vi，Pi和Qi，分别表示第i种设备的体积、价值和数量。输出：输出一个整数，表示最大总价值。示例：输入：54205433622533344255输出：24解析：选择体积为4的设备1件（价值3）、体积为6的设备1件（价值2）、体积为5的设备1件（价值3）、体积为3的设备2件（价值8），总价值为24，总体积为20，满足四个实验室的容积限制。答案与解析01背包问题：题目1：输入：3210342552输出：10解析：选择体积为3的物资2件（体积6）和体积为2的物资2件（体积4），总运输体积为10，刚好满足两辆卡车的载重限制。题目2：输入：431553348225输出：15解析：选择体积为5的商品1件（体积5）、体积为3的商品2件（体积6）和体积为2的商品2件（体积4），总装箱体积为15，刚好满足三个箱子的容积限制。题目3：输入：54204362533425输出：20解析：选择体积为4的商品1件（体积4）、体积为6的商品1件（体积6）、体积为5的商品1件（体积5）和体积为2的商品2件（体积4），总分配体积为20，刚好满足四个实验室的容积限制。完全背包问题：题目4：输入：450101025115372输出：45解析：购买体积为1的商品5件（价值5）、体积为2的商品2件（价值12），总价值为45，总重量为8，总花费为50，满足条件。题目5：输入：3100203010405208输出：140解析：投资体积为5的项目4件（收益40）、体积为8的项目1件（收益20），总收益为140，总投资额为100，总风险为20，满足条件。题目6：输入：543202301103402501输出：100解析：分配任务收益为30的任务1件（收益30）、任务收益为40的任务1件（收益40）、任务收益为20的任务2件（收益40），总收益为100，总任务数量为4，满足员工任务限制。多重背包问题：题目7：输入：32105253372491输出：24解析：选择重量为2的食材2件（价值10）、重量为3的食材1件（价值7），总价值为24，总重量为10，满足两辆货车的载重限制。题目8：输入：431555333448222