permutacje? kombinacje? php c++ excel - help needed .. Opcje

[pwsmile]

Witam i proszę o pomoc ..

nie mogę rozgryźć następującej sprawy..

mam dane :

- x liczb (np.5 liczb i np. takie : 1 2 3 4 5 , ale może być też: 1 3 3 5 5)

- sumę którą chcę otrzymać z dodania którychś (obojętnie ilu) z danych liczb (np. suma=11)

.. i potrzebuję program / skrypt / arkusz excel, który powie mi jak Abel krowie, które liczby ze zbioru muszą być dodane, żeby utworzyły sumę jaką chcę.

Dla zbioru: 1 2 3 4 5 i danej żądanej sumy 11 byłyby to następujące możliwości:

1_2_3___5 (suma: 11)
__2___4_5 (suma: 11)

Dla zbioru: 1 3 3 5 5 i danej żądanej sumy 11 są 3 możliwości:

__3_3_5__ (suma: 11)
__3_3___5 (suma: 11)
1_____5_5 (suma: 11)

Nie jest ważne ile z liczb podanych w zbiorze złoży się na podaną sumę, jednak każda kolejna z liczb w zbiorze powtarzać się może tylko 1 raz (np. pierwsza liczba w ostatnim przykładzie (1) może byż brana pod uwagę tylko raz, czyli rozwiązaniem nie może być

1_1_1_1_1_1_1_1_1_1_1 (bo liczba 1 w zbiorze wystepuje tylko raz)

ale

liczba 5 - też w drugim przykładzie - powtórzyć się może 2 razy, bo tyle razy wystepuje w zbiorze


Super optymalnie byłoby, gdyby programik w przypadku nie znalezienia pasujących składników dających szukaną sumę, podał najbliższą możliwą kombinację w górę i najbliższą możliwą w dół ..

.. np jezeli żądaną sumą byłaby liczba 2, to mając dany zbiór jak w przykładzie drugim: 1 3 3 5 5 program nie znajdzie wprawdzie odpowiednika, bo suma żadnych ze składników w tym zbiorze nie daje liczby 2, ale wypisze:

1________ (suma: 1, reszta 1)
__3______ (suma: 3, reszta -1)
____3____ (suma: 3, reszta -1)

podobnie dla szykanej sumy 12 i tego samego zbioru: 1 3 3 5 5 pasujący odpowiednik nie zostanie znaleziony, jednak najbliższymi dodatnimi i ujemnymi wartościami będą:

1_____5_5 (suma: 11, reszta 1)
1_3___5_5 (suma: 13, reszta -1)
1___3_5_5 (suma: 13, reszta -1)




Jeżeli ktoś ma jakiś pomysł, lub może już nad czymś takim myslał i ma gotowca, byłbym wdzięczny za udostępnienie.

Pozdrawiam
pwsmile

[jarrod]

[PHP] pobierz, plaintext 
<?php
function test($suma=null)
{
	if(!$suma) $suma = rand(0,45); // 45 ponieważ 9+9+9+9+9 = 45
	if($suma == 0) return 'Zbiór nie zawiera liczb ujemnych. Nie można wykonać działania.';
	elseif($suma == 1) return 'Suma == 1 zatem nie można wykonać działań.';
 
	$liczby[0] = rand(0,9);
	$liczby[1] = rand(0,9);
	$liczby[2] = rand(0,9);
	$liczby[3] = rand(0,9);
	$liczby[4] = rand(0,9);
	// posiadamy już pięć losowych liczb które mogą się powtarzać
 
	// dla porządku można je posortować
	sort($liczby);
 
 
	// sprawdzam czy suma wszystkich liczb jest większa od szukanej sumy
	// inaczej szykanie nie mam sensu
	if(array_sum($liczby) >= $suma) 
	{
		$breakAll = false; // kontrola wyników
		$nSuma = 0; // suma kontrolna
		$wynik = array(); // wynik działania funkcji
		$tmpKeys = array(); // tu przechowuję indexy liczb użytych w działaniu 
 
		// zaczynamy iterowanie po tablicy
		for($i=0; $i<5;$i++)
		{
 
			for($e=$i;$e<5;$e++)
			{
 
				$tmpKeys[] = $e;
				$nSuma += $liczby[$e];
 
				if($nSuma == $suma) // znaleziono pasujący wynik
				{
					$wyn = '';
					foreach($tmpKeys as $key)
					{
						$wyn .= $liczby[$key].'+';
					}
 
					$wyn = substr($wyn,0,strlen($wyn)-1);
					$wyn .= '='.$nSuma;
 
					$wynik['dokladnie'][] = $wyn;
 
					$nSuma = 0;
					$tmpKeys = array();
					break;
				}
				elseif($nSuma > $suma) // znaleziono pierwszy wyższy wynik
				{
					$wyn = '';
					foreach($tmpKeys as $key)
					{
						$wyn .= $liczby[$key].'+';
					}
					$wyn = substr($wyn,0,strlen($wyn)-1);
					$wyn .= '='.$nSuma;
					$resta = $suma-$nSuma;
 
					$wynik['wieksze'][] = array($wyn,$resta);
 
					$nSuma = 0;
					$tmpKeys = array();
					break;
				}
				elseif($e == 4) // ostatni element -> suma wszystkich pozostałych jest mniejsza od szukanej sumy
				{
					$breakAll = true;
 
					$wyn = '';
					foreach($tmpKeys as $key)
					{
						$wyn .= $liczby[$key].'+';
					}
					$wyn = substr($wyn,0,strlen($wyn)-1);
					$wyn .= '='.$nSuma;
					$resta = $suma-$nSuma;
 
					$wynik['mniejsze'][] = array($wyn,$resta);
 
					$nSuma = 0;
					$tmpKeys = array();
					break;
				}
			}
 
			if($breakAll) break;
 
		}
	}
	else
	{
		$wynik['max'] = array_sum($liczby);
	}
	$wynik['liczby'] = $liczby;
	$wynik['suma'] = $suma;
	return $wynik;
}
 
$wyniki = test();
 
$ret = 'Wynik działania programu:<br/>';
 
if(is_array($wyniki))
{
	$ret .= '<br/>Liczby w zbiorze: '.implode(',',$wyniki['liczby']);
	$ret .= '<br/>szukana suma: '.$wyniki['suma'].'<br/>';
 
	if(isset($wyniki['dokladnie']))
	{
		$ret .= '<br/>Dokładny wynik daje suma liczb:<br/>';
 
		foreach($wyniki['dokladnie'] as $wyn)
			$ret .= $wyn.'<br/>';
	}
	if(isset($wyniki['wieksze']))
	{
		$ret .= '<br/>Sumę minimalnie większą dają liczby:<br/>';
 
		foreach($wyniki['wieksze'] as $wyn)
			$ret .= $wyn[0].' reszty: '.$wyn[1].'<br/>';
	}
	if(isset($wyniki['mniejsze']))
	{
		$ret .= '<br/>Sumę minimalnie mniejszą dają liczby:<br/>';
 
		foreach($wyniki['mniejsze'] as $wyn)
			$ret .= $wyn[0].' pozostaje: '.$wyn[1].'<br/>';
	}
 
	if(isset($wyniki['max']))
	{
		$ret .= 'Suma wszyskich liczb zbioru ('.$wyniki['max'].') jest mniejsza od podanej sumy.';
	}
}
else
{
	$ret .= $wyniki;
}
echo $ret;
?>
[PHP] pobierz, plaintext 

uff (IMG:http://forum.php.pl/style_emoticons/default/aarambo.gif)