热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

算法问题:从数据集中按规则取指定数量的数据集合

遇到一个算法问题,一直不得求解,恳请大神指点!现有数据:{代码...}其中$data包含100组数据,每组数据由字母组成,数量和内容都是随机的。其中$times是每个字母出现的次数。现在需要从$data中取20组数据,使...
遇到一个算法问题,一直不得求解,恳请大神指点!
现有数据:

 29,
    'b' => 11,
    'c' => 33,
    'd' => 84,
    'e' => 46,
    'f' => 67,
    'g' => 19,
    'h' => 18,
    'i' => 88,
    'j' => 8,
    'k' => 54,
    'l' => 86,
    'm' => 88,
    'n' => 29,
    'o' => 96,
    'p' => 1,
    'q' => 4,
    'r' => 100,
    's' => 89,
    't' => 44,
    'u' => 53,
    'v' => 68,
    'w' => 12,
    'x' => 54,
    'y' => 23,
    'z' => 78,
);
?>

其中$data包含100组数据,每组数据由字母组成,数量和内容都是随机的。
其中$times是每个字母出现的次数。
现在需要从$data中取20组数据,使这20组数据排重过滤后组成的新数据中,所有字母出现次数总和最小(相比于其他的可能的组合)。
穷举法比较的路子走不通,因为从100组数据中取所有20组数据可能的组合,这个数据量太大。
请问,应该如何获取?

回复内容:

遇到一个算法问题,一直不得求解,恳请大神指点!
现有数据:

 29,
    'b' => 11,
    'c' => 33,
    'd' => 84,
    'e' => 46,
    'f' => 67,
    'g' => 19,
    'h' => 18,
    'i' => 88,
    'j' => 8,
    'k' => 54,
    'l' => 86,
    'm' => 88,
    'n' => 29,
    'o' => 96,
    'p' => 1,
    'q' => 4,
    'r' => 100,
    's' => 89,
    't' => 44,
    'u' => 53,
    'v' => 68,
    'w' => 12,
    'x' => 54,
    'y' => 23,
    'z' => 78,
);
?>

其中$data包含100组数据,每组数据由字母组成,数量和内容都是随机的。
其中$times是每个字母出现的次数。
现在需要从$data中取20组数据,使这20组数据排重过滤后组成的新数据中,所有字母出现次数总和最小(相比于其他的可能的组合)。
穷举法比较的路子走不通,因为从100组数据中取所有20组数据可能的组合,这个数据量太大。
请问,应该如何获取?

 29,
    'b' => 11,
    'c' => 33,
    'd' => 84,
    'e' => 46,
    'f' => 67,
    'g' => 19,
    'h' => 18,
    'i' => 88,
    'j' => 8,
    'k' => 54,
    'l' => 86,
    'm' => 88,
    'n' => 29,
    'o' => 96,
    'p' => 1,
    'q' => 4,
    'r' => 100,
    's' => 89,
    't' => 44,
    'u' => 53,
    'v' => 68,
    'w' => 12,
    'x' => 54,
    'y' => 23,
    'z' => 78,
);
/**
 * 算法思路:
 * 1.先排重
 * 2.排重之后的操作见注释
 */


$newData = array();
foreach ($data as $oldKey => $item){
    //去重后
    $removeDuplicatedItem = array_unique($item,SORT_NATURAL);
    $newData[$oldKey] = $removeDuplicatedItem;
}

uasort($newData,function($a,$b){
    $countForA = count($a);
    $countForB = count($b);
    if ($countForA == $countForB){
        return 0;
    }
    
    return ($countForA > $countForB ? 1 : -1);
});

$counter = 0;

$targetData = array();
foreach ($newData as $targetKey =>$newItem){

    $targetData[$targetKey] = $newItem;
    $counter++;
    if($counter == 20){
        break;
    }
}
$endMemoryUsage = memory_get_usage();
$endTimeStamp = microtime(true);
$totalMemoryUsage = $endMemoryUsage - $startMemoryUsage;
$totalTimeStamp = $endTimeStamp - $startTimeStamp;

print_r($totalMemoryUsage);
echo "\n";
print_r($totalTimeStamp);
echo "\n";
print_r($targetData);

推荐阅读
  • 如何实现织梦DedeCms全站伪静态
    本文介绍了如何通过修改织梦DedeCms源代码来实现全站伪静态,以提高管理和SEO效果。全站伪静态可以避免重复URL的问题,同时通过使用mod_rewrite伪静态模块和.htaccess正则表达式,可以更好地适应搜索引擎的需求。文章还提到了一些相关的技术和工具,如Ubuntu、qt编程、tomcat端口、爬虫、php request根目录等。 ... [详细]
  • 阿里Treebased Deep Match(TDM) 学习笔记及技术发展回顾
    本文介绍了阿里Treebased Deep Match(TDM)的学习笔记,同时回顾了工业界技术发展的几代演进。从基于统计的启发式规则方法到基于内积模型的向量检索方法,再到引入复杂深度学习模型的下一代匹配技术。文章详细解释了基于统计的启发式规则方法和基于内积模型的向量检索方法的原理和应用,并介绍了TDM的背景和优势。最后,文章提到了向量距离和基于向量聚类的索引结构对于加速匹配效率的作用。本文对于理解TDM的学习过程和了解匹配技术的发展具有重要意义。 ... [详细]
  • Monkey《大话移动——Android与iOS应用测试指南》的预购信息发布啦!
    Monkey《大话移动——Android与iOS应用测试指南》的预购信息已经发布,可以在京东和当当网进行预购。感谢几位大牛给出的书评,并呼吁大家的支持。明天京东的链接也将发布。 ... [详细]
  • 本文介绍了《中秋夜作》的翻译及原文赏析,以及诗人当代钱钟书的背景和特点。通过对诗歌的解读,揭示了其中蕴含的情感和意境。 ... [详细]
  • 本文详细介绍了SQL日志收缩的方法,包括截断日志和删除不需要的旧日志记录。通过备份日志和使用DBCC SHRINKFILE命令可以实现日志的收缩。同时,还介绍了截断日志的原理和注意事项,包括不能截断事务日志的活动部分和MinLSN的确定方法。通过本文的方法,可以有效减小逻辑日志的大小,提高数据库的性能。 ... [详细]
  • 本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值,函数可以作为变量自由传递,也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性,为程序开发带来了便利。 ... [详细]
  • 本文介绍了Python高级网络编程及TCP/IP协议簇的OSI七层模型。首先简单介绍了七层模型的各层及其封装解封装过程。然后讨论了程序开发中涉及到的网络通信内容,主要包括TCP协议、UDP协议和IPV4协议。最后还介绍了socket编程、聊天socket实现、远程执行命令、上传文件、socketserver及其源码分析等相关内容。 ... [详细]
  • GetWindowLong函数
    今天在看一个代码里头写了GetWindowLong(hwnd,0),我当时就有点费解,靠,上网搜索函数原型说明,死活找不到第 ... [详细]
  • 本文介绍了在Python3中如何使用选择文件对话框的格式打开和保存图片的方法。通过使用tkinter库中的filedialog模块的asksaveasfilename和askopenfilename函数,可以方便地选择要打开或保存的图片文件,并进行相关操作。具体的代码示例和操作步骤也被提供。 ... [详细]
  • 本文描述了作者第一次参加比赛的经历和感受。作者是小学六年级时参加比赛的唯一选手,感到有些紧张。在比赛期间,作者与学长学姐一起用餐,在比赛题目中遇到了一些困难,但最终成功解决。作者还尝试了一款游戏,在回程的路上感到晕车。最终,作者以110分的成绩取得了省一会的资格,并坚定了继续学习的决心。 ... [详细]
  • 本文介绍了在开发Android新闻App时,搭建本地服务器的步骤。通过使用XAMPP软件,可以一键式搭建起开发环境,包括Apache、MySQL、PHP、PERL。在本地服务器上新建数据库和表,并设置相应的属性。最后,给出了创建new表的SQL语句。这个教程适合初学者参考。 ... [详细]
  • 基于layUI的图片上传前预览功能的2种实现方式
    本文介绍了基于layUI的图片上传前预览功能的两种实现方式:一种是使用blob+FileReader,另一种是使用layUI自带的参数。通过选择文件后点击文件名,在页面中间弹窗内预览图片。其中,layUI自带的参数实现了图片预览功能。该功能依赖于layUI的上传模块,并使用了blob和FileReader来读取本地文件并获取图像的base64编码。点击文件名时会执行See()函数。摘要长度为169字。 ... [详细]
  • 搭建Windows Server 2012 R2 IIS8.5+PHP(FastCGI)+MySQL环境的详细步骤
    本文详细介绍了搭建Windows Server 2012 R2 IIS8.5+PHP(FastCGI)+MySQL环境的步骤,包括环境说明、相关软件下载的地址以及所需的插件下载地址。 ... [详细]
  • PHP图片截取方法及应用实例
    本文介绍了使用PHP动态切割JPEG图片的方法,并提供了应用实例,包括截取视频图、提取文章内容中的图片地址、裁切图片等问题。详细介绍了相关的PHP函数和参数的使用,以及图片切割的具体步骤。同时,还提供了一些注意事项和优化建议。通过本文的学习,读者可以掌握PHP图片截取的技巧,实现自己的需求。 ... [详细]
  • 关羽败走麦城时路过马超封地 马超为何没有出手救人
    对当年关羽败走麦城,恰好路过马超的封地,为啥马超不救他?很感兴趣的小伙伴们,趣历史小编带来详细的文章供大家参考。说到英雄好汉,便要提到一本名著了,没错,那就是《三国演义》。书中虽 ... [详细]
author-avatar
甄Ven-Li
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有