/*
A:80 B:158 C:464 D:608 E:1326 F:5164 G:2724 H:1452
分别有以上8个产品 冒号后面是价格要求 用户输入一个 价格比如 1166 然后程序要算出 可能有的集中产品 价格总和为1166 的排列组合
例如：1166 = 80 + 158 + 464 +464 排列为 A B C(2) [如果有多种可能也要列举出来有可能2个A 2个B 1个C类似这种]*/
#include <stdio.h>
int main()
{
/*
const int A = 80;
const int B = 158;
const int C = 464;
const int D = 608;
const int E = 1326;
const int F = 5164;
const int G = 2724;
const int H = 1452;
*/
FILE *fp;
const int a[8] ={80,158,464,608,1326,
5164,2724,1452};
int i, res, sum, index[8];
printf("输入总和:");
scanf("%d",&sum);
/*
说明：穷举法求解，当输入的数字不是很大时(<10000)，结果很快出来，
当输入的数字较大时(>20000)，方法就不行了，原因是8层循环，假设每层循环
执行20次，则总共执行20^8次 bt -_-!
*/
fp = fopen("enum_all.txt","w+");
if(fp == NULL)
{
printf("Can not open the file!\n");
exit(1);
}
for(index[0]=0; index[0]<=sum / a[0]; index[0]++)
for(index[1]=0; index[1]<=sum / a[1]; index[1]++)
for(index[2]=0; index[2]<=sum / a[2]; index[2]++)
for(index[3]=0; index[3]<=sum / a[3]; index[3]++)
for(index[4]=0; index[4]<=sum / a[4]; index[4]++)
for(index[5]=0; index[5]<=sum / a[5]; index[5]++)
for(index[6]=0; index[6]<=sum / a[6]; index[6]++)
for(index[7]=0; index[7]<=sum / a[7]; index[7]++){
res = index[0]*a[0] + index[1]*a[1] + index[2]*a[2] + index[3]*a[3] +
index[4]*a[4] + index[5]*a[5] + index[6]*a[6] + index[7]*a[7] ;
if(sum == res){
printf("%d = %d*%d + %d*%d + %d*%d + %d*%d + %d*%d + %d*%d + %d*%d + %d*%d \n",
sum, index[0],a[0], index[1],a[1], index[2],a[2], index[3],a[3],
index[4],a[4], index[5],a[5], index[6],a[6], index[7],a[7]);
fprintf(fp,"%d = %d*%d + %d*%d + %d*%d + %d*%d + %d*%d + %d*%d + %d*%d + %d*%d \n",
sum, index[0],a[0], index[1],a[1], index[2],a[2], index[3],a[3],
index[4],a[4], index[5],a[5], index[6],a[6], index[7],a[7]);
}
}
}
分别有以上8个产品 冒号后面是价格 要求 用户输入一个 价格比如 1166 然后程序要算出 可能有的集中产品 价格总和为1166 的排列组合
例如：1166 = 80 + 158 + 464 +464 排列为 A B C(2) [如果有多种可能也要列举出来有可能2个A 2个B 1个C类似这种] 设总和为$total;1、获得所有小于总和的值。
赋值到array
array[i];
并获得maxi;2、任意三个值相加的和。
赋值到array1
array1[j][A,B,C]
获得maxj;3、任意两个值相加的和。
赋值到array2
array2[k][A,B]
获得maxk;
4、任意一个值×2，的和。
赋值到array3
array3[l][A]
获得maxl;5、
判断的条件：
条件一：
array1[j][A,B,C]==$total;//直接等于的情况。
条件二：
array3[l][A]+array2[k][A,B]==$total;//A*2+B+C类型的组合。
or
array3[l][B]+array2[k][A,C]==$total;
or
array3[l][C]+array2[k][B,C]==$total;
or条件三：
array3[l][A]+array3[l][B]+array[i][C]==$total;//A*2+B*2+C类型的组合。
or
array3[l][B]+array3[l][C]+array[i][A]==$total;
or
array3[l][C]+array3[l][A]+array[i][B]==$total;条件四：
array3[l][A]+array3[l][B]+array3[l][C]==$total;//A*2+B*2+C*2类型的组合。以上条件满足一个即可。
条件一实质。
array1[j]==$total;
条件二的实质是即任意一个数*2+任意两个值相加等于$total。
array3[l]+array2[k]==$total;
变形
array[i]*2+array2[k]==$total;
条件三的实质是任意两个数的和的两倍加上第三个数等于$total。
即
array2[k]*2+array[i]==$total;条件四的实质是任意三个数和的两倍等于$total;
即array1[j]*2=$total;到这里，发现值array3[l]存在的意义不大。所以编程的时候放弃即可。
<?php$total=1166;$array=array(80,158,464,608,1326,5164,2724,1452);
$maxi=count($array);for($i=0;$i<$maxi;$i++)
{
for ($j=$i+1;$j<$maxi;$j++)
{
for ($k=$j+1;$k<$maxi;$k++)
{
$array1[]=array(
"total"=>($array[$i]+$array[$j]+$array[$k]),
"A"=>$i,
"B"=>$j,
"C"=>$k,
);
}
}
}
$maxj=count($array1);
//print_r($array1);
for($i=0;$i<$maxi;$i++)
{
for ($j=$i+1;$j<$maxi;$j++)
{
$array2[]=array(
"total"=>($array[$i]+$array[$j]),
"A"=>$i,
"B"=>$j,
);
}
}
$maxk=count($array2);
//print_r($array2);//3个数的和等于$total时。
for($i=0;$i<$maxj;$i++)
{ if($array1[$i]['total']==$total)
{
echo "符合条件的数：<br>";
echo $array[$array1[$i]['A']]."<br>";
echo $array[$array1[$i]['B']]."<br>";
echo $array[$array1[$i]['C']]."<br>";
}
if($array1[$i['total']]*2==$total)
{
echo "符合条件的数：<br>";
echo $array[$array1[$i]['A']]."(2)<br>";
echo $array[$array1[$i]['B']]."(2)<br>";
echo $array[$array1[$i]['C']]."(2)<br>";
}
}//任意一个数*2+任意两个数的和 相加等于
for($i=0;$i<$maxk;$i++)
{
for ($j=0;$j<$maxi;$j++)
{
$Temp_A=(($array[$j]*2)+($array2[$i]['total']));
$Temp_B=($array[$j]+$array2[$i]['total']*2);
if( $Temp_A == $total )
{
echo "符合条件的数：<br>";
echo $array[$j]."(2)<br>";
echo $array[$array2[$i]['A']]."<br>";
echo $array[$array2[$i]['B']]."<br>";
}
//任意两个数的和的两倍加任意一个数。
if($Temp_B == $total )
{
echo "符合条件的数：<br>";
echo $array[$j]."<br>";
echo $array[$array2[$i]['A']]."(2)<br>";
echo $array[$array2[$i]['B']]."(2)<br>";
}
}
}
?>执行结果符合题目。至于其他可能的组合。自己组合点数字进去测试吧。效率嘛，还不错。花了3个小时哦。。555
这里面的*2就得改成*n了。
$Temp_A=(($array[$j]*2)+($array2[$i]['total']));
$Temp_B=($array[$j]+$array2[$i]['total']*2);
而且外面得再套个循环。从*n开始循环到*2
由于将采用组合算法,为避免过多的无效计算
将单个大于目标值的元素剔除
由于组合中同一元素不重复出现,因此要适量充填小数值元素
*/
foreach($data as $v) {
for($i=0; $i<floor($input/$v); $i++) {
$ar[] = $v;
}
}//逐次调用组合函数
for($i=1; $i<count($ar); $i++) {
foreach(combination($ar, $i) as $v) {
if(array_sum($v) == $input) print_r($v);
}
}//计算组合的函数
function combination($ar, $k, $m=0, $a=array()) {
static $ret = array();
if($m == 0) {
$m = count($ar);
$ret = array();
}
for($i=$m; $i>=$k; $i--) {
$a[$k-1] = $ar[$i-1];
if($k > 1) {
combination(&$ar, $k-1, $i-1, $a);
}else {
array_unshift ($ret, array_reverse($a));
}
}
return $ret;
}
应该确定最大的值对应的组合，即 5164 =Ax+bY+cz+....
依次
然后更加输入值，从最大的走起。
假设输入的total = 10000,
10000 = 0*80 + 4*158 + 10*464 + 3*608 + 0*1326 + 0*5164 + 0*2724 + 2*1452
这样的情况是不是遗漏了呀?
的确是这样。
这个，
不懂排列组合，所以...
$test=array('A'=>80,'B'=>158,'C'=>464,'D'=>608,'E'=>1326,'F'=>5164,'G'=>2724,'H'=>1452);
asort($test); $value=800;
$count=array();
$array=array();
foreach ($test as $list=>$lists)
{
$int=intval($value /$lists);
array_push($array,$list.'|'.$lists);
array_push($count,$int);
}
for($a=0;$a<$count[0]+1;$a++)
{
$dikv=$dit[1] * $a;$dik=$dit[0].'|'.$a.'.';
$dit=explode('|',$array[0]);
if($dit[1] * $a == $value) {echo $dit[0].'|'.$a.'.<br>';break;}
if($dit[1] * $a > $value) break;
else {$dikv=$dit[1] * $a;$dik=$dit[0].'|'.$a.'.';}
for ($b=0;$b<$count[1]+1;$b++)
{
$dit=explode('|',$array[1]);
$dikv +=$dit[1] * $b;$dik.=$dit[0].'|'.$b.'.';
if($dikv == $value) {echo $dik.'<br>';break;}
if($dikv > $value) break;
for ($c=0;$c<$count[2]+1;$c++)
{
$dit=explode('|',$array[1]);
$dikv +=$dit[1] * $c;$dik.=$dit[0].'|'.$c.'.';
if($dikv == $value) {echo $dik.'<br>';break;}
if($dikv > $value) break;
for ($d=0;$d<$count[3]+1;$d++)
{
$dit=explode('|',$array[1]);
$dikv +=$dit[1] * $d;$dik.=$dit[0].'|'.$d.'.';
if($dikv == $value) {echo $dik.'<br>';break;}
if($dikv > $value) break;
for ($e=0;$e<$count[4]+1;$e++)
{
$dit=explode('|',$array[1]);
$dikv +=$dit[1] * $e;$dik.=$dit[0].'|'.$e.'.';
if($dikv == $value) {echo $dik.'<br>';break;}
if($dikv > $value) break;
for ($f=0;$f<$count[5]+1;$f++)
{
$dit=explode('|',$array[1]);
$dikv +=$dit[1] * $f;$dik.=$dit[0].'|'.$f.'.';
if($dikv == $value) {echo $dik.'<br>';break;}
if($dikv > $value) break;
for ($g=0;$g<$count[6]+1;$g++)
{
$dit=explode('|',$array[1]);
$dikv +=$dit[1] * $g;$dik.=$dit[0].'|'.$g.'.';
if($dikv == $value) {echo $dik.'<br>';break;}
if($dikv > $value) break;
for ($h=0;$h<$count[7]+1;$h++)
{
$dit=explode('|',$array[1]);
$dikv +=$dit[1] * $h;$dik.=$dit[0].'|'.$h;
if($dikv == $value) {echo $dik.'<br>';break;}
if($dikv > $value) break;
$dik='';
}
}
}
}
}
}
}
}
?>