大师作文网英文翻译几个专业词汇：NP-hard problem - NP困难问题3/2
来源：学生作业帮 编辑：大师作文网作业帮 分类：数学作业 时间：2024/11/18 19:11:23
英文翻译
几个专业词汇：
NP-hard problem - NP困难问题
3/2 - ε factor algrithm - 3/2-ε近似算法
这段话是说明为啥装箱问题不存在近似率在3/2以下的近似算法,不求文笔只求看懂.或者能给我讲明白为啥不存在3/2以下的近似率也行……
证明：如果有这么一种运算法则(算法),那么演示如何解决这个NP难题：决定是否有办法将n个非负数a1,…,an分成两组,每组相加得出1/2Σi ai.显然,如果n个东西可以装入两个大小为1/2Σi ai的箱子（或垃圾桶）,那么这个问题的答案是“是”.如果答案为“是”,那么3/2-ε近似算法（因子算法）就必须给出一个最佳（最优）装法,并因而解决这个分组难题.