#6001. [ZROI] 线性规划

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: long_hao

题目描述

给定三个长度为 n 的数列:{𝑎1, 𝑎2 … 𝑎𝑛},{𝑏1, 𝑏2 … 𝑏𝑛 },{𝑐1, 𝑐2 … 𝑐𝑛},且

∀ⅈ ∈ [1, 𝑛], 𝑎𝑖 ≤ 𝑏𝑖

需要满足约束:

𝑎1𝑥1 + 𝛼2𝑥2 + ⋯ + 𝛼𝑛𝑥𝑛 ≤ 𝑃

𝑏1𝑥1 + 𝑏2𝑥2 + ⋯ + 𝑏𝑛𝑥𝑛 ≥ 𝑃

∀ⅈ ∈ [1, 𝑛], 𝑥𝑖 ∈ {0,1}

最小化

𝑤 = 𝑐1𝑥1 + 𝑐2𝑥2 + ⋯ + 𝑐𝑛𝑥