民族工坊排产：双资源约束下的收益最大化 完整解题档案

档案概况

题目、题干与输入输出

正式题面

源文件：official-prompt.md

规则来源

• 赛项说明页码：15
• 训练题主题：民族工坊排产：双资源约束下的收益最大化
• 所属赛道：民族文化赛道

题目背景

民族工坊要在限定的工时和材料内安排生产。每种产品会消耗不同的工时和材料，并带来不同收益。需要找到最优排产方案。

任务描述

• 读取产品数量、总工时、总材料以及每种产品的资源消耗与收益。
• 每种产品可以生产任意非负整数件，但不能超过总工时和总材料限制。
• 求出最大总收益，并输出对应的每种产品件数。
• 若最大收益有多个方案，选择件数向量按字典序更小的方案。

输入格式

1. 第一行输入 n H M，分别表示产品数量、总工时和总材料。
2. 接下来 n 行，每行输入 name hours materials profit。

输出格式

1. 第一行输出 best_profit=最大收益。
2. 第二行输出 plan=，按输入顺序给出 名称:件数，用英文逗号连接。

数据范围与说明

• 1 <= n <= 8。
• 0 <= H, M <= 60。
• 1 <= hours, materials, profit <= 1000。
• 每种产品可重复生产，因此是完全背包问题。

样例输入

3 8 11
X 2 3 8
Y 3 4 14
Z 4 6 17

样例输出

best_profit=36
plan=X:1,Y:2,Z:0

样例解释

• 生产 X 1 件、Y 2 件会消耗工时 8、材料 11，收益为 36。
• Y 2 件的收益为 28，Z 2 件会超材料限制。
• 因此最优方案是 X:1,Y:2,Z:0。

知识点清单

• 二维资源约束建模。
• 完全背包动态规划。
• 方案恢复。
• 并列最优时的字典序比较。
• 优化题中的状态设计。

约束拆解

源文件：parsed-constraints.md

显式约束

• 1 <= n <= 8。
• 0 <= H, M <= 60。
• 1 <= hours, materials, profit <= 1000。
• 每种产品可重复生产，因此是完全背包问题。

建模拆解

• 先明确输入的实体和字段，再把它们翻译成 二维完全背包 + 方案恢复 需要的数据结构。
• 把输出中每一项指标都和中间变量对应起来，避免最后临时拼装。
• 先用样例手推一次，再确认边界条件是否都能走到正确分支。

易错边界

• 资源上限可能为 0，此时最优收益为 0。
• 多种方案收益相同，需要继续比较件数向量字典序。
• 最优方案不一定恰好用满两种资源。

计分模型

源文件：scoring-model.md

判题方式

• 主判题方式：optimization
• 主算法：二维完全背包 + 方案恢复

判题重点

• 重点校验建模是否正确、最优值维护是否稳定、路径或方案恢复是否完整。
• 隐藏数据会覆盖不可达、同值竞争和多约束并存情形。

公开样例建议

• 至少准备 1 组题面样例、2 组边界样例和 2 组自定义回归样例。
• 多输出题必须验证所有字段都来自同一套方案。

隐藏数据建议

• 验证资源上限为 0 的情况。
• 验证最优方案不满资源但收益最高的情况。
• 验证存在并列收益方案时的字典序比较。

验收清单

源文件：acceptance-checklist.md

• 正式题面、约束拆解、评分说明均已补齐
• 样例输入输出已定义并通过主实现校验
• python 主实现已提供并与样例输出对齐
• cpp 主实现已提供并与样例输出对齐
• 调试记录、决策记录、验证计划已补齐
• 可由 20-tools/assemble_case_dossiers.py 汇总为完整解题档案

样例输入输出

样例输入：sample.in

3 8 11
X 2 3 8
Y 3 4 14
Z 4 6 17

样例输出：sample.out

best_profit=36
plan=X:1,Y:2,Z:0

题解、建模与最终解法

自动整理的解题流程

• 题目主题：民族工坊排产：双资源约束下的收益最大化
• 题目摘要：在工时和材料双重约束下，确定各产品的生产数量，使总收益最大，并输出对应生产方案。
• 判题提示：该题以优化求解为主，重点是约束建模、可行性检查和最优值维护。
• 把题目拆成状态变量和逐步更新规则，明确每轮输入、状态变化和终止条件。
• 优先用样例手推每一步状态，避免分支条件顺序与题意相反。

解题思路

源文件：solution-rationale.md

1. 问题重述

在工时和材料双重约束下，确定各产品的生产数量，使总收益最大，并输出对应生产方案。

2. 数据结构与建模

• 主算法：二维完全背包 + 方案恢复
• 输入拆解后对应的数据结构要和输出项一一对应。
• 需要重点维护的状态包括：题目实体、核心指标、中间结果和最终答案。

3. 算法步骤

1. 把工时和材料作为二维状态，dp[h][m] 记录最大收益与对应方案。
2. 从小到大枚举状态，尝试继续生产每一种产品。
3. 当收益更高，或收益相同但件数向量字典序更小时，更新状态。
4. 遍历所有可行状态，选出全局最优方案并输出。

4. 正确性说明

• 每一步都严格对应题面给出的规则或约束。
• 所有输出字段都来自同一份计算过程，不会出现“各算各的”的不一致情况。
• 边界情况通过单独分支或统一规则处理，保证程序在最小规模和重复值情况下也稳定。

5. 复杂度分析

• 复杂度取决于输入规模和主算法，但整体设计保持在初中组可讲解、可验证的范围内。
• 只保留必要状态，不引入超出题意的数据结构。

6. 易错点

• 资源上限可能为 0，此时最优收益为 0。
• 多种方案收益相同，需要继续比较件数向量字典序。
• 最优方案不一定恰好用满两种资源。

7. 知识点清单

• 二维资源约束建模。
• 完全背包动态规划。
• 方案恢复。
• 并列最优时的字典序比较。
• 优化题中的状态设计。

设计决策记录

源文件：decision-log.md

• 选择 二维完全背包 + 方案恢复 作为主算法，因为它能直接覆盖题目的核心约束。
• 两个资源限制天然对应二维 DP 状态。
• 为了输出最终方案，状态中需要同时保留收益和件数向量。
• Python 与 C++ 版本统一输出格式，便于双语训练和证据采集。

验证计划

源文件：validation-plan.md

• 先验证题面公开样例，确保基础流程无误。
• 验证资源上限为 0 的情况。
• 验证最优方案不满资源但收益最高的情况。
• 验证存在并列收益方案时的字典序比较。
• 最后再补 1 组手工构造的极小数据，确认程序不会依赖特殊输入规模。

备选方案

源文件：alternatives.md

最终代码与实现

Python 主实现

源文件：main.py

• 实现状态：当前已有可执行实现

import sys


def better(left, right):
    if right is None:
        return True
    if left[0] != right[0]:
        return left[0] > right[0]
    return left[1] < right[1]


def solve(data: str) -> str:
    tokens = data.split()
    if not tokens:
        return ""
    it = iter(tokens)
    n = int(next(it))
    limit_h = int(next(it))
    limit_m = int(next(it))
    names = []
    items = []
    for _ in range(n):
        name = next(it)
        hours = int(next(it))
        materials = int(next(it))
        profit = int(next(it))
        names.append(name)
        items.append((hours, materials, profit))
    zero = tuple([0] * n)
    dp = [[None for _ in range(limit_m + 1)] for _ in range(limit_h + 1)]
    dp[0][0] = (0, zero)
    for h in range(limit_h + 1):
        for m in range(limit_m + 1):
            state = dp[h][m]
            if state is None:
                continue
            profit, counts = state
            for index, (hours, materials, value) in enumerate(items):
                nh = h + hours
                nm = m + materials
                if nh > limit_h or nm > limit_m:
                    continue
                next_counts = list(counts)
                next_counts[index] += 1
                candidate = (profit + value, tuple(next_counts))
                if better(candidate, dp[nh][nm]):
                    dp[nh][nm] = candidate
    best = (0, zero)
    for h in range(limit_h + 1):
        for m in range(limit_m + 1):
            state = dp[h][m]
            if state is not None and better(state, best):
                best = state
    plan = ",".join(f"{name}:{count}" for name, count in zip(names, best[1]))
    return f"best_profit={best[0]}\nplan={plan}"


if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()).strip())
    sys.stdout.write("\n")

C++ 对照实现

源文件：main.cpp

• 实现状态：当前已有可执行实现

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct State {
    bool valid = false;
    int profit = 0;
    vector<int> counts;
};

bool better(const State& left, const State& right) {
    if (!right.valid) {
        return true;
    }
    if (left.profit != right.profit) {
        return left.profit > right.profit;
    }
    return lexicographical_compare(left.counts.begin(), left.counts.end(), right.counts.begin(), right.counts.end());
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, limit_h, limit_m;
    if (!(cin >> n >> limit_h >> limit_m)) {
        return 0;
    }
    vector<string> names(n);
    vector<int> hours(n), materials(n), profit(n);
    for (int i = 0; i < n; ++i) {
        cin >> names[i] >> hours[i] >> materials[i] >> profit[i];
    }
    vector<vector<State>> dp(limit_h + 1, vector<State>(limit_m + 1));
    dp[0][0].valid = true;
    dp[0][0].counts.assign(n, 0);

    for (int h = 0; h <= limit_h; ++h) {
        for (int m = 0; m <= limit_m; ++m) {
            if (!dp[h][m].valid) {
                continue;
            }
            for (int i = 0; i < n; ++i) {
                int nh = h + hours[i];
                int nm = m + materials[i];
                if (nh > limit_h || nm > limit_m) {
                    continue;
                }
                State candidate = dp[h][m];
                candidate.valid = true;
                candidate.profit += profit[i];
                candidate.counts[i] += 1;
                if (better(candidate, dp[nh][nm])) {
                    dp[nh][nm] = candidate;
                }
            }
        }
    }

    State best;
    best.valid = true;
    best.profit = 0;
    best.counts.assign(n, 0);
    for (int h = 0; h <= limit_h; ++h) {
        for (int m = 0; m <= limit_m; ++m) {
            if (dp[h][m].valid && better(dp[h][m], best)) {
                best = dp[h][m];
            }
        }
    }

    cout << "best_profit=" << best.profit << "\n";
    cout << "plan=";
    for (int i = 0; i < n; ++i) {
        if (i) {
            cout << ',';
        }
        cout << names[i] << ':' << best.counts[i];
    }
    cout << "\n";
    return 0;
}

代码执行与运行结果

最新成功运行

PY 运行输出摘录

best_profit=36
plan=X:1,Y:2,Z:0

CPP 运行输出摘录

best_profit=36
plan=X:1,Y:2,Z:0

全部运行记录索引

调试、修正与流程留痕

调试日志

源文件：debug-journal.md

失败案例目录

源文件：failure-catalog.md

编码过程记录

源文件：implementation-journal.md

全流程文件导航

• 题目总览：s4-jh-02-production-plan/README.md
• 题面与约束：official-prompt.md、parsed-constraints.md、scoring-model.md、acceptance-checklist.md
• 代码与样例：10-cases/s4-jh-02-production-plan/02-solution
• 运行证据：10-cases/s4-jh-02-production-plan/03-execution
• 调试过程：debug-journal.md、failure-catalog.md、implementation-journal.md
• 解法说明：solution-rationale.md、decision-log.md、validation-plan.md、alternatives.md
• 交付档案：final-report.md、appendix-code.md、appendix-runs.md、evidence-pack.md