当前位置：首页 > article >正文

【蓝桥】线性DP--最快洗车时间

article 2025/2/19 8:03:22

题目描述

解题思路

完整代码

举例

总结

基于 0/1 背包思想 解决洗车时间分配问题，本质上是子集和问题【给定一个正整数数组 nums 和一个目标值 target，判断是否可以从 nums 选择若干个数（每个数最多选一次），使其和恰好等于 target】

题目描述

解题思路

一开始用的使用了排序+贪心的方法：

对洗车时间从大到小排序（先分配长时间的任务）。
优先分配给当前时间较短的那个人（类似负载均衡）。
遍历数组，依次分配，最终返回 max(wash1, wash2)

但这种思路是错的，求的是局部最优解，局部最优不一定导致全局最优，即在每一步都选择当前看起来最好的方案，并不一定能得到最优解。

正确方法：设所有洗车时间之和为 total，我们希望 找到一个子集，使得其和 best 尽可能接近 total / 2。这样 max(best, total - best) 就是两人最优的洗车时间

1. 定义状态

设 dp[j] 表示是否可以从数组 nums 中选取若干个数，使得它们的和为 j：

dp[j] = true 表示存在一个子集的和恰好等于 j；
dp[j] = false 表示无法找到这样的子集。

2. 状态转移方程

对于当前遍历的 nums[i]：

如果不选 nums[i]，那么 dp[j] 由前一轮 dp[j] 继承；
如果选 nums[i]，那么 dp[j] 取决于 dp[j - nums[i]] 是否为 true，即如果 j - nums[i] 之前是可行的，那么 j 也是可行的。

状态转移方程：

3. 初始化

dp[0] = true（因为总和为 0 的子集是空集，肯定可以达到）。
其他 dp[j] 初始设为 false。

4. 遍历顺序

外层循环 遍历 nums[i]（每个数只能选一次，必须按顺序遍历）。
内层循环 采用逆序 for (int j = target; j >= nums[i]; j--)，确保 nums[i] 只被选取一次。
最终遍历最终的DP数组，从 target 开始向 0 逆序查找 最大的 i，满足 dp[i] == true

完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110; // 设定数组大小
bool dp[N];  // 0/1 背包 DP 数组
int car[N];  // 存储每辆车的洗车时间
int n, target, total; // 变量定义

int main() {
    cin >> n; // 读取车辆数量
    for (int i = 1; i <= n; i++) {
        cin >> car[i];
        total += car[i]; // 计算洗车时间总和
    }

    target = total / 2; // 目标是尽量分成两半
    dp[0] = true; // 初始状态，和为 0 一定是可行的

    for (int i = 1; i <= n; i++) { // 遍历每辆车
        for (int j = target; j >= car[i]; j--) { // 逆序遍历
            dp[j] = dp[j] || dp[j - car[i]];
        }
    }

    int best = 0;
    // 找到最接近 total/2 的可行解
    for (int i = target; i >= 0; i--) { 
        if (dp[i]) {
            best = i;
            break;
        }
    }

    cout << max(best, total - best); // 计算最短最大时间
    return 0;
}

举例

n = 4
car = [8, 6, 5, 5]
total = 8 + 6 + 5 + 5 = 24
target = total / 2 = 24 / 2 = 12

初始化dp

dp = [true, false, false, ..., false]  // 长度为 target + 1，即 13

第 1 辆车 (洗车时间 8)：

dp[12] = dp[12] || dp[12 - 8] = false || dp[4] = false
dp[11] = dp[11] || dp[11 - 8] = false || dp[3] = false
dp[10] = dp[10] || dp[10 - 8] = false || dp[2] = false
dp[9] = dp[9] || dp[9 - 8] = false || dp[1] = false
dp[8] = dp[8] || dp[8 - 8] = false || dp[0] = true   // dp[8] = true

第 2 辆车 (洗车时间 6)：

dp[12] = dp[12] || dp[12 - 6] = false || dp[6] = false
dp[11] = dp[11] || dp[11 - 6] = false || dp[5] = false
dp[10] = dp[10] || dp[10 - 6] = false || dp[4] = false
dp[9] = dp[9] || dp[9 - 6] = false || dp[3] = false
dp[8] = dp[8] || dp[8 - 6] = true  || dp[2] = false
dp[7] = dp[7] || dp[7 - 6] = false || dp[1] = false
dp[6] = dp[6] || dp[6 - 6] = false || dp[0] = true   // dp[6] = true

.......

最终

dp = [true, false, false, false, false, true, true, false, true, true, true, true, false]

总结

✅ 转换成 0/1 背包问题，利用 动态规划 解决。
✅ dp[j] 表示是否能凑出 j 这个和，递推转移 dp[j] = dp[j] || dp[j - car[i]]。
✅ 时间复杂度 O(n * sum/2)，适用于 sum ≤ 10^4。
✅ 贪心方法可能失效，而动态规划保证最优解。