0

我找到了一个解决方案，请参阅下面的答案和/或Github Gist，它有更新的优化。

我有一系列信用卡费用和批次总额...有时金额的 SUM() = 批次金额，所以这很容易分组到批次，我们可以检查促成当天存款的交易支票账户。

有时，适当的总和是这些费用的一个子集，其中 1 个或多个在第二天分批。你能帮我以编程方式解决这个问题吗？这是为了我的 authorize.net 批量会计，这很糟糕，所以我正在为我的簿记员制作一个工具。

+------------+--------+
| transId    | amount |
+------------+--------+
| 2863996511 | 154.00 |
| 2863992361 | 762.20 |
| 2863898975 |  49.00 |
| 2863894564 |   5.44 |
| 2863879671 |  10.88 |
| 2863858891 | 209.00 |
| 2863856334 | 148.00 |
| 2863367273 | -25.01 |
+------------+--------+

当天的批次总额为 1302.63 美元。正如经常发生的那样，该批次中没有电荷，因此该批次是阵列中电荷总和的某个子集。在这种情况下，10.88 美元的费用在第二天的批次中。这段伪代码可以通过两个嵌套的 for 循环来捕获：

        for( $skipdx=0; $skipdx<$size; $skipdx++){
            $total=0;
            for( $idx=0; $idx<$size; $idx++){
                if($idx!=$skipdx){
                    $total+=$charges[$idx]['amount'];
                    $thisBatch[]=$charges[$idx]['transId'];
                }
                if( abs($total-$batch['total']) < .04 ) {
                    echo "sum of charges matches $date batch total: $$total  (line: ". __LINE__ .")\n";
                    $foundIt=TRUE;
                    break;
                }
            }
            if($foundIt==TRUE)
                break;
        }

如何动态选择搜索未添加两个的费用？然后三个？我可以看到，如果$skipdx省略了一项费用，那么跳过两项费用将添加一个skip2dx嵌套循环。如果仍未找到，skip3dx将是第 3 级嵌套。

在递归之前，我通常非常擅长算法，然后我变得愚蠢。

4

2 回答 2

0

它来找我了！递归的“当前层”这样做：

  1. 合计费用金额。
  2. 遍历费用数组，一次减去 1 个费用并针对目标批次数量进行测试。
  3. 如果金额在本次迭代中匹配，则取消设置此费用的 id 并返回结果数组。
  4. 如果未找到，则再次遍历电荷数组，这次移除当前电荷。以相同的目标数量再次调用该函数，并将新的缩短数组再次调用到相同的函数。

工作代码（Github 也有更新的优化）：

$charges=Array(
     '2863996511' => 154.00 ,'2863879671' => 10.88
    ,'2863992361' => 762.20 ,'2863858891' => 209.00
    ,'2863898975' => 49.00  ,'2863856334' => 148.00
    ,'2863894564' => 5.44   ,'2863367273' => -25.01
); print_r($charges);
$targets=Array(1302.63, 1327.64, 1322.20 );
foreach( $targets as $batch ) {
    printf( "We seek combination of transIds to = $%-7.2f\n", $batch);
    $answer=reco( $batch, $charges );
    if( is_array($answer) )
        echo eval( "return ".implode("+",$answer).";" )."\nWIN!\n";
    else
        echo "Bust!\n";
}   

function reco( $target, $arr ){
    if( count($arr) < 2 )
        return FALSE;
    $killid='';
    $sum = eval( "return ".implode("+",$arr).";" );
    foreach( $arr as $id=>$amt ){
        if( abs($sum-$target-$amt) < .01 ) {
            $killid=$id;
            break;
        }
    }
    if( strlen($killid) > 1 ) {
        echo ".  omit $killid : ".$arr[$killid]."\n";
        unset($arr[$killid]); 
        return $arr;
    }
    foreach( $arr as $id=>$amt ){
        $tmp=$arr;
        unset($tmp[$id]);
        $rtn = reco( $target, $tmp );
        if( is_array($rtn) ) {
            echo ".. omit $id : ".$arr[$id]."\n";
            return $rtn;
        }
    }
    return FALSE;
}

和输出：

We seek combination of transIds to = $1302.63
. omit 2863879671 : 10.88
1302.63
WIN!
We seek combination of transIds to = $1327.64
. omit 2863367273 : -25.01
.. omit 2863879671 : 10.88
1327.64
WIN!
We seek combination of transIds to = $1322.20
. omit 2863367273 : -25.01
.. omit 2863879671 : 10.88
.. omit 2863894564 : 5.44
1322.2
WIN!

性能不是一个大问题。在大约一秒钟内处理到第三级递归。

于 2013-02-06T09:18:29.717 回答
0

当您开始查看您的一组费用的所有可能子集时，您可能会注意到有时选择与您的批次总和匹配的第一个子集并不是一个好的会计解决方案。可能有几个可能的费用子集加起来就是您的批次总数。

你会选哪一个？

实际上，这会导致一个众所周知的问题，称为子集和问题 - 请参阅此处的 wiki 。

还有一个名为SumMatch的廉价 Excel 插件，它可以找到与给定总和匹配的所有数字组合。考虑是否值得您花时间编写正确的算法。

于 2013-05-21T07:10:15.620 回答