[PHP] Łączenie liczb Opcje

[slawo]

Witajcie, nie wiem jak zatytułować mój temat. Załóżmy, że mamy klocki z wartościami:

1 / 1,25 / 1,5 / 2 / 2,5 / 3 / 5 / 10 / 15 / 20

Chcę aby skrypt dobrał mi jak najmniejszą ilość klocków aby wyszła wpisana wartość.

Przykład: podaje wartość 18

Chciałbym aby skrypt dobrał: 15 + 3

Błędne: 3 + 5 + 10

Klocki nie mogą się powtarzać: 5 + 5 + 3

Proszę o jakieś wskazówki, nie wiem jak się z to zabrać

[kpt_lucek]

Tworzysz sobie wszystkie możliwe kombinacje liczb, które w efekcie utworzą sumę wymaganą przez Ciebie (bądź sumę która będzie jej najbliższa), do tego zliczasz ilość składników i zwracasz to, co wymagało ich najmniej

[trueblue]

A może tak:
redukujesz tablicę składników do tych mniejszych lub równych szukanej, sortujesz malejąco, dzielisz przez największą i sprawdzasz resztę, jeśli reszta jest większa od 0, to zapisujesz składnik na liście z boku, a dla reszty wykonujesz operację analogiczną jak dla całości.

[lustfingers]

Jeśli to do zupek amino to jest do tego apka na androida https://play.google.com/store/apps/details?...akalkulator.app

oraz kalkulator do pobrania: http://michalmleczko.waw.pl/kalkulator-wyg...ii-kasa-romana/

Ten post edytował lustfingers 22.09.2016, 04:39:23

[noche]

ja bym na początek spróbował posortować tablice malejąco
wrzucił do foreach'a coś na zasadzie $value <= $ szukana

[Pyton_000]

Łopatologiczne

[PHP] pobierz, plaintext 
<?php
 
$liczby = [1, 1.25, 1.5, 2, 2.5, 3, 5, 10, 15, 20];
$szukana = 18;
 
$wyniki = [];
rsort($liczby);
 
for($i=0, $c=count($liczby); $i<$c; $i++) {
    if($liczby[$i] > $szukana){
        continue;
    }
    $wyniki[$i][] = $liczby[$i];
 
    if($liczby[$i] == $szukana) {
        continue;
    }
 
    for($j=0; $j<$c; $j++) {
        if($j == $i) {
            continue;
        }
        $sum = array_sum($wyniki[$i])+$liczby[$j];
        if($sum > $szukana) {
            continue;
        }
        $wyniki[$i][] = $liczby[$j];
 
        if($sum == $szukana) {
            break;
        }
 
    }
    sort($wyniki[$i]);
}
array_walk($wyniki, function(&$val) {
    $val =  implode(',', $val);
});
 
$wyniki = array_unique($wyniki);
var_dump($wyniki);
[PHP] pobierz, plaintext 

[slawo]

Nie działa coś ten kod. Nie ukrywam nie poradzę sobie z tym nie mam na tyle wiedzy

[Pyton_000]

A u mnie działa:

Kod

array(5) {
  [1]=>
  string(4) "3,15"
  [2]=>
  string(6) "3,5,10"
  [5]=>
  string(6) "2.5,15"
  [6]=>
  string(6) "1,2,15"
  [7]=>
  string(11) "1.25,1.5,15"
}

[slawo]

Niby tak ale powinno zwrócić tylko 3+15 (najlepszą opcję). Poza tym niektóre sumy nie dają 18.

[Pyton_000]

Spoko, zmodyfikuj go sobie o przefiltrowanie wyników i będziesz miał gotowe

[Puszy]

Do użycia funkcja findComponents(), jeżeli możliwa jest kombinacja unikalnych składników zwróci ją lub false w przypadku braku takiej kombinacji. Choć wydaje mi się że skrypt ma wadę bo leci od największych składników przez co nie wszystkie kombinacje są możliwe :/

edit: jednak nie działa w pełni poprawnie, wysypuje się na floatach ale może Cię to na coś naprowadzi, tak na prawdę to potrzebny tu jest jedynie sensowny algorytm, przełożenie go na kod to już formalność.

[PHP] pobierz, plaintext 
$acceptable	=	[1, 1.25, 1.5, 2, 2.5, 3, 5, 10, 15, 20];
 
print_r(findComponents(18, $acceptable));
 
function findComponents($search, $acceptable){
	$components	=	findComponentsR($search, $acceptable);
	return array_sum($components) == $search ? $components : false;
}
 
function findComponentsR($search, $acceptable, $originalSearch=null, $components=[]){
 
	$components	=	array_unique($components);
 
	if(!is_null($originalSearch) && array_sum($components) == $originalSearch){
		return $components;
	}
 
	rsort($acceptable);
 
	foreach ($acceptable as $k => $v) {
		if ($v > $search) {
			unset($acceptable[$k]);
		} elseif($v == $search) {
			unset($acceptable[$k]);
			return [$v];
		}else{
			$components[] = $v;
			unset($acceptable[$k]);
 
			if(!empty($acceptable)) {
				$components = array_merge($components, findComponentsR($search - $v, $acceptable, $originalSearch, $components));
				break;
			}
		}
	}
	return array_unique($components);
}
[PHP] pobierz, plaintext 

Ten post edytował Puszy 30.09.2016, 15:17:09