数学排列、阶乘、组合:

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

// 阶乘
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);
}