动态规划 -- 活动时间问题
活动时间问题描述:有n个需要在同一天使用同一个教室的活动a1,a2,…,an,教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后,活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠,ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行(最大兼容活动子集)。动态规划法代码实现:us...
动态规划--C#求解01背包
背包问题(Knapsack problem)是一种组合优化的NP完全问题。给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。应用:背包问题出现在各种领域的现实世界的决策过程中,例如寻找最少浪费的方式来削减原材料, 选择投资和投资组合,选择资产支持资产证券化 ,和生成密钥为Merkle-Hellman 和其他背包密码系统1,穷举法(把所有情况列出来...
动态规划 -- 钢条切割
动态规划(Dynamic Programming)什么是动态规划,我们要如何描述它?动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。动态规划和分治法相似,都是通过组合子问题的解来求解原问题。分治法将问题划分成互不相交的子问题,递归求解子问题,再将他们的解组合起来,求出原问题的解。与之相反,动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题...
堆排序 -- C#代码实现
using System;namespace _3_1_1堆排序_顺序存储{ class Program { static void Main(string[] args) { int[] data = { 50, 10, 90, 30, 70, 40, 80, 60, 20 }; HeapSort(data); foreach (int item i...
堆的简介以及堆排序
什么是堆?堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。堆分为大顶堆和小顶堆,满足:Key[i]>=Key[2i+1]&...