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
)

)

// php 练习之装箱问题
// author: mx (http://my.oschina.net/meikaiyuan)
// 2013/5/30
// 问题：
// http://www.oschina.net/question/117304_112681
/*
题目：
以前问过类似问题，没有很好解答。所以想再问一次。
有大大小小的一堆石头要用船拉到河对岸
--石头有m块，每块的重量已知
--船每次只能装k块石头，并且装载重量不可以超过w
--想求出最少几趟能把全部石头运过河。
------------------------------------
例1
石头有9块，重量分别是1,2,3,4,5,6,7,8,9
k=3
w=15
那么结果是，最少3次就可以运完。
------------------------------------
例2
石头有9块，重量分别是1,1,1,5,6,6,7,9,9
k=3
w=15
那么结果是，最少 4 次才可以运完。
*/
//代码开始
//石头
global $rocks;
// 船每次最多装几块
global $k;
// 船最大载重量
global $w;
$k=3;
$rocks=array(1,2,3,4,5,6,7,8,9);
// $rocks=array(1,1,1,5,6,6,7,9,9); //换成这组数据试试结果？
$w=15;
// 当前运了几次
$count=0;
// 运输过程,二维数组，形如 1=>array(9,5,1)，表示第几次运了哪一些
$process=array();
// 求数组$rocks中一组合，使得最多$k个元素且这些元素的和尽可能大但小于等于指定值$w, 数组已经按从大到小排序过
function getMaxCombination( ) {
//石头
global $rocks;
// 船每次最多装几块
global $k;
// 船最大载重量
global $w;
// 保存各种$k下满足所有元素之和小于等于w且最大的集合
$k_w_result=array();
// 最大组合值
$max_sum=0;
// 哪项最大
$max_one=0;
for ($start=$k;$start>0;$start--){
// 找到由固定$start个元素组成的最大解
$start_w_arr = getMaxCombination2($start);
echo "寻找由 $start 个元素组成的最大解: \n";
print_r($start_w_arr);
echo "\n";
$sum=array_sum( $start_w_arr );
// 注意：因为是降序排列的，$k--, 越早找到的同sum的组合$k越大，也就是解越好，所以是小于不是小于等于
if($sum>$max_sum){
$max_sum=$sum;
$max_one=$k-$start;
}
$k_w_result[]= $start_w_arr ;
}
return $k_w_result[$max_one];
}
// 求数组$rocks中一由给定$start个元素构成的组合，这些元素的和尽可能大但小于等于指定值$w, 数组已经按从大到小排序过
function getMaxCombination2($start ) {
//石头们
global $rocks;
// 船每次最多装几块
global $k;
// 船最大载重量
global $w;
if(count($rocks) return array(0);
}
$c=count($rocks);
// 根据$start生成一函数，内含$start层for循环代码, 然后包含进来再调用此函数
if(!file_exists( "$start.php")){
$output_1="";
$output_2='$sum=';
$output_3='if($sum $output_4='';
for($i=0;$i $output_1.='for($p'.$i.'='.$i.';$p'.$i.' if($i>0){
$output_2.='+';
}
$output_2.='$rocks[$p'.$i.']';
$output_3.='$arr[]=$rocks[$p'.$i.'];';
$output_4.='}';
}
$output_2.=';';
$output_3.=' return $arr; }' ;
$output='';
file_put_contents("$start.php",$output);
include_once "$start.php";
}
else{
include_once "$start.php";
}
return call_user_func('myfor'.$start ,$rocks,$c,$w);
}
//开始计算
// 数组先从大到小排序, 此操作是后续算法省时省力的关键
rsort($rocks);
// 为了防止石头过大船过小造成下面算法死循环
foreach ($rocks as $v){
if($v>$w){
die("有石头不可能装船，换大船来再战！");
}
}
// 算法开始
while(!empty($rocks)){
// 开始装一船
$process[$count]=array();
// 装船
$process[$count]= getMaxCombination( ) ;
// 从石头中移除已经装船的
foreach($process[$count] as $v){
$key=array_search($v, $rocks);
unset( $rocks[$key]);
}
$rocks=array_values($rocks);
// 装船数+1
$count++;
}
// 输出结果
echo '最小次数:'.$count."\n";
echo '装船过程:';
print_r($process);
?>

复制代码

PHP移动端访问404怎么破_PHP移动端404适配法【指导】

Laravel控制器方法参数不匹配：修复storeDetail方法的参数错误

如何使用PHP表单一次性为多名学生批量录入考勤记录

如何高效检索指定客户名的印刷订单数据

PHP中访问空值数组偏移量的错误解决方案

PHP速学教程(入门到精通)

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

下载

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

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

热门AI工具

DeepSeek

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

AI大模型

开放平台

豆包大模型

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

AI大模型

通义千问

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

AI大模型

腾讯元宝

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

文档处理

Excel 表格

文心一言

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

AI大模型

中文写作

讯飞写作

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

中文写作

写作工具

即梦AI

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

图片拼接

图画生成

ChatGPT

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

AI大模型

中文写作

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

AI大模型

PDF 文档

相关专题

云朵浏览器入口合集

本专题整合了云朵浏览器入口合集，阅读专题下面的文章了解更多详细地址。

2026.01.20

Java JVM 原理与性能调优实战

本专题系统讲解 Java 虚拟机（JVM）的核心工作原理与性能调优方法，包括 JVM 内存结构、对象创建与回收流程、垃圾回收器（Serial、CMS、G1、ZGC）对比分析、常见内存泄漏与性能瓶颈排查，以及 JVM 参数调优与监控工具（jstat、jmap、jvisualvm）的实战使用。通过真实案例，帮助学习者掌握 Java 应用在生产环境中的性能分析与优化能力。

2026.01.20

PS使用蒙版相关教程

本专题整合了ps使用蒙版相关教程，阅读专题下面的文章了解更多详细内容。

149

2026.01.19

java用途介绍

本专题整合了java用途功能相关介绍，阅读专题下面的文章了解更多详细内容。

120

2026.01.19

java输出数组相关教程

本专题整合了java输出数组相关教程，阅读专题下面的文章了解更多详细内容。

2026.01.19

java接口相关教程

本专题整合了java接口相关内容，阅读专题下面的文章了解更多详细内容。

2026.01.19

xml格式相关教程

本专题整合了xml格式相关教程汇总，阅读专题下面的文章了解更多详细内容。

2026.01.19

PHP WebSocket 实时通信开发

本专题系统讲解 PHP 在实时通信与长连接场景中的应用实践，涵盖 WebSocket 协议原理、服务端连接管理、消息推送机制、心跳检测、断线重连以及与前端的实时交互实现。通过聊天系统、实时通知等案例，帮助开发者掌握使用 PHP 构建实时通信与推送服务的完整开发流程，适用于即时消息与高互动性应用场景。

2026.01.19