讲师中心 微信公众号
首页
文章
后端开发 web前端 数据库 开发工具 php框架 常见问题 人工智能 Java 系统教程 电脑教程 硬件教程 手机教程 软件教程 游戏教程 自媒体 新闻
专题
后端开发 web前端 数据库 开发工具 php框架 人工智能 Java 系统教程 电脑教程 硬件教程 手机教程 软件教程 游戏教程 新闻
AI工具
AI 聊天问答 Agent智能体 AI 文本写作 AI 绘画作图 AI 设计工具 AI 视频创作 AI 音频制作 AI 办公学习 AI 编程开发 Prompt指令
学习
大前端 后端开发 数据库 移动端 运维开发 计算机基础
编程手册
大前端 后端开发 数据库 移动端 运维开发 计算机基础
下载
js特效 网站源码 工具下载 类库下载 网站素材 学习资源 插件扩展 手机游戏
最近更新
当前位置：首页 > 后端开发 > php教程 >

正文

0

0

php解决装箱问题

php中文网

php中文网

发布时间：2016-07-25 08:51:00

|

1470人浏览过

|

来源于php中文网

原创

我对装箱问题，石头过河问题的解法
见http://www.oschina.net/question/117304_112681

实现思路主要为：
1. 大块石头必须优先装箱（早装和留到后面装都要装，先解决之）
2. 优先装重量接近w的
3. 同样重量优先装多块，如装9,6和装9,5,1比，则优先951装箱
4. 使用php的函数以简化代码，并使用根据k值生成函数的技巧
5. 此类问题由于本身性质，计算量较大，请酌情设置参数测试。

示例输出：（当rocks为1~9，w为15，k为3）
寻找由 3 个元素组成的最大解:
Array
(
[0] => 9
[1] => 5
[2] => 1
)

寻找由 2 个元素组成的最大解:
Array
(
[0] => 9
[1] => 6
)

寻找由 1 个元素组成的最大解:
Array
(
[0] => 9
)

寻找由 3 个元素组成的最大解:
Array
(
[0] => 8
[1] => 4
[2] => 3
)

寻找由 2 个元素组成的最大解:
Array
(
[0] => 8
[1] => 7
)

寻找由 1 个元素组成的最大解:
Array
(
[0] => 8
)

寻找由 3 个元素组成的最大解:
Array
(
[0] => 7
[1] => 6
[2] => 2
)

寻找由 2 个元素组成的最大解:
Array
(
[0] => 7
[1] => 6
)

寻找由 1 个元素组成的最大解:
Array
(
[0] => 7
)

最小次数:3
装船过程:Array
(
[0] => Array
(
[0] => 9
[1] => 5
[2] => 1
)

[1] => Array
(
[0] => 8
[1] => 4
[2] => 3
)

[2] => Array
(
[0] => 7
[1] => 6
[2] => 2
)

)
  1. // php 练习 之装箱问题
  2. // author: mx (http://my.oschina.net/meikaiyuan)
  3. // 2013/5/30
  5. // 问题：
  6. // http://www.oschina.net/question/117304_112681
  7. /*
  8. 题目：
  10. 以前问过类似问题，没有很好解答。所以想再问一次。
  12. 有大大小小的一堆石头要用船拉到河对岸
  13. --石头有m块，每块的重量已知
  14. --船每次只能装k块石头，并且装载重量不可以超过w
  15. --想求出最少几趟能把全部石头运过河。
  17. ------------------------------------
  18. 例1
  19. 石头有9块，重量分别是1,2,3,4,5,6,7,8,9
  20. k=3
  21. w=15
  22. 那么结果是，最少3次就可以运完。
  23. ------------------------------------
  24. 例2
  25. 石头有9块，重量分别是1,1,1,5,6,6,7,9,9
  26. k=3
  27. w=15
  28. 那么结果是，最少 4 次才可以运完。
  29. */
  31. //代码开始
  33. //石头
  34. global $rocks;
  35. // 船每次最多装几块
  36. global $k;
  37. // 船最大载重量
  38. global $w;
  40. $k=3;
  41. $rocks=array(1,2,3,4,5,6,7,8,9);
  42. // $rocks=array(1,1,1,5,6,6,7,9,9); //换成这组数据试试结果？
  43. $w=15;
  45. // 当前运了几次
  46. $count=0;
  47. // 运输过程,二维数组，形如 1=>array(9,5,1)，表示第几次运了哪一些
  48. $process=array();
  50. // 求数组$rocks中一组合，使得最多$k个元素且这些元素的和尽可能大但小于等于指定值$w, 数组已经按从大到小排序过
  51. function getMaxCombination( ) {
  52. //石头
  53. global $rocks;
  54. // 船每次最多装几块
  55. global $k;
  56. // 船最大载重量
  57. global $w;
  59. // 保存各种$k下满足所有元素之和小于等于w且最大的集合
  60. $k_w_result=array();
  61. // 最大组合值
  62. $max_sum=0;
  63. // 哪项最大
  64. $max_one=0;
  66. for ($start=$k;$start>0;$start--){
  67. // 找到由固定$start个元素组成的最大解
  68. $start_w_arr = getMaxCombination2($start);
  69. echo "寻找由 $start 个元素组成的最大解: \n";
  70. print_r($start_w_arr);
  71. echo "\n";
  72. $sum=array_sum( $start_w_arr );
  73. // 注意：因为是降序排列的，$k--, 越早找到的同sum的组合$k越大，也就是解越好，所以是小于不是小于等于
  74. if($sum>$max_sum){
  75. $max_sum=$sum;
  76. $max_one=$k-$start;
  77. }
  78. $k_w_result[]= $start_w_arr ;
  79. }
  80. return $k_w_result[$max_one];
  81. }
  83. // 求数组$rocks中一由给定$start个元素构成的组合，这些元素的和尽可能大但小于等于指定值$w, 数组已经按从大到小排序过
  84. function getMaxCombination2($start ) {
  85. //石头们
  86. global $rocks;
  87. // 船每次最多装几块
  88. global $k;
  89. // 船最大载重量
  90. global $w;
  92. if(count($rocks) return array(0);
  93. }
  94. $c=count($rocks);
  95. // 根据$start生成一函数，内含$start层for循环代码, 然后包含进来再调用此函数
  96. if(!file_exists( "$start.php")){
  97. $output_1="";
  98. $output_2='$sum=';
  99. $output_3='if($sum $output_4='';
  100. for($i=0;$i $output_1.='for($p'.$i.'='.$i.';$p'.$i.' if($i>0){
  101. $output_2.='+';
  102. }
  103. $output_2.='$rocks[$p'.$i.']';
  104. $output_3.='$arr[]=$rocks[$p'.$i.'];';
  105. $output_4.='}';
  106. }
  107. $output_2.=';';
  108. $output_3.=' return $arr; }' ;
  109. $output='';
  111. file_put_contents("$start.php",$output);
  112. include_once "$start.php";
  113. }
  114. else{
  115. include_once "$start.php";
  116. }
  117. return call_user_func('myfor'.$start ,$rocks,$c,$w);
  118. }
  120. //开始计算
  121. // 数组先从大到小排序, 此操作是后续算法省时省力的关键
  122. rsort($rocks);
  124. // 为了防止石头过大船过小造成下面算法死循环
  125. foreach ($rocks as $v){
  126. if($v>$w){
  127. die("有石头不可能装船，换大船来再战！");
  128. }
  129. }
  131. // 算法开始
  132. while(!empty($rocks)){
  133. // 开始装一船
  134. $process[$count]=array();
  136. // 装船
  137. $process[$count]= getMaxCombination( ) ;
  139. // 从石头中移除已经装船的
  140. foreach($process[$count] as $v){
  141. $key=array_search($v, $rocks);
  142. unset( $rocks[$key]);
  143. }
  144. $rocks=array_values($rocks);
  145. // 装船数+1
  146. $count++;
  147. }
  148. // 输出结果
  149. echo '最小次数:'.$count."\n";
  151. echo '装船过程:';
  152. print_r($process);
  154. ?>
复制代码


相关文章

如何让 Laravel 应用在 Docker 容器中将日志输出到 stdout

如何将 URL 查询字符串安全还原为 PHP 数组

php修改文件所有者与权限_php改属主和权限教程【技巧】

如何在抽象类中实现类型安全的 compareTo 方法

PHP 中双引号包含文件导致解析错误的根源与解决方案
PHP速学教程(入门到精通)
PHP速学教程(入门到精通)

PHP怎么学习？PHP怎么入门？PHP在哪学？PHP怎么学才快？不用担心，这里为大家提供了PHP速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：分享个php eval后门程序 下一篇：php python ftp操作类

热门AI工具

更多
DeepSeek
DeepSeek

幻方量化公司旗下的开源大模型平台

AI 编程开发AI 聊天问答
豆包大模型
豆包大模型

字节跳动自主研发的一系列大型语言模型

AI 编程开发AI大模型
通义千问
通义千问

阿里巴巴推出的全能AI助手

AI 编程开发Agent智能体
腾讯元宝
腾讯元宝

腾讯混元平台推出的AI助手

文档处理AI 聊天问答
文心一言
文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI 编程开发AI 文本写作
讯飞写作
讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

AI 文本写作中文写作
即梦AI
即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接
ChatGPT
ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI 编程开发AI 文本写作
智谱清言 - 免费全能的AI助手
智谱清言 - 免费全能的AI助手

智谱清言 - 免费全能的AI助手

AI 编程开发Agent智能体

相关专题

更多
C++ 设计模式与软件架构
C++ 设计模式与软件架构

本专题深入讲解 C++ 中的常见设计模式与架构优化，包括单例模式、工厂模式、观察者模式、策略模式、命令模式等，结合实际案例展示如何在 C++ 项目中应用这些模式提升代码可维护性与扩展性。通过案例分析，帮助开发者掌握 如何运用设计模式构建高质量的软件架构，提升系统的灵活性与可扩展性。

14

2026.01.30

c++ 字符串格式化
c++ 字符串格式化

本专题整合了c++字符串格式化用法、输出技巧、实践等等内容，阅读专题下面的文章了解更多详细内容。

9

2026.01.30

java 字符串格式化
java 字符串格式化

本专题整合了java如何进行字符串格式化相关教程、使用解析、方法详解等等内容。阅读专题下面的文章了解更多详细教程。

12

2026.01.30

python 字符串格式化
python 字符串格式化

本专题整合了python字符串格式化教程、实践、方法、进阶等等相关内容，阅读专题下面的文章了解更多详细操作。

4

2026.01.30

java入门学习合集
java入门学习合集

本专题整合了java入门学习指南、初学者项目实战、入门到精通等等内容，阅读专题下面的文章了解更多详细学习方法。

20

2026.01.29

java配置环境变量教程合集
java配置环境变量教程合集

本专题整合了java配置环境变量设置、步骤、安装jdk、避免冲突等等相关内容，阅读专题下面的文章了解更多详细操作。

18

2026.01.29

java成品学习网站推荐大全
java成品学习网站推荐大全

本专题整合了java成品网站、在线成品网站源码、源码入口等等相关内容，阅读专题下面的文章了解更多详细推荐内容。

19

2026.01.29

Java字符串处理使用教程合集
Java字符串处理使用教程合集

本专题整合了Java字符串截取、处理、使用、实战等等教程内容，阅读专题下面的文章了解详细操作教程。

3

2026.01.29

Java空对象相关教程合集
Java空对象相关教程合集

本专题整合了Java空对象相关教程，阅读专题下面的文章了解更多详细内容。

6

2026.01.29

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

相关下载

更多
hoverIntent延迟误操作插件
jQuery鼠标悬停查看大图功能

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
支付宝沙箱支付（个人也能用的支付）
支付宝沙箱支付（个人也能用的支付）

共12课时 | 0.6万人学习

Swoole5 Hyperf3 php8新版本协程框架讲说
Swoole5 Hyperf3 php8新版本协程框架讲说

共37课时 | 1.8万人学习

微信小程序开发之API篇
微信小程序开发之API篇

共15课时 | 1.2万人学习

最新文章

更多
php怎样判断变量为颜色值字符串_php颜色值串判断法【示例】
PHP 中如何正确验证 XML 解析后的整数输入
如何在 PHP for 循环中正确累加变量值
如何在 macOS M1 上为 Apache 正确启用 PHP 模块
如何在 PHP for 循环中正确累加变量值（如 $prog_total）
如何在 WooCommerce 中准确获取保存后的商品类型
如何在 PHP 中正确判断多个输入字段是否为空并据此生成数据库插入值
Laravel 路由 404 错误排查与修复指南
如何在 Timber 中通过 ACF 字段动态构建 WordPress 查询
PHP 中正确验证 XML 输入为整数的完整指南
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网：公益在线php培训，帮助PHP学习者快速成长！
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号

  • PHP学习

  • 技术支持

  • 返回顶部