公司网站建网,建设掌上银行官方网站,小程序ui设计,网站app免费制作软件题目描述
解题思路
完整代码
举例
总结 基于 0/1 背包思想 解决 洗车时间分配问题#xff0c;本质上是子集和问题【给定一个 正整数数组 nums 和一个目标值 target#xff0c;判断是否可以从 nums 选择 若干个数#xff08;每个数最多选一次#xff09;#xff0c;使…题目描述
解题思路
完整代码
举例
总结 基于 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 表示存在一个子集的和恰好等于 jdp[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。 ✅ 贪心方法可能失效而动态规划保证最优解。
