浅谈数据的合理组织

浅 谈 数 据 的 合 理 组 织 引 子 题 目 越 来 越 难 数 据 关 系 越 来 越 复 杂 ！对 组 织 数 据 的 要 求 越 来 越 高 ！合 理 组 织 在 解 题 中 越 来 越 重 要 ！ 【 题 意 描 述 】给 出 N个 物 品 ， 每 个 物 品 都 有 一 个 权 值 (50000)和 一 个 价 格(10000)。 我 们 称 可 以 直 接 被 购 买 的 物 品 为 主 件 ， 称 不 能 被 直接 购 买 的 物 品 为 附 件 ， 附 件 只 有 当 其 主 件 被 购 买 了 才 能 被 购 买 ，一 个 主 件 最 多 有 两 个 附 件 ， 附 件 没 有 下 一 级 附 件 。【 任 务 】用 不 超 过 M元 钱 ， 购 买 一 些 物 品 ， 使 得 被 购 买 的 物 品 的 总 权 值 最大 。金 明 的 预 算 方 案【 数 据 规 模 】N60 M3200 题 目 中 给 出 的 主 件 与 附 件 间 形 成 树 形 结 构 ， 而 所 有 的 物 品 间 形成 森 林 结 构 。 为 了 方 便 起 见 ， 我 们 给 所 有 的 主 件 都 加 上 一 个 “上 级 主 件 ” ， 这 样 ， 所 有 的 物 品 形 成 了 一 棵 树 。数 据 的 初 步 组 织 树 形 动 态 规 划 算 法 !算 法 1状 态 Fij表 示 给 以 i为 根 的 子 树 ， 总 共 花 费 不 超 过 j元 ，所 能 取 得 的 最 大 权 值 和 。? ? ?枚 举 量 太 大 ， 效 率 不 高 ！总 花 费 不 超 过 j 用 左 儿 子 右 兄 弟 表 示 法 来 表 示 这 一 棵 树 ！时 间 复 杂 度 为 O(NM2)状 态 总 数 O(MN)状 态 转 移 代 价 O(M)N*M*M=6*108 ， 不 太 理 想 。状 态 Fij表 示 以 i为 根 的 子 树 总 共 花 费 j元 能 获 得 的 最 大 权 值 和 。我 们 只 需 要 枚 举 给 左 子 树 分 配 多 少 钱 ， 剩 下 的 钱 都 分 给 右 子 树 。 我 们 把 配 套 的 主 件 和 附 件 看 成 一 组 。这 样 ， 显 然 对 于 每 一 组 ， 可 能 的 购 买 方 案 最 多 只 有 如 下 五 种 ：我 们 换 一 种 数 据 组 织 方 式1. 附 件 没 有 附 件 。2. 每 个 主 件 最 多 只 有 两 个 附 件 。考 虑 本 题 特 殊 条 件 ： 1.什 么 都 不 买2.只 购 买 主 件3.购 买 主 件 和 附 件 14.购 买 主 件 和 附 件 25.全 购 买 类 似 经 典 的 - 背 包 问 题 ！组 织 数 据 后 ， 我 们 可 以 得 到 复 杂 度 为 O(NM)的 优 秀 算 法 状 态 总 数 O(MN) 状 态 转 移 代 价 O(1) 郁 闷 的 金 明【 题 意 描 述 】给 出 N个 物 品 ， 每 个 物 品 都 有 一 个 权 值 (50000)和 一 个 价 格(10000)。 我 们 称 可 以 直 接 被 购 买 的 物 品 为 主 件 ， 称 不 能 被 直接 购 买 的 物 品 为 附 件 ， 附 件 只 有 当 其 主 件 被 购 买 了 才 能 被 购 买 ，主 件 可 以 有 任 意 多 附 件 ， 附 件 没 有 下 一 级 附 件 。【 任 务 】用 不 超 过 M元 钱 ， 购 买 一 些 物 品 ， 使 得 被 购 买 的 物 品 的 总 权 值 最大 。【 数 据 规 模 】 N60 M3200 题 目 放 宽 了 “ 一 个 主 件 最 多 可 以 有 两 个 附 件 ” 这 个 限 制 。问 题 分 析 数 据 组 织 方 式 依 然 适 用 效 率以 物 品 为 节 点 的 树 形 结 构 以 组 为 元 素 的 序 列 -我 们 回 想 上 题 的 数 据 组 织 方 式 。 重 新 安 排 这 些 物 品 的 顺 序 ， 使 得 每 个 附 件 都 紧 跟 其 主 件 ， 保证 其 前 面 的 最 近 的 主 件 就 是 它 附 属 的 主 件 。 如 下 图 ：数 据 组 织 方 案 二主 件 1 附 件 主 件 2 附 件 附 件 主 件 3 附 件 附 件 附 件附 件树 序 列 状 态 Fijk表 示 从 第 i个 物 品 到 第 n个 物 品 ， 最 多 花 费 j元 ， k表 示 i物 品 前 面 的 主 件 有 没 有 被 购 买 ， 的 最 大 价 值 和 。这 样 组 织 数 据 以 后 ， 一 个 附 件 能 被 购 买 的 必 要 条 件 是 “ 其 前 面 的 最近 的 主 件 被 购 买 了 ” 。算 法 3主 件 1 附 件 主 件 2 附 件 附 件 主 件 3 附 件 附 件 附 件附 件K=0 主 件 2没 有 被 购 买1 主 件 有 被 购 买 状 态 总 数 O(NM*2) 状 态 转 移 代 价 O(1) 时 间 复 杂 度 O(NM)算 法 3 重 新 组 织 数 据 后 ， 我 们 再 次 成 功 地 设计 出 了 O(NM)的 算 法 。 【 题 意 描 述 】给 出 N个 物 品 ， 每 个 物 品 都 有 一 个 权 值 (50000)和 一 个 价 格(10000)。 我 们 称 可 以 直 接 被 购 买 的 物 品 为 主 件 ， 称 不 能 被 直接 购 买 的 物 品 为 附 件 ， 附 件 只 有 当 其 主 件 被 购 买 了 才 能 被 购 买 ，主 件 可 以 有 任 意 多 附 件 ， 可 以 有 多 级 附 件 。很 郁 闷 的 金 明【 任 务 】用 不 超 过 M元 钱 ， 购 买 一 些 物 品 ， 使 得 被 购 买 的 物 品 的 总 权 值 最大 。【 数 据 规 模 】N60 M3200 现 在 的 题 目 在 原 题 的 基 础 条 件 上 不 仅 增 加 附 件 的 个 数 ， 还 出 现了 多 级 附 件 。问 题 分 析 这 是 很 一 般 的 树 ！ 一 般 的 树 形 结 构 ， 我 们 还 能 不 能 用 前 面 的 数 据 组织 方 式 呢 ？数 据 组 织 方 式 依 然 适 用 效 率以 物 品 为 节 点 的 树 形 结 构 以 组 为 元 素 的 序 列 附 件 紧 跟 其 主 件 的 序 列 说 明 这 些 数 据 组 织 方 式 都 不 合 理 ， 需 要 再 次 重 新 组 织 数 据 ！ 现 在 我 们 再 回 过 头 来 研 究 一 下 前 面 一 种 数 据 组 织 方 式 ：把 同 在 一 个 组 的 主 件 放 在 附 件 的 前 面 ， 将 树 形 问 题 转 化 到 序列 上 来 。而 现 在 的 问 题 是 ： 树 的 高 度 增 加 了 。组 织 数 据 方 案 三考 虑 ： 树 的 先 根 遍 历 序 。 仔 细 思 考 算 法 3的 状 态 转 移 ：主 件 1 附 件 主 件 2 附 件 附 件 主 件 3 附 件 附 件 附 件附 件K=0迁 移 到 本 题 中 ， 对 于 一 棵 子 树 ， 如 果 我 们不 购 买 其 根 结 点 ， 那 么 其 子 孙 都 不 必 讨 论了 （ 因 为 其 子 孙 节 点 都 不 能 被 购 买 ）但 是 我 们 不 能 用 加 一 维 的 方 法 来 记 录 每个 附 件 的 主 件 是 否 被 购 买 了 ！ 这 一 结 论 似 乎 很 显 然 ， 但 是 我 们 并 不 是 要 在 树 形结 构 中 运 用 这 一 结 论 。正 如 上 面 提 到 的 ， 我 们 要 在 树 的 先 根 遍 序 上 进 行 动态 规 划 ， 而 这 一 结 论 正 是 我 们 成 功 的 关 键 。 状 态 Fij表 示 在 遍 历 序 列 中 从 第 i个 物 品 到 第 n个 物 品 ， 最 多花 费 j元 ， 能 得 到 的 最 大 权 值 和 。算 法 4主 件 1 附 件 主 件 2 附 件 附 件 主 件 3 附 件 附 件 附 件附 件没 有 购 买 根 结 点 ！直 接 “ 跳 ” 过 去 ！ 状 态 总 数 O(NM) 状 态 转 移 代 价 O(1) 时 间 复 杂 度 O(NM)重 新 组 织 数 据 后 ， 我 们 再 一 次 优 解 此 题 。算 法 4 这 样 ， 实 际 上 我 们 避 开 了 “ 记 录 主 件 状 态 ”的 问 题 ！ 成 功 地 实 现 了 状 态 的 合 法 转 移 小 结 树 形 结 构 树 形 动 态 规 划 O(NM2)线 形 结 构合 理 地 组 织 数 据线 形 动 态 规 划 O(NM) 【 题 意 描 述 】给 出 一 棵 有 N个 节 点 的 有 根 树 （ 根 为 1号 节 点 ） ， 每 个 节 点 有 权值 。要 求 对 于 每 一 个 节 点 ， 求 ：1.其 子 树 中 权 值 比 该 节 点 大 的 节 点 总 数2.树 上 所 有 比 该 节 点 大 的 节 点 总 数3.从 根 节 点 到 该 节 点 路 径 中 比 该 节 点 大 的 节 点 总 数其 中 (1=N=105) 树 的 果 实 问 题 分 析 树 形 上 的 统 计 问 题 ！序 列 上 的 统 计 问 题 。 对 数 据 的 初 步 组 织我 们 进 行 新 的 组 织 数 据 的 尝 试 ： 利 用 先 根 遍 历 序 将 树 转 化为 序 列 ， 因 为 这 样 ， 同 一 棵 子 树 构 成 一 个 连 续 的 区 间 ， 这是 一 个 非 常 好 的 性 质 。问 题 转 化 为 ： 在 一 个 由 整 数 构 成 的 序 列 上 ， 进 行 N次 区 间 询问 。 询 问 一 个 区 间 中 有 多 少 元 素 的 权 值 比 给 定 的 值 大 。 在 组 织 后 的 数 据 中 尝 试 求 解我 们 直 接 在 组 织 成 序 列 的 数 据 中 进 行 统 计 。 可 以 利 用 以有 序 表 为 元 素 的 线 段 树 ！每 次 统 计 的 时 间 复 杂 度 为 O(log 22(N) 总 的 时 间 复 杂 度 为 O(Nlog22(N) 预 处 理 归 并 排 序 O(Nlog2(N) 我 们 重 新 考 虑 转 化 后 的 问 题 。进 一 步 组 织 数 据答 案 即 是 区 间 中 的 元 素 个 数 ！这 是 线 段 树 和 树 状 数 组 的 看 家 本 领 !考 虑 一 种 特 殊 的 情 况 ： 当 前 的 序 列 中 所 有 元 素 的 权 值 均 大 于 给 定 的 值 。 一 个 很 巧 妙 的 方 法 ： 从 大 到 小 地 向 线 段 树 里 面 依 次 加 入 元素 ， 边 加 边 统 计 。3 2 4 5 1 7 6 67 6 6 5 4 3 1 1 3 2 4 5 1 7 6 6排 序依 次 插 入 并 统 计这 样 ， 我 们 的 总 时 间 复 杂 度 为 O(Nlog2(N) 小 结 树序 列 嵌 套 数 据 结 构“从 大 到 小 ”组 织 “ 形 态 ” 一 般 数 据 结 构组 织 “ 顺 序 ” 以 上 我 们 从 几 个 例 题 介 绍 了 “ 数 据 的 合 理 组织 ” 的 重 要 性 及 其 在 解 题 中 的 一 些 应 用 ， 然而 例 题 只 是 一 部 分 题 目 的 代 表 ， 具 体 的 题 目应 该 具 体 分 析 。总 结 没 有 最 合 理 的 数 据 组 织 方 式 ！ 多 思 考 ， 多 总 结 ，多 实 践 ， 才 是 万 能 的 解 题 之 道 。 谢 谢