PHP中优化数字构成查找:最小余数与最优单类型组合算法

夏强大大_9740

夏强大大_9740

2025-10-29

916人浏览

原创

PHP中优化数字构成查找:最小余数与最优单类型组合算法

本文旨在解决如何从给定数字集合中,为目标数字寻找一个最优的单类型构成组合。针对传统贪婪算法在处理非精确整除时可能出现的局限性,我们提出一种改进方法。该方法通过独立计算每个可用构成数能提供的最大倍数及其剩余量,并对结果进行智能排序,以优先选择余数最小且使用次数合理的组合,从而实现更精准的数字分解近似。

在许多实际应用场景中,我们可能需要将一个目标数值分解为由一组预定义数值(构成数)的组合。例如,在库存管理或资金分配中,我们需要从一系列固定面额或尺寸的物品中,尽可能精确地凑出或接近一个目标总量。一个常见的挑战是,当目标数值无法被构成数精确整除时,如何找到一个“最接近”的组合,或者说,一个剩余量最小的组合。

传统贪婪算法的局限性

一种直观的解决方案是采用贪婪算法:总是优先使用当前能使用的最大构成数,并尽可能多地使用它,然后用剩余的量继续这个过程。让我们看一个PHP示例:

<?php $amount = 3000;
$sizes = array(1300, 1200, 1100, 1000, 950, 900, 800, 700); // 建议降序排列以符合贪婪策略

$result = array();
$remainingAmount = $amount; // 使用一个变量来跟踪剩余量

foreach ($sizes as $size) {
    if ($remainingAmount >= $size) {
        $times = floor($remainingAmount / $size);
        $result[$size] = $times;
        $remainingAmount -= $times * $size;
    } else {
        $result[$size] = 0;
    }
}

echo '<pre class="brush:php;toolbar:false;">'; print_r($result); echo '
'; ?>

对于 $amount = 3000,上述代码的输出将是:

Array
(
    [1300] => 2
    [1200] => 0
    [1100] => 0
    [1000] => 0
    [950] => 0
    [900] => 0
    [800] => 0
    [700] => 0
)

这里,1300 * 2 = 2600,剩余 400。虽然 1300 * 2 是一个有效的组合,但我们知道 1000 * 3 = 3000 是一个更好的选择,因为它没有剩余量。这表明简单的贪婪算法可能无法找到全局最优的近似解,尤其是在寻求最小余数时。其主要原因在于,贪婪算法一旦选择了一个构成数并减去了相应的量,就不会回头考虑其他可能更好的组合。

优化算法:基于最小余数和使用次数的排序

为了克服贪婪算法的局限性,我们可以采用一种不同的策略:不立即减少目标数值,而是针对每个可用的构成数,独立地计算它能提供的最大倍数以及此时产生的剩余量。然后,我们对这些计算结果进行排序,以找到最优的近似解。这里的“最优”定义为:首先余数最小,如果余数相同,则使用次数较少的方案(或根据具体需求选择使用次数较多的方案)。

btpanel phpsite 宝塔面板PHP网站
btpanel phpsite 宝塔面板PHP网站

宝塔面板 PHP 网站管理:站点创建、删除、启停、PHP 版本切换、域名管理、SSL证书管理、伪静态管理、数据库管理

下载

算法步骤

  1. 遍历所有构成数: 对于给定的目标数值 $amount 和构成数数组 $sizes 中的每一个 $size。
  2. 计算倍数和余数:
    • 计算当前 $size 能整除 $amount 的最大次数 ($times = floor($amount / $size))。
    • 计算此时的剩余量 ($remainder = $amount - $times * $size)。
  3. 存储结果: 将 $size、$times 和 $remainder 作为一个临时结果存储起来。
  4. 排序结果: 对所有临时结果进行排序。
    • 主要排序键: $remainder,按升序排列(最小余数优先)。
    • 次要排序键: $times,按升序或降序排列,具体取决于业务需求。例如,如果希望在余数相同的情况下优先选择使用次数较少的(更“紧凑”的)组合,则按升序排列。如果希望优先选择使用次数较多的(可能更“分散”的)组合,则按降序排列。在我们的示例中,我们选择升序。

PHP实现

<?php $amount = 3000;
// 构成数数组,顺序不影响最终结果,因为是独立计算
$sizes = [ 1300, 1200, 1100, 1000, 950, 900, 800, 700 ];

$results = []; // 注意:这里改名为 $results 以避免与 $result 混淆

foreach ($sizes as $size) {
  $times = (int)floor($amount / $size); // 计算当前构成数能使用的最大次数
  $remainder = $amount - $times * $size; // 计算此时的剩余量

  $results[] = [
      'size' => $size,
      'times' => $times,
      'remainder' => $remainder
  ];
}

// 使用 usort 进行自定义排序
usort($results, static function ($item1, $item2): int {
  // 首先按 'remainder' 升序排序
  $comparison = $item1['remainder']  $item2['remainder'];

  // 如果 'remainder' 相同,则按 'times' 升序排序
  // 这样在余数相同的情况下,会优先选择使用次数较少的方案
  return $comparison === 0 ? $item1['times']  $item2['times'] : $comparison;
});

echo '<pre class="brush:php;toolbar:false;">'; print_r($results); echo '
'; ?>

输出分析

运行上述代码,输出结果如下:

Array
(
    [0] => Array
        (
            [size] => 1000
            [times] => 3
            [remainder] => 0
        )

    [1] => Array
        (
            [size] => 950
            [times] => 3
            [remainder] => 150
        )

    [2] => Array
        (
            [size] => 700
            [times] => 4
            [remainder] => 200
        )

    [3] => Array
        (
            [size] => 900
            [times] => 3
            [remainder] => 300
        )

    [4] => Array
        (
            [size] => 1300
            [times] => 2
            [remainder] => 400
        )

    [5] => Array
        (
            [size] => 1200
            [times] => 2
            [remainder] => 600
        )

    [6] => Array
        (
            [size] => 800
            [times] => 3
            [remainder] => 600
        )

    [7] => Array
        (
            [size] => 1100
            [times] => 2
            [remainder] => 800
        )
)

从输出中可以看到,排序后的第一个元素 [0] 提供了最佳结果:size 为 1000,times 为 3,remainder 为 0。这正是我们期望的 1000 * 3 = 3000 的完美组合。

值得注意的是,在 remainder 均为 600 的情况下,[5] 元素 (1200 * 2) 比 [6] 元素 (800 * 3) 靠前,这是因为我们设置了次要排序键为 times 的升序,即在余数相同的情况下,优先选择使用次数更少的方案 (2

注意事项与扩展

  1. 问题定义: 本文提供的解决方案旨在找到一个单类型构成数(例如 X * N)来最佳近似目标数值。如果您的需求是寻找多种不同类型构成数的组合(例如 A * N1 + B * N2 + C * N3)来达到目标或最小余数,那么这属于更复杂的背包问题或找零问题范畴,通常需要动态规划或回溯算法来解决。本教程的方案不适用于这类多类型组合问题。
  2. 性能考量: 对于较小的构成数数组,这种遍历和排序的方法效率很高。如果构成数数组非常庞大,可能需要考虑更优化的数据结构或算法。
  3. 浮点数处理: 如果目标数值或构成数是浮点数,需要特别注意浮点数比较的精度问题,可能需要使用 bcmath 扩展进行精确计算,而不是直接使用 floor 和减法。
  4. 排序规则: 次要排序键(times)的选择应根据具体业务需求调整。例如,如果更倾向于使用尽可能多的构成数来分解,即使余数相同,可以将 times 设置为降序排序。
  5. 无解情况: 如果目标数值为负数或构成数数组为空,代码需要添加额外的逻辑进行处理,以避免错误或产生无意义的结果。

总结

通过对每个构成数独立进行计算,并结合多级排序策略,我们能够有效地找到给定目标数值的最佳单类型构成组合,尤其是在存在非精确整除情况时。这种方法比简单的贪婪算法更具鲁棒性,能够提供更符合“最小余数”或“最接近”原则的解决方案,为资源分配、库存优化等场景提供了实用的技术支持。

php免费学习视频:立即使用
踏上前端学习之旅,开启通往精通之路!从前端基础到项目实战,循序渐进,一步一个脚印,迈向巅峰!

相关文章

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

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

下载

相关标签:

php 库存管理 排列

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

相关专题

更多
treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.12.01

2941

7

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

2025.12.22

416

20

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

2026.01.06

437

22

C++ 数据结构与算法实现教程合集
C++ 数据结构与算法实现教程合集

以 C++ 为实现语言,系统讲解核心数据结构与算法,涵盖链表(单链表/双链表/环检测)、栈与队列(单调栈/优先队列)、二叉树(遍历/BST/AVL/红黑树)、哈希表(开地址法/链地址法)、图(邻接表/BFS/DFS/Dijkstra/拓扑排序)、常见排序算法(快排/归并/堆排/计数排序)的实现与复杂度分析,同时分享 LeetCode 刷题技巧、竞赛编程常用模板(二分/前缀和/滑动窗口/动态规划),帮助开发者夯实算法基础。

2026.05.09

512

25

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7216

4

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

140

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

60

15

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

2026.11.06

160

12

热门下载

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

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
墨刀帮助中心
墨刀帮助中心

共0课时 | 0人学习

MyEclipse学习中心
MyEclipse学习中心

共0课时 | 0人学习

Apache Subversion 官方手册
Apache Subversion 官方手册

共0课时 | 0人学习