PHP实现-数学排列、阶乘、组合、背包算法

数学排列、阶乘、组合:

数学里面的算法在编程中是处处可用,而且是可以提高效率的,甚至是只有使用这些算法才能实现的应用,将算法代码化需要思维转换,以下是算法的实现:

// 阶乘
function factorial($n) {
    return array_product(range(1, $n));
}
 
// 排列数
function A($n, $m) {
    return factorial($n)/factorial($n-$m);
}
 
// 组合数
function C($n, $m) {
    return A($n, $m)/factorial($m);
}
 
// 排列
function arrangement($a, $m) {
    $r = array();
 
    $n = count($a);
    if ($m <= 0 || $m > $n) {
        return $r;
    }
 
    for ($i=0; $i<$n; $i++) {
        $b = $a;
        $t = array_splice($b, $i, 1);
        if ($m == 1) {
            $r[] = $t;
        } else {
            $c = arrangement($b, $m-1);
            foreach ($c as $v) {
                $r[] = array_merge($t, $v);
            }
        }
    }
 
    return $r;
}
 
// 组合
function combination($a, $m) {
    $r = array();
 
    $n = count($a);
    if ($m <= 0 || $m > $n) {
        return $r;
    }
 
    for ($i=0; $i<$n; $i++) {
        $t = array($a[$i]);
        if ($m == 1) {
            $r[] = $t;
        } else {
            $b = array_slice($a, $i+1);
            $c = combination($b, $m-1);
            foreach ($c as $v) {
                $r[] = array_merge($t, $v);
            }
        }
    }
 
    return $r;
}
 
 
// ====== 测试 ======
$a = array("A", "B", "C", "D");
// 排列
$r = arrangement($a, 2);
var_dump($r);
echo '========================================'."\n";

// 排列数
$r = A(4, 2);
echo $r."\n";
echo '========================================'."\n";

// 组合
$r = combination($a, 2);
var_dump($r);
echo '========================================'."\n";

// 组合数
$r = C(4, 2);
echo $r."\n";

来自: https://zhidao.baidu.com/question/396366323226834965.html

背包算法1:

//取得背包算法最优结果
function KnapSack($capacity, $weight, $value, $itemsCount)
{
	$K = array();

	for ($i = 0; $i <= $itemsCount; ++$i)
	{
		for ($w = 0; $w <= $capacity; ++$w)
		{
			if ($i == 0 || $w == 0)
				$K[$i][$w] = 0;
			else if ($weight[$i - 1] <= $w)
				$K[$i][$w] = max($value[$i - 1] + $K[$i - 1][$w - $weight[$i - 1]], $K[$i - 1][$w]);
			else
				$K[$i][$w] = $K[$i - 1][$w];
		}
	}

	return $K[$itemsCount][$capacity];
}

//Example
$value = array(60, 100, 120);
$weight = array(10, 20, 30);
$capacity = 50;
$itemsCount = 3;

$result = KnapSack($capacity, $weight, $value, $itemsCount);

//Output
220

背包算法,算出最优的数字:https://www.programmingalgorithms.com/algorithm/knapsack-problem?lang=PHP

背包算法2:

选择最优叠加组合方式:
define('CAPACITY', 26);
define('GOODSNUM', 6);

main();

function main()
{
	$nVolume = array(3, 5, 1, 9, 3, 7);// N件物品的容量
	$nValue = array(10, 12, 40, 40, 40, 15);// N件物品的价值
	$selectTable = array();
	$nKnapsack = array();
	$itemIndex = $capIndex = $tmpIndex = $tmpValue = 0;
	for ($itemIndex = 0; $itemIndex < GOODSNUM; $itemIndex ++)
	{
		for ($capIndex = CAPACITY; $capIndex >= $nVolume[$itemIndex]; $capIndex --)
		{
			$tmpIndex = $capIndex - $nVolume[$itemIndex];
			if(! isset($nKnapsack[$capIndex])) $nKnapsack[$capIndex] = 0;
			if(! isset($nKnapsack[$tmpIndex])) $nKnapsack[$tmpIndex] = 0;
			$tmpValue = $nKnapsack[$tmpIndex] + $nValue[$itemIndex];
			if ($nKnapsack[$capIndex] <= $tmpValue)
			{
				$nKnapsack[$capIndex] = $tmpValue;
				$selectTable[$itemIndex][$capIndex] = 1;
			}
			else
				$nKnapsack[$capIndex] = $nKnapsack[$capIndex];
		}
	}
	echo "The max value is: ", $nKnapsack[CAPACITY], "<br>\n";
	echo "The selected items are: <br>\n";
	for ($itemIndex = GOODSNUM - 1, $capIndex = CAPACITY; $itemIndex >= 0; $itemIndex --)
	{
		$ok = isset($selectTable[$itemIndex][$capIndex]) ? $selectTable[$itemIndex][$capIndex] : 0;
		if ($ok)
		{
			echo $itemIndex + 1, ': Volume[', $nVolume[$itemIndex], '], Value[', $nValue[$itemIndex], ']', "<br>\n";
			$capIndex = $capIndex - $nVolume[$itemIndex];
		}
	}
	echo '<pre>';
	var_dump($nKnapsack, $selectTable);
}