JAVA认证基础知识:近似算法(格雷厄姆算法)简介
来源:才华咖 本文已影响2.59W人
来源:才华咖 本文已影响2.59W人
之前做了很多贪心算法,他们都能找到最优解,这也是之所以用贪心算法的原因。贪心算法较之其他,最大的优势体现在时间复杂度低,空间复杂度也比较低。对于试用贪心算法的题型,有两个重要特征:贪心策略与最优子结构。贪心策略即每步采取策略的依据;最优子结构则是指问题的'求解可以转化为求解子问题的最优解。这点与动态规划有点像,但后者要枚举问题的解空间,资源消耗很大。
贪心算法不一定保证得到最优解,但很多时候用其他方法的无效(有的是确实没有解决方法,有的是复杂度难以接受),在这种情况下我们可以尝试用近似算法,根据一定的有效贪心策略,哪怕得不到最优解,但权衡之下也是可以接受的。
例如给定若干物品,要求尽可能的将它们分成质量相近的两堆。如物品数为5,重量分别为3,3,2,2,2,很容易根据经验判断分成3+3和 2+2+2的两堆。但这是一个2^n级难题,数据量一大就出现组合爆炸。解决该问题目前还没有无有效的方法。枚举法可以得到最优解,但时间复杂度为 O(2^n),难以接受。下面是n<=15时的枚举法,用位操作简化计算。
#include
#include
using namespace std;
const int MAXN=20;
int w[MAXN];
int used[MAXN];
const int INF=1<<30;
int n,id,sum;
int Solve()
{
int min,cnt=1
memset(used,0,sizeof(used));
for(int i=0;i>w[i];
int ans=Solve();
for(int i=0;i运行结果为:2+2+2=6 3+3=6
格雷厄姆提出了解决该问题的近似算法。即每次从尚未分堆的物品中选择最大我w[i]的,然后分别将它试探性加到已分的两堆(a1,b1)中,若|a1+w[i]-b1|>|a1-w[i]-b1|,泽加到b1中;否则加到
a1中。已有神牛可以证明这样的最终结果与最优解的误差不超过16%。下面是格雷厄姆算法的实现。
#include
#include
#include
using namespace std;
const int MAXN=20;
int w[MAXN];
int used[MAXN];
int n,a,b;
void Solve()
{
sort(w,w+n);
a=0,b=0;
for(int i=n-1;i>=0;i--)
{
if(abs(a+w[i]-b)<=abs(a-w[i]-b))
{
a+=w[i];
used[i]=true;
}
else b+=w[i];
}
}
int main()
{
cin>>n;
memset(used,0,sizeof(used));
for(int i=0;i>w[i];
Solve();
printf(" 第一堆为:");
for(int i=0;i运行结果为:2+2+3=7 2+3=7
在有些情况下是完全可以接受近似算法的。
JAVA认证基础知识:基于反射机制的服务代理调用
Java认证考试知识点:JavaSE6的新功能
JAVA认证基础知识:JSP使用数据库操作
JAVA基础知识:简单介绍form的提交方式
JAVA认证开源技术:关于Java的对象equals方法
2016年JAVA认证基础知识:基于反射机制的服务代理调用
Java入门基础知识:Java IO(输入/输出)
Java基于余弦方法实现的计算相似度算法示例
Java计算机基础知识
Java认证考试知识点:Java时间类的函数
计算机二级考试JAVA基础知识:创建窗口
计算机二级考试JAVA基础知识:线程
计算机二级考试JAVA基础知识:组件和容器
JAVA认证基础知识:JavaNativeInterface学习小结
计算机二级考试java基础知识
计算机二级考试《Java》代码的基本知识
java se基础知识介绍
Java基本语法—java标识符
税法基础知识
Sun认证Java程序员(SCJP)考试科目介绍
JAVA认证基础知识:近似算法(格雷厄姆算法)简介
零基础如何学习Java运算符
计算机基础认识实习报告
sun认证java基础模拟试题
计算机二级考试Java知识点:创建窗口
合格Sun认证Java程序员(SCJP)具备的能力
Java 2.1 java基本类型的转换和运算符
JAVA认证简介
sun认证java程序员须知Java日志框架
JAVA基础知识:form的提交方式
2015年计算机二级《VB》考试基础知识:Visual Basic的启动方法
计算机二级考试JAVA知识点:组件和容器
Java中4大基本加密算法
Java的算术运算符简介
java基础知识:强制类型转换
经典Java面试题之Java中Char类型的运算
JAVA简单选择排序算法及实现
java算法实现排列组合的方法介绍
JavaWeb基础教程之Java基础加强版参考
计算机基础知识 汉字录入教学设计