PHP 获取给定值的最优组合
方法 - （蓝洛提供，博客地址： www.zhaorui.info）
<?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);
方法二：
<?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;
}
?>