PHP算法: 获取“给定值”的最优组合 代码

PHP 获取给定值的最优组合代码实现有两种方法:

 

方法一:

<?php
 ini_set('error_reporting','E_ALL^E_NOTICE');
 $arr2 = array(
    0 => array(
        'id'=>'1',
        'cur' => '15',
        'cash' => '2'
    ),
    1 => array(
        'id'=>'2',
        'cur' => '20',
        'cash' => '2'
    ),
    2 => array(
        'id'=> '3',
        'cur' => '10',
        'cash' => '2'
    ),
    3 => array(
        'id'=> '4',
        'cur' => '6.2',
        'cash' => '10'
    ),
 );
 $arr = array_column($arr2,'cur');
 //循环取出,转化成整数类型
 foreach($arr as &$v){
     $v = intval($v);
 }
 print_r($arr);
 unset($v);
$maxSize = floor(23.6);//此处填写要的值
//$arr = array(15, 20, 10, 6,30,5,1,13,17,9);
$result = array();
$answers = array();
$currSize = floor(23.6);//此处也填写要的值
$len = count($arr);
for ($i = 0; $i < $len; $i++) {
    $result[] = array();
    for ($j = 0; $j <= $maxSize; $j++) {
        $result[$i][$j] = 0;
    }
}
//var_dump($result);die;
for ($i = 0; $i <= $maxSize; $i++) {
    for ($j = 0; $j < $len; $j++) {
        if ($arr[$j] > $i) {
            if ($j === 0) $result[$j][$i] = 0;
            else $result[$j][$i] = $result[$j - 1][$i];
        } else {
            if ($j === 0) $result[$j][$i] = $arr[$j];
            else $result[$j][$i] = max($result[$j - 1][$i], $result[$j - 1][$i - $arr[$j]] + $arr[$j]);
        }
    }
}
// 找出答案
for ($i = $len - 1; $i >= 0 && $currSize !== 0; $i--) {
    if ($result[$i][$currSize] - $result[$i - 1][$currSize - $arr[$i]] === $arr[$i]) {
        $answers[] = $arr[$i];
        $currSize -= $arr[$i];
    }

}
print_r($answers);

$arr3 = array();
foreach($arr2 as $k=>$v){
    if(in_array(intval($v['cur']),$answers)){
        $arr3[$k]=$v;
    }
}

print_r($arr3);

结果如下:

Array ( [0] => 15 [1] => 20 [2] => 10 [3] => 6 )Array ( [0] => 6 [1] => 15 )Array ( [0] => Array ( [id] => 1 [cur] => 15 [cash] => 2 ) [3] => Array ( [id] => 4 [cur] => 6.2 [cash] => 10 ) )

 

方法二:

<?php

    $result_flb = array(
        array('id'=>'1','currency' => '15','cash' => '2',),
        array('id'=>'2','currency' => '20','cash' => '2'),
        array('id'=> '3','currency' => '10','cash' => '2'),
        array('id'=> '4','currency' => '6','cash' => '10'),
     );

     $arr = array_column($result_flb,'currency');
     //循环取出,转化成floor类型
     foreach($arr as &$v){
         $v = floor($v);
     }
     unset($v);
     
    $max = 23;   //想要的值
    $re = digui($arr);

    foreach ($re as $key => $value) {
        if ($key <= $max) {
            isset($result) || $result = [$key, $value];
            if ($key > $result[0]) {
                $result = [$key, $value];
            }
        }
    }
    isset($result) || $result = [0, []]; 
    print_r($result); //打印答案

function digui($arr, $re = []) {
    if (count($arr) == 0) {
        return [];
    }
    if (count($arr) == 1) {
        $re[$arr[0]] = [$arr[0]];
    }
    if (count($arr) >= 2) {
        $x = array_shift($arr);
        $re[$x] = [$x];
        for ($b = 0; $b < count($arr); $b++) {
            $result = $x + $arr[$b];
            $re[$result] = [$x, $arr[$b]];
        }
        $re = digui($arr, $re);
        foreach ($re as $k => $v) {
            if (!in_array($arr[0], $v)) {
                array_unshift($v, $arr[0]);
                $re[$arr[0] + $k] = $v;
            }
        }
    }
    return $re;
}



?>

结果如下:

Array ( [0] => 21 [1] => Array ( [0] => 6 [1] => 15 ) )

 

PHP 获取“给定值”算法

    A+
发布日期:2017年12月15日  所属分类:PHP算法
最后修改时间:2017-12-15 17:23
评分: (当前没有评级)
PHP运行环境 Wamp Lamp Lnmp 安装、配置、搭建服务
PHP运行环境 Wamp Lamp Lnmp 安装、配置、搭建服务
  • ¥ 9.9元
  • 市场价:49.9元
SEO顾问服务 中小型网站 单站/最低99.9元 全方位优化
SEO顾问服务 中小型网站 单站/最低99.9元 全方位优化
  • ¥ 99.9元
  • 市场价:5000元
wordpress站群服务 泛解析二级域名站群 二级目录站群
wordpress站群服务 泛解析二级域名站群 二级目录站群
  • ¥ 1999.9元
  • 市场价:4800元
花牛苹果 甘肃天水 李宏恩家自种 1斤 包邮
花牛苹果 甘肃天水 李宏恩家自种 1斤 包邮
  • ¥ 6.8元
  • 市场价:8.8元

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: