[算法]在已知数字中找到N个满足条件的组合

已知有N个数字，找到能够满足条件的N个组合。
已知数字如图：

现在需要找到任意几个数字相加等于 50 的所有的组合。
写了一个程序，但是一直跑不出来结果（可能是数据量太大了），有没有大佬有更好的方法。

<?php
function printAllSubsetsRec($arr, $n, $v, $sum)
{
    if ($sum == 0) {
        for ($i = 0; $i < count($v); $i++)
            echo $v[$i] . " ";
        echo "\n";
        return;
    }

    if ($n == 0)
        return;

    printAllSubsetsRec($arr, $n - 1, $v, $sum);
    array_push($v, $arr[$n - 1]);
    printAllSubsetsRec($arr, $n - 1, $v,
        $sum - $arr[$n - 1]);
}

function printAllSubsets($arr, $n, $sum)
{
    $v = array();
    printAllSubsetsRec($arr, $n, $v, $sum);
}


$data_list = [
    ['number' => 6, 'total' => 41],
    ['number' => 7.1, 'total' => 168],
    ['number' => 8.2, 'total' => 22],
    ['number' => 6.9, 'total' => 171],
    ['number' => 6.5, 'total' => 310],
    ['number' => 7.2, 'total' => 238],
    ['number' => 7, 'total' => 189],
    ['number' => 6.8, 'total' => 287],
    ['number' => 7.6, 'total' => 58],
    ['number' => 8, 'total' => 44],
    ['number' => 7.5, 'total' => 90],
    ['number' => 7.7, 'total' => 50],
    ['number' => 7.4, 'total' => 119],
];

$arr = [];
foreach ($data_list as $item) {
    for ($i = 0; $i < $item['total']; $i++) {
        $arr[] = $item['number'];
    }
}
$sum = 50;
$n = count($arr);
printAllSubsets($arr, $n, $sum);

算法

MIYA28118

课程读者 37 声望

暂无个人描述~

0 人点赞

你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程，JWT 概念及使用和 API 开发相关的进阶知识。

从零开始带你一步步开发一个 Go 博客项目，让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。

推荐文章：

更多推荐...

博客

PHP面试高薪宝典系列: 常见基础算法（附完整代码） 23 / 3 |

博客

PHP实现汉诺塔算法 21 / 9 |

博客

PHP使用动态规划实现最优红包组合 33 / 5 |

博客

PHP拆红包算法 12 / 8 |

博客

我的 LeetCode 15 / 5 |

博客

PHP 实现 HTTP 表单请求服务器 45 / 7 |

讨论数量: 3

Siam

98 声望

你写的程序是来搞笑的吗...没看出和你题目有啥关系。。这个算法挺难，建议你有偿找人写吧

3年前评论

MIYA28118 （楼主）

其实并不难。已经解决了，优化了一下算法，每次找到组合就把栈内有组合的数字 pop 出去，这样就不会占用过多内存了。

Siam （作者）

@Stone007 这段代码算不上算法...N*N的复杂度了，你可以试着使用array_column把number、total字段提成一维数组，算出number字段的一维数组的和为50的组合为二维数组，把number和total数组合并，一个作为key一个作为value，循环之前的二维数组用里面对应的value去组合数组内减去对应的数量

Siam （作者）

@Stone007 本来这个回答是敲了一大堆代码的，想想删了，上述是昨天的想法，你可以参考参考

Siam （作者）

@Stone007 如果你计算和为50用你原来的办法，只是优化了你原来代码中把数量也遍历出来的弊端，但是这个难点是在于在已定的数字查找不定数量和值为50的组合，我是感觉有更优解，应该是可以写一个算法实现这个需求，所以我昨天说挺难的。

slpi1

78 声望

按照已知的条件，可能不止一个解，是不是还有什么隐含条件。

3年前评论

slpi1

78 声望

提供一个解法，过程分为两步：

找出所有和为50的不重复组合结果
按不同的逻辑对结果进行组合，验证数据余量

<?php

namespace App\Console\Commands;

use Illuminate\Console\Command;

class Test extends Command
{

    protected $signature = 'test';

    protected $description = 'Command description';

    protected $count    = 50;
    protected $dataList = [
        ['number' => 6, 'total' => 41],
        ['number' => 7.1, 'total' => 168],
        ['number' => 8.2, 'total' => 22],
        ['number' => 6.9, 'total' => 171],
        ['number' => 6.5, 'total' => 310],
        ['number' => 7.2, 'total' => 238],
        ['number' => 7, 'total' => 189],
        ['number' => 6.8, 'total' => 287],
        ['number' => 7.6, 'total' => 58],
        ['number' => 8, 'total' => 44],
        ['number' => 7.5, 'total' => 90],
        ['number' => 7.7, 'total' => 50],
        ['number' => 7.4, 'total' => 119],
    ];

    protected $items = [];

    protected $result = [];

    public function handle()
    {
        // 1. 计算所有和为50的不重复的情况 => $this->items
        $nums = collect($this->dataList)->pluck('number')->toArray();
        $this->sumDetail($nums, $this->count);

        // dd($this->items); 1014
        $this->items = array_keys($this->items);

        // 2. 穷举尽可能不重复的情况
        // 这里如果对 $this->items 进行一次洗牌，就可能会产生一个不同的结果 
        // shuffle($this->items);
        foreach ($this->items as $item) {
            if ($this->enough($item)) {
                $this->result[] = $item;
            }
        }
       // 即便这里循环完毕后，剩余数据可能依然充足，可以执行下一轮循环

        dd($this->result);
    }

    public function sumDetail($nums, $count, $stack = [])
    {
        if ($count <= 0) {
            return;
        }

        if (in_array($count, $nums)) {
            $stack[] = $count;

            // 去重
            sort($stack);
            $str = implode(':', $stack);
            if (!isset($this->items[$str])) {
                $this->items[$str] = 1;
            }
        }

        foreach ($nums as $num) {
            $newStack   = $stack;
            $newStack[] = $num;

            $this->sumDetail($nums, $count - $num, $newStack);
        }
    }

    protected function enough($str)
    {
        $list = explode(':', $str);
        foreach ($list as $num) {
            foreach ($this->dataList as &$item) {
                if ($item['number'] == $num) {
                    if ($item['total'] > 0) {
                        $item['total']--;
                    } else {
                        return false;
                    }

                }
            }
        }
        return true;
    }
}

3年前评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

[算法]在已知数字中找到N个满足条件的组合

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

[算法]在已知数字中找到N个满足条件的组合

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录