http://200yi.com/ff_internal/ 2026-05-25T14:46:07+0800 http://200yi.com/ff_internal/ http://200yi.com/ff_internal/lib/tpl/mnml-blog/images/favicon.ico text/html 2023-06-17T21:25:19+0800 Anonymous (anonymous@undisclosed.example.com) http://200yi.com/ff_internal/wiki.php?id=wiki:%E7%AE%97%E6%B3%95:Hash%E7%AE%97%E6%B3%95%E6%A6%82%E8%BF%B0&rev=1687008319&do=diff 哈希函数（hash function） 哈希表是一种通过 keys 对 value 的映射，来实现数据访问的数据结构，而这种映射一般分为两个阶段： * 将关键字 key 作为自变量， 通过一定的函数关系，计算出的因变量作为 value 的索引（index）。 text/html 2023-06-17T21:25:19+0800 Anonymous (anonymous@undisclosed.example.com) http://200yi.com/ff_internal/wiki.php?id=wiki:%E7%AE%97%E6%B3%95:Knapsack%20Problem&rev=1687008319&do=diff 摘自：https://zhuanlan.zhihu.com/p/136244119 1. Greedy Algorithm * 每个问题都有多种贪婪算法 * 在遇到一个新问题时，可首先采用贪婪算法作为Baseline。 2. Modeling （1）决策变量 （Decision Variables） Xi定义为第 i 个物品是否被选择$$ \sum_{i \in I} w_ix_i < K $$$$ \sum_{i \in I} v_ix_i $$$$ maximize \sum_{i \in I} v_ix_i $$$$ subject\ to \sum_{i \in I} w_ix_i < K $$$$ x_i \in \{0,1\} ( i \in I) $$ text/html 2023-06-17T21:25:19+0800 Anonymous (anonymous@undisclosed.example.com) http://200yi.com/ff_internal/wiki.php?id=wiki:%E7%AE%97%E6%B3%95:Knapsack%EF%BC%88%E8%83%8C%E5%8C%85%EF%BC%89%E9%97%AE%E9%A2%98&rev=1687008319&do=diff 摘自：https://blog.csdn.net/u010900754/article/details/53937804 Knapsack（背包）问题 Problem：给定n件物品，每一件物品有价值vi和重量wi，给定一个容量为W的箱子，要求用在不超过箱子容量的前提下，装入价值尽可能多的物品。 这个问题分为两个版本，一种是fractional，即每件物品是可拆分的，另一种是01类型的，即每件物品要么全拿要么不拿。 text/html 2023-06-17T21:25:19+0800 Anonymous (anonymous@undisclosed.example.com) http://200yi.com/ff_internal/wiki.php?id=wiki:%E7%AE%97%E6%B3%95:%E7%AE%97%E6%B3%95%E5%B8%B8%E7%94%A8%E6%9C%AF%E8%AF%AD&rev=1687008319&do=diff GCD：Greatest Common Divisor，最大公约数 LCM：Least Common Multiple，最小公倍数 erf：误差函数（也称之为高斯误差函数，error function or Gauss error function） erfc：互补误差函数 exp：e为底的指数函数