最小机器重量设计问题

问题描述

设某一机器由 n 个部件组成，部件编号为 0 到 n-1。每一种部件都可以从 m 个供应商处购得，供应商编号为 0 到 m-1。设 w[i][j] 是从供应商 j 处购得的部件 i 的重量，c[i][j] 是相应的价格。

本项目旨在设计一个算法，用于求解在总价格不超过给定成本 cost 的前提下，如何选择每个部件的供应商，以使得整台机器的总重量最小。

---

算法思想与原理详解

这个问题本质上是一个多阶段决策过程，我们需要为每个部件做一次决策（选择哪个供应商），最终使得总体目标（总重量）最优。这类问题是动态规划（Dynamic Programming, DP）的经典应用场景。

1. 核心思想：化繁为简，分而治之

动态规划的核心思想是将一个复杂的大问题分解为一系列更小的、可管理的子问题。通过解决这些子问题，并将其结果存储起来，最终组合出大问题的解。关键在于，这些子问题之间不是完全独立的，后一阶段的决策依赖于前一阶段的结果。

对于本问题，我们可以这样分解：

• 大问题：为 n 个部件选择供应商，在成本约束下实现重量最轻。
• 子问题：为前 i 个部件（i < n）选择供应商，在某个特定成本 j 下，能实现的最小重量是多少？

如果我们知道了所有关于前 i-1 个部件的子问题的答案，我们就可以利用这些答案来解决关于前 i 个部件的子问题。

2. 状态定义：构建决策表

我们需要一个“表格”来记录所有子问题的解。在动态规划中，这个表格通常是一个数组（或矩阵），我们称之为 状态。

我们定义一个二维数组 dp[i][j] 作为我们的核心状态表：

• dp[i][j] 的含义：组装前 i 个部件（即部件 0 到部件 i-1），花费总成本恰好为 j 时，所能达到的最小总重量。

如果某个状态 dp[i][j] 无法实现（例如，用 i 个部件无论如何也凑不出成本 j），我们就将其值设为一个极大值（例如 Integer.MAX_VALUE），表示此路不通。

3. 状态转移：如何从子问题推导出最终解

状态转移是动态规划的灵魂，它定义了子问题之间如何关联。我们的目标是填充整个 dp 表。

假设我们正在计算 dp[i][j]，即考虑前 i 个部件、总成本为 j 的情况。这个状态可以由“组装好前 i-1 个部件”的状态推导而来。具体来说：

1. 我们为第 i 个部件（在数组中索引为 i-1）选择一个供应商 k。
2. 这个选择会带来 c[i-1][k] 的成本和 w[i-1][k] 的重量。
3. 那么，留给前 i-1 个部件的预算就只剩下 j - c[i-1][k]。
4. 我们从 dp 表中查询“用 j - c[i-1][k] 的成本组装前 i-1 个部件的最小重量”，这个值就是 dp[i-1][j - c[i-1][k]]。
5. 因此，选择供应商 k 得到的总重量就是 dp[i-1][j - c[i-1][k]] + w[i-1][k]。

我们需要对第 i 个部件的所有供应商 k（从 0 到 m-1）都进行上述计算，然后取其中的最小值，作为 dp[i][j] 的最终解。

这就得到了状态转移方程：

dp[i][j] = min( dp[i-1][j - c[i-1][k]] + w[i-1][k] )  (对于所有供应商 k = 0..m-1)

4. 初始化：确定起点

算法需要一个起始点。对于第一个部件（i=1，即索引为 0），我们不需要依赖之前的状态。我们可以直接填充 dp 表的第一行：

对于部件 0 的每一个供应商 k，如果其成本为 c[0][k] 且不超预算，那么 dp[1][c[0][k]] 的值就是其重量 w[0][k]。

5. 最终答案：从表格中寻找最优解

当整个 dp 表格填充完毕后，dp[n][j] 存储了用 n 个部件、成本为 j 时的最小重量。由于题目要求是总成本不超过 maxCost，我们需要在 dp 表的最后一行中，寻找从成本 0 到 maxCost 范围内的最小值。

minWeight = min(dp[n][j]) (对于所有 j 从 0 到 maxCost)

6. 回溯：重建最优路径

dp 表只告诉我们最小重量是多少，但没告诉我们是如何达到的。为了知道每个部件具体选择了哪个供应商，我们需要在计算 dp 表时，额外用一个 path[i][j] 数组记录下导致 dp[i][j] 取到最小值的那个供应商 k。

在找到最终的最优总成本 finalCost 后，我们就可以从 path[n][finalCost] 开始，一步步反向推导出每个部件的选择，最终重建出完整的解决方案。

---

示例

输入

• 部件数量 n = 3
• 供应商数量 m = 3
• 最大成本 cost = 7
• 重量矩阵 w = {{1,2,3}, {3,2,1}, {2,3,2}}
• 价格矩阵 c = {{1,2,3}, {5,4,2}, {2,1,2}}

输出

0: 0
1: 2
2: 0
sum weight = 4
cost = 5

这个结果表示：

• 部件 0 选择供应商 0 (重量 1, 成本 1)
• 部件 1 选择供应商 2 (重量 1, 成本 2)
• 部件 2 选择供应商 0 (重量 2, 成本 2)

最终得到总重量为 1+1+2 = 4，总成本为 1+2+2 = 5，该成本在预算 7 以内，且是所有可行方案中重量最轻的。

如何运行

在 IDE 中一键运行

1. 环境准备: 确保您的开发环境中已安装 OpenJDK 24 或更高版本。
2. 项目设置: 在 IntelliJ IDEA 中，请确保项目的语言级别设置为 SDK 默认级别。
3. 运行: 打开 src/main/java/org/example/Main.java 文件，您会看到 main 方法旁边有一个绿色的 ▶️ 图标。点击此图标，然后选择 "Run 'Main.main()'" 即可一键运行程序。
4. 自定义测试: 您可以直接在 main 方法中修改输入参数（n, m, cost, w, c）来测试不同的场景。

从命令行运行

1. 环境准备: 确保您的终端环境中可以访问 javac 和 java 命令 (需要 OpenJDK 24 或更高版本)。
2. 编译: 在项目的根目录 (untitled1) 下，运行以下命令来编译源代码：

   javac -d out src/main/java/org/example/Main.java

3. 运行: 编译成功后，运行以下命令来执行程序：

   java -cp out org.example.Main

4. 自定义测试: 如果需要修改输入，请直接编辑 src/main/java/org/example/Main.java 文件，然后重新执行步骤 2 和 3。