百度有哪些网站可免费做软件推广行业资讯网

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

百度有哪些网站可免费做软件推广,行业资讯网,百度网站搜索量提高,国外网站入口Hw 9 1 Scheduling with profits and deadlines12345 2 Parallel machine1234 1 Scheduling with profits and deadlines 1 决策问题表述#xff1a; 给定一个利润值 P P P#xff0c;是否存在一个任务调度方案使得完成所有任务的总利润至少为 P P P 2 在 NP 类中… Hw 9 1 Scheduling with profits and deadlines12345 2 Parallel machine1234 1 Scheduling with profits and deadlines 1 决策问题表述 给定一个利润值 P P P是否存在一个任务调度方案使得完成所有任务的总利润至少为 P P P 2 在 NP 类中 给定一个任务调度方案可以在多项式时间内验证该方案的总利润是否至少为 P P P。验证过程包括检查每个任务是否在截止日期前完成并计算总利润。因此该问题在 NP 类中。 对于 NP 完全性 - 给定一个 0/1 背包问题实例其中有 n n n 个物品每个物品有一个重量 w i w_i wi​ 和价值 v i v_i vi​以及一个总重量限制 W W W。 对应于调度问题中的每个任务 a j a_j aj​设置其处理时间 t j w i t_j w_i tj​wi​利润 p j v i p_j v_i pj​vi​并设置截止日期 d j W d_j W dj​W保证任务必须在总时间 W W W 内完成。利润值 P P P 设为背包问题中的价值总和的要求。 通过归约若能在调度问题中找到一个利润至少为 P P P 的方案则在 0/1 背包问题中可以找到一个总价值至少为 P P P 且总重量不超过 W W W 的物品选择方案。因此调度问题的决策版本是 NP 完全的。 3 状态定义设 d p [ t ] [ k ] dp[t][k] dp[t][k] 表示在总时间 t t t 内选择前 k k k 个任务能获得的最大利润。 状态转移方程 对于每个任务 a j a_j aj​有两种选择 不选择任务 a j a_j aj​ d p [ t ] [ k ] d p [ t ] [ k − 1 ] dp[t][k] dp[t][k-1] dp[t][k]dp[t][k−1]选择任务 a j a_j aj​前提是 t ≥ t j t \geq t_j t≥tj​ 且 t ≤ d j t \leq d_j t≤dj​ d p [ t ] [ k ] max ⁡ ( d p [ t ] [ k − 1 ] , d p [ t − t j ] [ k − 1 ] p j ) dp[t][k] \max(dp[t][k-1], dp[t-t_j][k-1] p_j) dp[t][k]max(dp[t][k−1],dp[t−tj​][k−1]pj​) 初始状态 d p [ 0 ] [ 0 ] 0 dp[0][0] 0 dp[0][0]0表示没有时间且没有任务时的利润为 0。 算法步骤 初始化 d p dp dp 数组为 0。遍历所有任务根据上述状态转移方程更新 d p dp dp 数组。最终检查 d p [ T ] [ n ] dp[T][n] dp[T][n] 是否大于等于 P P P其中 T T T 是计算机的总时间。 4 状态定义设 d p [ t ] dp[t] dp[t] 表示在总时间 t t t 内能获得的最大利润。 状态转移方程 对于每个任务 a j a_j aj​有两种选择 不选择任务 a j a_j aj​ d p [ t ] d p [ t ] dp[t] dp[t] dp[t]dp[t]选择任务 a j a_j aj​前提是 t ≥ t j t \geq t_j t≥tj​ 且 t ≤ d j t \leq d_j t≤dj​ d p [ t ] max ⁡ ( d p [ t ] , d p [ t − t j ] p j ) dp[t] \max(dp[t], dp[t-t_j] p_j) dp[t]max(dp[t],dp[t−tj​]pj​) 初始状态 d p [ 0 ] 0 dp[0] 0 dp[0]0表示没有时间时的利润为 0。 算法步骤 初始化 d p dp dp 数组为 0。遍历所有任务根据上述状态转移方程更新 d p dp dp 数组。最终 d p [ T ] dp[T] dp[T] 即为最大利润其中 T T T 是计算机的总时间。 5 由于上述动态规划算法是一个精确算法在多项式时间内找到最优解因此它的近似比为 1即它能够找到最优解。 2 Parallel machine 1 考虑所有工作中处理时间最长的工作 J k J_k Jk​其处理时间为 p k max ⁡ { p j : 1 ≤ j ≤ n } p_k \max{p_j : 1 \leq j \leq n} pk​max{pj​:1≤j≤n}。 由于该工作必须在某台机器上连续运行 p k p_k pk​ 时间单位且在此期间不能有其他工作在同一台机器上运行因此该工作的完工时间至少为 p k pk pk​。 因此最优完工时间 C max ∗ C^*{\text{max}} Cmax∗​ 必须至少为 p k pk pk​即 C max ∗ ≥ max ⁡ { p k : 1 ≤ k ≤ n } C^*{\text{max}} \geq \max{pk : 1 \leq k \leq n} Cmax∗​≥max{pk​:1≤k≤n}。 2 设所有工作的总处理时间为 P ∑ k 1 n p k P \sum{k1}^{n} pk P∑k1n​pk​。 对于最优调度每台机器在总时间 C max ∗ C^*{\text{max}} Cmax∗​ 内处理一部分工作。 由于共有 m m m 台机器总的工作负载 P P P 必须分配给这 m m m 台机器。因此平均每台机器的负载为 P m \frac{P}{m} mP​。 在最优调度中任意机器的完工时间不能少于其分配到的工作负载时间即最优完工时间 C max ∗ C^_{\text{max}} Cmax∗​ 不能小于平均机器负载 P m \frac{P}{m} mP​即 C max ∗ ≥ 1 m ∑ k 1 n p k C^{\text{max}} \geq \frac{1}{m} \sum{k1}^{n} p_k Cmax∗​≥m1​∑k1n​pk​。 3 def GreedyParallelScheduling(jobs, m):# jobs 是一个由元组 (p_k, job_id) 组成的作业列表# m 是机器的数量# 初始化了一个大小为m的空列表schedules# 用于记录每台机器分配的作业schedules [[] for _ in range(m)]# 初始化了一个大小为m的数组machine_completion_times# 用于记录每台机器的完工时间初始值为0machine_completion_times [0] * m# 对作业列表按照处理时间的非递增顺序进行排序jobs.sort(reverseTrue, keylambda x: x[0])# 对每个已排序的作业进行调度for (p_k, job_id) in jobs:# 找到完工时间最小的机器 Mimin_machine machine_completion_times.index(min(machine_completion_times))# 将作业分配给机器 Mischedules[min_machine].append(job_id)# 更新机器 Mi 的完工时间增加该作业的处理时间machine_completion_times[min_machine] pkreturn schedules运行时间: 初始化和读取输入需要 O ( n ) O(n) O(n) 时间。对作业按处理时间排序需要 O ( n log ⁡ n ) O(n \log n) O(nlogn) 时间。遍历每个作业并找到具有最小结束时间的机器需要 O ( n log ⁡ m ) O(n \log m) O(nlogm) 时间因为可以使用最小堆来跟踪机器的结束时间。 总体运行时间为 O ( n log ⁡ n n log ⁡ m ) O ( n log ⁡ n ) O(n \log n n \log m) O(n \log n) O(nlognnlogm)O(nlogn)因为通常情况下 n ≥ m n \geq m n≥m。 4 设所有工作的总处理时间为 P ∑ k 1 n p k P \sum{k1}^{n} pk P∑k1n​pk​处理时间最长的工作为 p max max ⁡ { p k : 1 ≤ k ≤ n } p{\text{max}} \max{pk : 1 \leq k \leq n} pmax​max{pk​:1≤k≤n}。 在贪心算法中任何时刻将未分配的工作分配给当前空闲时间最少的机器这种策略确保每台机器的负载是尽可能均衡的。 假设最坏情况下某台机器上的负载时间为 L L L即 L ≤ P m p max L \leq \frac{P}{m} p{\text{max}} L≤mP​pmax​ 其中 P m \frac{P}{m} mP​ 是平均每台机器分配到的负载时间 p m a x p{max} pmax​ 是任何单个工作可能增加的最大负载时间。 因此贪心算法的完工时间 C m a x C{max} Cmax​ 满足 C max ≤ 1 m ∑ k 1 n p k max ⁡ { p k : 1 ≤ k ≤ n } C{\text{max}} \leq \frac{1}{m} \sum{k1}^{n} p_k \max{pk : 1 \leq k \leq n} Cmax​≤m1​k1∑n​pk​max{pk​:1≤k≤n} 由于最优完工时间 C m a x ∗ C^*{max} Cmax∗​ 至少为这两个量中的最大值即 C m a x ∗ ≥ max ⁡ ( 1 m ∑ k 1 n p k , max ⁡ { p k : 1 ≤ k ≤ n } ) C^{max} \geq \max \left(\frac{1}{m} \sum{k1}^{n} p_k, \max{pk : 1 \leq k \leq n}\right) Cmax∗​≥max(m1​k1∑n​pk​,max{pk​:1≤k≤n}) 结合以上两个不等式可得 C m a x ≤ 2 C m a x ∗ C{max} \leq 2C^_{max} Cmax​≤2Cmax∗​ 因此贪心算法是一个多项式时间的 2-近似算法。